Zeichen in Query optimal aufteilen

[Maekkelrajter]

Für die Track-Suche mit der Spotify Web API wird eine Query erstellt mit den Filtern Titel, Artist und Album.

Beispiel:
Gesucht (Titel - Artist - Album):
The Only Thing Worth Fighting For - Rosanne Cash, Colin Meloy - She Remembers Everything (Deluxe)

Query (String):
track:The Only Thing Worth Fighting For artist:Rosanne Cash Colin Meloy album:She Remembers Everything (Deluxe)

Query (URLEncoded):
track%3AThe+Only+Thing+Worth+Fightin+artist%3ARosa nne+Cash+Colin+Meloy+album%3AShe+Remembers+Everyth ing+(Deluxe)

Eine Abfrage mit dieser syntaktisch korrekten Query liefert leider einen Error 400 (Bad Request). Nach langer Recherche habe ich herausgefunden dass die Gesamtlänge der Query offenbar nur maximal 100 Zeichen betragen darf. Das wird in der Dokumentation der Spotify Web API leider nirgendwo erwähnt, was auch im Spotify Developer Forum beklagt wird.
Nun mein Problem: Wie teile ich die verfügbaren Zeichen am effizientesten auf die drei Filter auf? 34 + 33 + 33 Zeichen liefert schon eine sehr gute Trefferquote:

Delphi-Quellcode:

    If length(Title) > 34 Then  setlength(title,34);
    If length(artist) > 33 Then  setlength(artist,33);
    If length(album) > 33 Then  setlength(album,33);
    query:= title + artist + album;
    query:= URLEncoder.encode(trim(query));

Es kommt jedoch nicht selten vor, dass eins der Elemente weniger als 33 bzw. 34 Zeichen lang ist. Wie schaffe ich es nun, 'freie' Zeichen so auf die anderen Filter zu verteilen, dass ich möglichst wenig abschneiden muss? Das ist anscheinend ein (für mich) ziemlich kniffliges Problem, für dessen Lösung wohl Informatik-Grundlagen ganz hilfreich wären, über die ich leider nicht verfüge. Vielleicht hat hier jemand einen Tipp oder hat gar eine Idee für den passenden Algorithmus?

Gruß LP

[himitsu]

Alles gleichmäßig verteilen ist einfach

du rechnest alle Längen zusammen und verteilt es prozenzual auf die Gesamtlänge auf

Code:

möglich := 34 + 33 + 33
gesamt := Title.Length + Artist.Length + Album.Length
faktor := möglich / gesamt

Title.Length * faktor 
Artist.Length * faktor 
Album.Length * faktor

Das was kürzer ist, würde dann prozentual auch abgeschnitten. (alles gleichmäßig zusammenschieben, bis es passt)

Als nächste Verainte nimmt für die Aufteilung nur das, was übersteht,
also erstmal das passende (maximal 33 bzw. 34) abziehen und dann nur mit dem Rest rechnen

Code:

möglich := 34 + 33 + 33
normal := max(Title.Length,34) + max(Artist.Length,33) + max(Album.Length,33)
zuviel := max(Title.Length-34,0) + max(Artist.Length-33,0) + max(Album.Length-33,0)
nochmöglich := möglich - normal

faktor := nochmöglich / zuviel

max(Title.Length,34) + max(Title.Length-34,0) * faktor 
max(Artist.Length,33) + max(Artist.Length-33,0) * faktor 
max(Album.Length,33) + max(Album.Length-33,0) * faktor

[Olli73]

Ungetestet:

Delphi-Quellcode:

var
  l1, l2, l3: Integer;
begin
  l1 := Length(title);
  l2 := Length(artist);
  l3 := Length(album);
  while (l1 + l2 + l3) > 100 do begin
    if l1 > 34 then
      Dec(l1);
    if (l1 + l2 + l3) <= 100 then
      break;
    if l2 > 33 then
      Dec(l2);
    if (l1 + l2 + l3) <= 100 then
      break;
    if l3 > 33 then
      Dec(l3);
  end;
  setlength(title, l1);
  setlength(artist, l2);
  setlength(album, l3);

end;

[Maekkelrajter]

Wie es aussieht, ist die Lösung des Problems doch einfacher als ich dachte. Himitsus mathematischer Ansatz ist zwar 'smarter', aber der Vorschlag von Olli73 schien mir vor allem wegen seiner einfachen und (für mich) gut durchschaubaren Struktur für meine Zwecke am besten geeignet.

Auf der Basis dieses Codes habe ich folgende Routine entwickelt:

Delphi-Quellcode:

