AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Zeichen in Query optimal aufteilen

Ein Thema von Maekkelrajter · begonnen am 2. Okt 2022 · letzter Beitrag vom 27. Okt 2022
Antwort Antwort
Maekkelrajter

Registriert seit: 8. Mär 2017
Ort: Köln
104 Beiträge
 
Delphi 10.4 Sydney
 
#1

Zeichen in Query optimal aufteilen

  Alt 2. Okt 2022, 13:59
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.727 Beiträge
 
Delphi 11 Alexandria
 
#2

AW: Zeichen in Query optimal aufteilen

  Alt 2. Okt 2022, 14:52
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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu ( 2. Okt 2022 um 14:56 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Olli73
Olli73

Registriert seit: 25. Apr 2008
Ort: Neunkirchen
538 Beiträge
 
#3

AW: Zeichen in Query optimal aufteilen

  Alt 2. Okt 2022, 15:00
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;
  Mit Zitat antworten Zitat
Maekkelrajter

Registriert seit: 8. Mär 2017
Ort: Köln
104 Beiträge
 
Delphi 10.4 Sydney
 
#4

AW: Zeichen in Query optimal aufteilen

  Alt 4. Okt 2022, 14:16
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.727 Beiträge
 
Delphi 11 Alexandria
 
#5

AW: Zeichen in Query optimal aufteilen

  Alt 4. Okt 2022, 17:38
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)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu ( 4. Okt 2022 um 17:53 Uhr)
  Mit Zitat antworten Zitat
Maekkelrajter

Registriert seit: 8. Mär 2017
Ort: Köln
104 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Zeichen in Query optimal aufteilen

  Alt 4. Okt 2022, 23:48
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
Miniaturansicht angehängter Grafiken
trimquery.jpg  
  Mit Zitat antworten Zitat
Redeemer

Registriert seit: 19. Jan 2009
Ort: Kirchlinteln (LK Verden)
952 Beiträge
 
Delphi 2009 Professional
 
#7

AW: Zeichen in Query optimal aufteilen

  Alt 5. Okt 2022, 09:36
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
Janni
2005 PE, 2009 PA, XE2 PA
  Mit Zitat antworten Zitat
Maekkelrajter

Registriert seit: 8. Mär 2017
Ort: Köln
104 Beiträge
 
Delphi 10.4 Sydney
 
#8

AW: Zeichen in Query optimal aufteilen

  Alt 7. Okt 2022, 13:25
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
  Mit Zitat antworten Zitat
Maekkelrajter

Registriert seit: 8. Mär 2017
Ort: Köln
104 Beiträge
 
Delphi 10.4 Sydney
 
#9

AW: Zeichen in Query optimal aufteilen

  Alt 27. Okt 2022, 13:38
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!
Miniaturansicht angehängter Grafiken
spotifyoptions.png  

Geändert von Maekkelrajter (27. Okt 2022 um 14:03 Uhr) Grund: Anhang bearbeitet
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf