Heute werden wir unsere eigene FTS-Engine schreiben. Am Ende dieses Artikels kann er in weniger als einer Millisekunde Millionen von Dokumenten durchsuchen. Wir beginnen mit einfachen Suchanfragen wie "Alle Dokumente mit cat zurückgeben" und erweitern dann die Engine, um komplexere logische Abfragen zu unterstützen.
Hinweis: Die bekannteste Volltextsuchmaschine ist Lucene (und auch Elasticsearch) und Solr darauf gebaut).
Warum brauchst du FTS?
Bevor Sie Code schreiben, könnten Sie fragen: "Könnten Sie nicht einfach grep oder eine Schleife verwenden, die jedes Dokument auf das Suchwort überprüft?" Ja, du kannst. Das ist aber nicht immer die beste Idee.
Gehäuse
Wir werden nach Fragmenten von Anmerkungen aus der englischsprachigen Wikipedia suchen. Der neueste Dump ist unter dumps.wikimedia.org verfügbar . Ab heute beträgt die Dateigröße nach dem Entpacken 913 MB. Die XML-Datei enthält mehr als 600.000 Dokumente.
Beispieldokument:
<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>Dokumente hochladen
Zunächst müssen Sie alle Dokumente mit einem sehr praktischen integrierten Paket aus dem Speicherauszug laden
encoding/xml:
import (
"encoding/xml"
"os"
)
type document struct {
Title string `xml:"title"`
URL string `xml:"url"`
Text string `xml:"abstract"`
ID int
}
func loadDocuments(path string) ([]document, error) {
f, err := os.Open(path)
if err != nil {
return nil, err
}
defer f.Close()
dec := xml.NewDecoder(f)
dump := struct {
Documents []document `xml:"doc"`
}{}
if err := dec.Decode(&dump); err != nil {
return nil, err
}
docs := dump.Documents
for i := range docs {
docs[i].ID = i
}
return docs, nil
}Jedem Dokument wird eine eindeutige ID zugewiesen. Der Einfachheit halber wird dem ersten geladenen Dokument die ID = 0, die zweite ID = 1 usw. zugewiesen.
Erster Versuch
Inhaltssuche
Jetzt haben wir alle Dokumente in den Speicher geladen. Versuchen wir, diejenigen zu finden, die Katzen erwähnen. Lassen Sie uns zunächst alle Dokumente durchgehen und sie auf einen Teilstring überprüfen
cat:
func search(docs []document, term string) []document {
var r []document
for _, doc := range docs {
if strings.Contains(doc.Text, term) {
r = append(r, doc)
}
}
return r
}Auf meinem Laptop dauert die Suche 103 ms - nicht schlecht. Wenn eine Stelle mehr Dokumente aus der Ausgabe überprüfen, können wir sehen , dass die Funktion Zufriedenheit auf dem Wort gibt Raupe und Kategorie , aber nicht bei Cat mit einem Großbuchstaben der C . Dies ist nicht genau das, wonach wir suchen.
Bevor Sie fortfahren, müssen Sie zwei Dinge beheben:
- Machen Sie die Suche ohne Berücksichtigung der Groß- und Kleinschreibung (damit die Ausgabe auch Cat enthält ).
- Berücksichtigen Sie Wortgrenzen, keine Teilzeichenfolgen (damit die Ausgabe keine Wörter wie Raupe und Kommunikation enthält ).
Suche mit regulären Ausdrücken
Eine offensichtliche Lösung, die beide Probleme löst, sind reguläre Ausdrücke .
In diesem Fall brauchen wir
(?i)\bcat\b:
(?i)bedeutet, dass bei der Regex die Groß- und Kleinschreibung nicht berücksichtigt wird
\bzeigt die Übereinstimmung mit Wortgrenzen an (ein Ort, an dem sich auf der einen Seite ein Zeichen befindet und auf der anderen nicht)
Aber jetzt dauerte die Suche mehr als zwei Sekunden. Wie Sie sehen können, wurde das System selbst bei einer bescheidenen Anzahl von 600.000 Dokumenten langsamer. Dieser Ansatz ist zwar einfach zu implementieren, lässt sich jedoch nicht sehr gut skalieren. Mit zunehmendem Datensatz müssen immer mehr Dokumente gescannt werden. Die zeitliche Komplexität dieses Algorithmus ist linear, dh die Anzahl der zu scannenden Dokumente entspricht der Gesamtzahl der Dokumente. Wenn wir 6 Millionen Dokumente anstelle von 600.000 hätten, würde die Suche 20 Sekunden dauern. Wir müssen uns etwas Besseres einfallen lassen.
Invertierter Index
Um Suchanfragen zu beschleunigen, verarbeiten wir den Text vor und erstellen einen Index.
Der Kern von FTS ist eine Datenstruktur, die als invertierter Index bezeichnet wird . Es verknüpft jedes Wort mit Dokumenten, die dieses Wort enthalten.
Beispiel:
documents = {
1: "a donut on a glass plate",
2: "only the donut",
3: "listen to the drum machine",
}
index = {
"a": [1],
"donut": [1, 2],
"on": [1],
"glass": [1],
"plate": [1],
"only": [2],
"the": [2, 3],
"listen": [3],
"to": [3],
"drum": [3],
"machine": [3],
}Unten sehen Sie ein reales Beispiel für einen invertierten Index. Dies ist ein Index in einem Buch, in dem dem Begriff Seitenzahlen folgen:
Textanalyse
Bevor Sie mit der Erstellung des Index beginnen, müssen Sie den Quelltext in eine Liste von Wörtern (Token) aufteilen, die für die Indizierung und Suche geeignet sind.
Der Textanalysator besteht aus einem Tokenizer und mehreren Filtern.
Tokenizer
Der Tokenizer ist der erste Schritt beim Parsen von Text. Seine Aufgabe ist es, den Text in eine Liste von Token umzuwandeln. Unsere Implementierung teilt den Text an Wortgrenzen und entfernt Satzzeichen:
func tokenize(text string) []string {
return strings.FieldsFunc(text, func(r rune) bool {
// Split on any character that is not a letter or a number.
return !unicode.IsLetter(r) && !unicode.IsNumber(r)
})
}> tokenize("A donut on a glass plate. Only the donuts.")
["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]Filter
In den meisten Fällen reicht es nicht aus, nur Text in eine Liste von Token zu konvertieren. Zusätzliche Normalisierung ist erforderlich, um die Indizierung und Suche zu erleichtern.
Kleinbuchstaben
Um die Groß- und Kleinschreibung nicht zu berücksichtigen, konvertiert der Kleinbuchstaben-Token Token in Kleinbuchstaben. Die Wörter cAt , Cat und caT sind alle auf cat normalisiert . Wenn wir später auf den Index verweisen, normalisieren wir die Suchabfragen auch in Kleinbuchstaben, sodass die cAt- Suchabfrage das Wort Cat findet .
Gemeinsame Wörter entfernen
Fast jeder englische Text enthält gebräuchliche Wörter wie a , I , The oder be . Sie werden als Stoppwörter bezeichnet und sind in fast allen Dokumenten vorhanden. Sie sollten daher entfernt werden.
Es gibt keine "offizielle" Stoppwortliste. Lassen Sie uns die Top 10 auf der OEC-Liste streichen . Fühlen Sie sich frei, es zu ergänzen:
var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
"a": {}, "and": {}, "be": {}, "have": {}, "i": {},
"in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}
func stopwordFilter(tokens []string) []string {
r := make([]string, 0, len(tokens))
for _, token := range tokens {
if _, ok := stopwords[token]; !ok {
r = append(r, token)
}
}
return r
}> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})
["donut", "on", "glass", "plate", "only", "donuts"]Stemming
Aufgrund von Grammatikregeln gibt es in Dokumenten verschiedene Formen von Wörtern. Stemming reduziert sie auf Grundform. Zum Beispiel Angeln , gefischt, und Fischer alle kochen hinunter zur Hauptfischform .
Das Implementieren von Stemming ist keine triviale Aufgabe und wird in diesem Artikel nicht behandelt. Nehmen wir eines der vorhandenen Module:
import snowballeng "github.com/kljensen/snowball/english"
func stemmerFilter(tokens []string) []string {
r := make([]string, len(tokens))
for i, token := range tokens {
r[i] = snowballeng.Stem(token, false)
}
return r
}> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})
["donut", "on", "glass", "plate", "only", "donut"]Hinweis: Stemmers funktionieren nicht immer richtig. Zum Beispiel können einige die Fluggesellschaft zum Flugzeug verkürzen .
Zusammenbau des Analysators
func analyze(text string) []string {
tokens := tokenize(text)
tokens = lowercaseFilter(tokens)
tokens = stopwordFilter(tokens)
tokens = stemmerFilter(tokens)
return tokens
}Der Tokenizer und die Filter konvertieren die Sätze in eine Liste von Token:
> analyze("A donut on a glass plate. Only the donuts.")
["donut", "on", "glass", "plate", "only", "donut"]Token sind für die Indizierung bereit.
Index erstellen
Kehren wir zum invertierten Index zurück. Es ordnet jedem Wort Dokument-IDs zu. Der integrierte Datentyp eignet sich gut zum Speichern einer Karte (Anzeigen)
map. Der Schlüssel ist ein Token (Zeichenfolge) und der Wert ist eine Liste von Dokument-IDs:
type index map[string][]intBeim Erstellen des Index werden Dokumente analysiert und ihre Kennungen zur Karte hinzugefügt:
func (idx index) add(docs []document) {
for _, doc := range docs {
for _, token := range analyze(doc.Text) {
ids := idx[token]
if ids != nil && ids[len(ids)-1] == doc.ID {
// Don't add same ID twice.
continue
}
idx[token] = append(ids, doc.ID)
}
}
}
func main() {
idx := make(index)
idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
idx.add([]document{{ID: 2, Text: "donut is a donut"}})
fmt.Println(idx)
}Alles arbeitet! Jedes Token in der Anzeige bezieht sich auf die IDs der Dokumente, die dieses Token enthalten:
map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]Anfragen
Bei Abfragen an den Index wenden wir denselben Tokenizer und dieselben Filter an, die wir für die Indizierung verwendet haben:
func (idx index) search(text string) [][]int {
var r [][]int
for _, token := range analyze(text) {
if ids, ok := idx[token]; ok {
r = append(r, ids)
}
}
return r
}> idx.search("Small wild cat")
[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]Und jetzt können wir endlich alle Dokumente finden, in denen Katzen erwähnt werden. Das Durchsuchen von 600.000 Dokumenten dauerte weniger als eine Millisekunde (18 μs)!
Bei einem invertierten Index ist die zeitliche Komplexität einer Suchabfrage linear mit der Anzahl der Suchtoken. Im obigen Abfragebeispiel werden neben der Analyse des Eingabetextes nur drei Kartensuchen durchgeführt.
Logische Abfragen
Die vorherige Anforderung gab eine nicht verknüpfte Liste von Dokumenten für jedes Token zurück. Aber wir erwarten in der Regel eine Suche nach kleinen Wildkatze auf eine Liste der Ergebnisse zurück , die sowohl enthalten kleine , wilde und Katze . Der nächste Schritt besteht darin, den Schnittpunkt zwischen den Listen zu berechnen. Auf diese Weise erhalten wir eine Liste der Dokumente, die allen Token entsprechen.
Glücklicherweise werden die IDs in unserem invertierten Index in aufsteigender Reihenfolge eingefügt. Da die IDs sortiert sind, können Sie den Schnittpunkt zwischen den Listen in linearer Zeit berechnen. Die Funktion
intersectiondurchläuft zwei Listen gleichzeitig und sammelt die Bezeichner, die in beiden vorhanden sind:
func intersection(a []int, b []int) []int {
maxLen := len(a)
if len(b) > maxLen {
maxLen = len(b)
}
r := make([]int, 0, maxLen)
var i, j int
for i < len(a) && j < len(b) {
if a[i] < b[j] {
i++
} else if a[i] > b[j] {
j++
} else {
r = append(r, a[i])
i++
j++
}
}
return r
}Der aktualisierte
searchanalysiert den angegebenen Anforderungstext, sucht nach Token und berechnet den angegebenen Schnittpunkt zwischen den ID-Listen:
func (idx index) search(text string) []int {
var r []int
for _, token := range analyze(text) {
if ids, ok := idx[token]; ok {
if r == nil {
r = ids
} else {
r = intersection(r, ids)
}
} else {
// Token doesn't exist.
return nil
}
}
return r
}Der Wikipedia-Dump enthält nur zwei Dokumente, die gleichzeitig die Wörter small , wild und cat enthalten :
> idx.search("Small wild cat")
130764 The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692 Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.Die Suche funktioniert wie erwartet!
Übrigens habe ich zuerst etwas über Katopums gelernt , hier ist eines davon:
Schlussfolgerungen
Also haben wir eine Volltextsuchmaschine erstellt. Trotz seiner Einfachheit kann es eine solide Grundlage für fortgeschrittenere Projekte bieten.
Ich habe nicht viele Aspekte erwähnt, die die Leistung erheblich verbessern und die Suche komfortabler machen können. Hier einige Ideen für weitere Verbesserungen:
- Fügen Sie logische Operatoren ODER und NICHT hinzu .
- Index auf Festplatte speichern:
- Bei jedem Neustart der Anwendung dauert es einige Zeit, den Index wiederherzustellen.
- Große Indizes passen möglicherweise nicht in den Speicher.
- Bei jedem Neustart der Anwendung dauert es einige Zeit, den Index wiederherzustellen.
- Experimentieren Sie mit speicher- und CPU-optimierten Datenformaten zum Speichern von ID-Sätzen. Schauen Sie sich Roaring Bitmaps an .
- Indizieren mehrerer Felder des Dokuments.
- Ergebnisse nach Relevanz sortieren.
Der gesamte Quellcode wird auf GitHub veröffentlicht .