Function GetQuery(title,artist,album: string): string;
var qlen,namlen,artlen,alblen: Integer;
    const nam = 40;                       // Werte können evtl. noch zur Optimierung des Suchergebnisses variiert werden
          art = 30;
          alb = 30;
          maxlen = nam + art + alb;       // maximal 100
begin
  namlen:= length(Title);
  artlen:= length(artist);
  alblen:= length(album);
  qlen:= namlen + artlen + alblen;
  If qlen > maxlen Then
  begin
    while qlen > maxlen do
    begin
      if alblen > alb then                    // Reihenfolge nach Priorität der Elemente
      begin
        Dec(alblen);
        dec(qlen);
        if qlen <= maxlen then break;
      end;
      if artlen > art then
      begin
        Dec(artlen);
        dec(qlen);
        if qlen <= maxlen then break;
      end;
      if namlen > nam then
      begin
        Dec(namlen);
        dec(qlen);
      end;
    end;
    setlength(title,namlen);
    setlength(artist,artlen);
    setlength(album,alblen);
  end;
  result:= title + artist + album;
end;

Das scheint hervorragend zu funktionieren. Die Trefferquote bei der Suche ist jedenfalls geradezu sensationell. Für die Konstanten werde ich noch einen Konfigurationsdialog basteln, der nur die Eingabe von Werten erlaubt, deren Summe den Maximalwert nicht überschreitet.
Nochmals Danke für die Hilfe!

Gruß LP

[himitsu]

Bei Olliver mußt du nur aufpassen, es wird von Allem gleich viel abgeschnitten,
also bleibt womöglich nur noch der Längste übrig.

Ein ganz langes Wort bekommt quasi Alles, von den kürzeren zu langen Wörtern.

**
*****++++++
*****+++++++++

**
*****++
*****+++++++++

Andersrum, also vom Kürzesten (längstem ohne Abschneiden) an Buchstaben hinzu, so lange noch Platz ist, würde die freien Buchstaben gleichmäßig verteilen

**
*****++++++
*****+++++++++

**
*****++
*****+++++++++

(nicht maßstabsgetreu)

Die mathematische Lösung kommt etwa auf das, wenn man Beides kombiniert, also das Mittelding, wie wenn man abwechselnd Stellen entfernt und hinzufügt

**
*****++++++
*****++++++++

**
*****++
*****+++++++++


Jenachdem was Einem wichtiger ist, gibt es optimalere Lösungen, wie man die Stellen verteilt (wie viel man wo weglässt)

[Maekkelrajter]

Zitat von himitsu:

Bei Olliver mußt du nur aufpassen, es wird von Allem gleich viel abgeschnitten,
also bleibt womöglich nur noch der Längste übrig.

Ein ganz langes Wort bekommt quasi Alles, von den kürzeren zu langen Wörtern.

Das kann überhaupt nicht passieren. Es wird nur abgeschnitten, solange die Gesamtlänge > 100 und der einzelne Filter länger als die vordefinierte Länge ist, in unserem Fall 30 bzw 40 Zeichen. Filter, die kleiner oder gleich 30 (40) Zeichen lang sind, werden nicht abgeschnitten. Wie man aus den Beispielen im Anhang sehen kann, funktioniert das einwandfrei.
Das einzige Problem ist wohl, ob die verbliebenen Fragmente für die Suche ausreichend signifikant sind. Erfahrungsgemäß sind die ersten Zeichen die wichtigsten und reichen in der Kombination Titel - Artist - Album fast immer für die Erkennung aus. Die Beispiele im Anhang wurden jedenfalls alle gefunden. Vermutlich verwendet Spotify ausgeklügelte Suchalgorithmen. Notfalls kann ich in meinem Programm die Suchfilter auch manuell modifizieren. Für den vorgesehenen Verwendungszweck ist die jetzige Lösung jedenfalls völlig ausreichend.

Gruß LP

[Redeemer]

Zitat von himitsu:

Alles gleichmäßig verteilen ist einfach

du rechnest alle Längen zusammen und verteilt es prozenzual auf die Gesamtlänge auf

Das Wort, das du suchst, heißt Sitzzuteilungsverfahren. In meinem ERP-System kommt sehr häufig das Hare-Niemeyer-Verfahren zum Einsatz.

Delphi-Quellcode:

function HareNiemeyer64(Stimmen: TInt64Array; const Sitze: Int64): TInt64Array;
var
  Stimmenanzahl: Int64;
  Stimmenzahl: Int64;
  Vergeben, Hoechste: Int64;
  i: Integer;
  SitzeFloat: array of Extended;
  Hoechstwert: Extended;
resourcestring
  _HareNiemeyer64DivBy0 = 'Hare-Niemeyer-Sitzzuteilungsverfahren (64-Bit-Integer) kann nicht durchgeführt werden, da 0 Stimmen abgegeben wurden. Eine Division durch 0 wäre unausweichlich.';
