Wie funktioniert die 'Awesome'-Leiste von Firefox beim Vergleichen von Zeichenfolgen?

Question

Die Frage ist, wie das Zeichenfolgen-Matching durchgeführt wird, um übereinstimmende Einträge in der Adressleiste von Firefox 3 zu finden. Das Matching von Teilzeichenfolgen bei jedem Eintrag könnte langsam sein. Welcher Algorithmus kann verwendet werden, um auf schnelle Weise an beliebiger Stelle übereinzustimmen?

Answer 1

Der Algorithmus der Adressleiste in Firefox 3.0 ist etwas kompliziert. Er erhält Daten aus zwei (drei für Firefox 3.5 und später) verschiedenen Abfragen:

• Bei der ersten Abfrage überprüft er die Tabelle moz_inputhistory, um zu sehen, ob die aktuelle Suchzeichenfolge in dieser Tabelle gespeichert ist. Diese Ergebnisse werden nach "Rang" sortiert, was eine Zahl ist, die bestimmt, wie kürzlich sie verwendet wurde. Diese Zahl wird einmal täglich abgebaut. Diese Suche sorgt dafür, dass die Adressleiste sich im Laufe der Zeit an das anpasst, was Sie auswählen (implementiert in Bug 95739).

• In Firefox 3.5 und später überprüft er dann die Tabelle moz_keyword nach Lesezeichen mit einem Schlüsselwort, das genau mit dem Suchtext übereinstimmt.

• Bei der letzten Abfrage durchläuft er jeden Eintrag in moz_places, der alle Besuche und Lesezeichen enthält. Diese Ergebnisse werden nach Häufigkeit und Aktualität sortiert.

In allen drei Fällen wird der folgende Algorithmus für das Matchen gegen die Tags, den Titel und die URL verwendet (unten als "durchsuchbarer Text" bezeichnet). Dies ist etwas schwierig zu erklären, daher ist es vielleicht einfacher, sich den Quellcode anzusehen.

1. Die Suchzeichenfolge wird in Tokens aufgeteilt, die durch Leerzeichen bestimmt sind (jedes Nicht-Leerzeichen "Wort" ist ein Token).
2. Für jedes Token beginnen Sie mit dem Vergleich jedes Zeichens des durchsuchbaren Textes und des Tokens auf eine Unicode-, Groß-/Kleinschreibung-ignorante Weise, bis es vollständig übereinstimmt. Wenn ein Satz von Zeichen nicht übereinstimmt, gehen Sie zum nächsten "Wortgrenze" im durchsuchbaren Text und versuchen es erneut.
3. Wenn wir eines der durchsuchbaren Texte finden, wird es in der Adressleiste angezeigt.
4. Wenn wir nicht genügend Ergebnisse haben (Standard sind 12), führen wir die Suche erneut durch, indem wir jedes Lesezeichen und jeden Besuch in der Historie durchgehen und den durchsuchbaren Text auf eine Unicode-, Groß-/Kleinschreibung-ignorante Weise für jedes Token irgendwo (nicht nur an Wortgrenzen) testen.

Hoffentlich erklärt das es auf verständliche Weise!

Answer 2

Der normale Weg, um eine schnelle Unterzeichenfolgen-Suche durchzuführen, besteht darin, eine Datenstruktur zu erstellen, die alle Suffixe aller Zeichenfolgen enthält, die Sie suchen möchten. Abhängig von der Organisation kann dies als "Suffixbaum" oder "Suffix-Array" bezeichnet werden. Wenn Sie beispielsweise 1000 Zeichenfolgen haben und jede 50 Zeichen lang ist, haben Sie 1.000 x 50 nicht-triviale Suffixe, d.h. Ihr Suffix-Array würde 50.000 Einträge haben.

Dann suchen Sie nach Übereinstimmungen, indem Sie binäre Suche (bei Arrays) oder Baumssuche (bei Bäumen) durchführen, um alle Suffixe in der Datenstruktur zu finden, deren Anfang mit der im Suchfeld eingegebenen Zeichenfolge übereinstimmt. Da es der Anfang des Suffixes ist, den Sie abgleichen, können Sie Standard-Suchverfahren (binäre Suche, Baumsuche) verwenden, um schnell zum Ergebnis zu gelangen. Jedes Suffix ist mit den Zeichenfolgen verknüpft, in denen es vorkommt.

Beispiel: Sie haben zwei Zeichenfolgen "CAT" und "DOT". Ihr Suffix-Array sieht wie folgt aus (Beachten Sie die lexikografische = alphabetische Reihenfolge):

#1 AT  --> CAT
#2 CAT --> CAT
#3 DOT --> DOT
#4 OT  --> DOT
#5 T   --> DOT, CAT

Beachten Sie, dass es sechs Suffixe gibt, aber zwei von ihnen sind gleich (das letzte "T" in "CAT" und "DOT") und beide werden durch denselben Eintrag (#5) repräsentiert.

Wenn der Benutzer jetzt die Suche z.B. "OT" (was "DOT" entsprechen sollte) eingibt, können Sie eine einfache lexikografische Suche in logarithmischer Zeit durchführen, da Sie jetzt nach einer Beginn-Übereinstimmung im Suffix-Array suchen.

Dies ist das grundlegende Prinzip der schnellen Textsuche, wenn das Suchmuster keine Platzhalter enthält.

Answer 3

Die Awesomebar schlägt URLs basierend auf einem Algorithmus namens dem Places Frecency-Algorithmus vor.

Laut der Mozilla-Entwicklerwebsite:

Das Wort "Frecency" selbst ist eine Kombination der Wörter "Frequenz" und "Relevanz".

Answer 4

Ich denke, dass dies dem zugrunde liegenden Speicher überlassen wird: Die SQLite-Datenbank, in der Firefox die von Ihnen besuchten Seiten speichert, bietet eine schnelle Funktion für die Teilzeichenfolgenvergleich.

Ich glaube, Firefox stellt eine SQL-Abfrage an die Datenbank. Dies geschieht recht schnell, da die Datenbank im Speicher zwischengespeichert ist.