begin
  Stimmenanzahl := 0;
  for Stimmenzahl in Stimmen do
  Stimmenanzahl := Stimmenanzahl + Stimmenzahl;

  if Stimmenanzahl = 0 then
  raise EDivByZero.Create(_HareNiemeyer64DivBy0);

  Vergeben := 0;
  SetLength(Result, Length(Stimmen));
  SetLength(SitzeFloat, Length(Stimmen));
  for i := Low(Stimmen) to High(Stimmen) do
  begin
    SitzeFloat[i] := Stimmen[i] / Stimmenanzahl * Sitze;
    Result[i] := Floor(SitzeFloat[i]);
    Inc(Vergeben, Result[i]);
    SitzeFloat[i] := SitzeFloat[i] - Result[i];
  end;

  while Vergeben < Sitze do
  begin
    Hoechstwert := 0;
    Hoechste := Low(SitzeFloat);
    for i := Low(SitzeFloat) to High(SitzeFloat) do
    if SitzeFloat[i] > Hoechstwert then
    begin
      Hoechste := i;
      Hoechstwert := SitzeFloat[i];
    end;
    SitzeFloat[Hoechste] := 0;
    Inc(Result[Hoechste]);
    Inc(Vergeben);
  end;
end;

Anders als in meiner Software, wo der Algorithmus auch oft aufgerufen wird, wenn es weniger Stimmen als Sitze gibt, braucht man den hier natürlich nur ausführen, wenn man weniger Sitze als Stimmen hat. Der obige Algorithmus funktioniert mit negativen Stimmen wahrscheinlich nicht richtig.

Stimmen = die drei Längen
Sitze = 100

[Maekkelrajter]

Ich habe nun auch mal 'Hare-Niemeyer' mit Redeemers Code getestet. In den meisten Fällen liefert diese Methode gute Ergebnisse, nur bei extremen Längenunterschieden der einzelnen Elemente besteht eben die Gefahr, dass ausgerechnet die kürzesten bis zur Unkenntlichkeit gekappt werden.
Ein Problem bei allen Verfahren ist die Signifikanz der verbliebenen Fragmente. Besonders bei Klassik - Tracks können die Original - Querys bis zu 300 Zeichen lang werden.

Beispiel:
track:Also sprach Zarathustra, Op. 30, TrV 176: Prelude (Sonnenaufgang) - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Von den Hinterweltlern - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Von der großen Sehnsucht - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Von den Freuden und Leidenschaften - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Das Grablied - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Von der Wissenschaft - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Der Genesende - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Das Nachtwandlerlied - artist:Richard Strauss Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils
track:Also sprach Zarathustra, Op. 30, TrV 176: Das Tanzlied - Das Nachtlied - artist:Richard Strauss Michel Schwalbé Berliner Philharmoniker Herbert von Karajan - album:Strauss, R.: Also sprach Zarathustra; Till Eulenspiegel; Don Juan; Salomes Dance Of The Seven Veils

In diesem Fall sind die Track - Filter erst ab dem 50. Zeichen unterschiedlich. Die mit 'Hare-Niemeyer' gekürzten Filter sind aber nur noch 26 - 32 Zeichen lang. Bei der Suche wird dann, wenn überhaupt etwas gefunden wurde, nicht selten eine ellenlange Liste von Fundstellen zurückgegeben. Da muss ich dann die passende in meinem Programm per (Fuzzy-) Stringvergleich oder, wenn alles nichts hilft, 'von Hand' auswählen.
Den signifikanten Teil eines Filter-Strings zu finden ist, wenn überhaupt, wohl nur mit KI - Algorithmen möglich.
Die besten Ergebnisse habe ich mit meiner in Post #4 skizzierten Methode erzielt, mit der ich mit verschiedenen Kombinationen von Mindestlängen experimentieren kann.

Gruß LP

[Maekkelrajter]

Das eigentliche Problem hat sich weitgehend erledigt. In der Spotify Web API wurde die Limitierung der Such-Query von 100 auf 250 Zeichen erhöht. Aber auch das ist leider nirgendwo dokumentiert, ich habe das nur zufällig bei Experimenten herausgefunden. In meiner Mediathek mit 13100 Titeln sind immerhin 28 Tracks enthalten, bei denen eine Query nach dem Muster 'track:Track-Name artist:Artist-Name album:Album-Name' länger als 250 Zeichen ist. Bei einer Kürzung der Filter mit dem Algorithmus aus #4 und mit Werten wie im Anhang sichtbar werden alle 28 mit nur einer, nämlich der exakt übereinstimmenden Fundstelle, gefunden. Geht doch!