Die Volltextsuche ist im Gegensatz zu den meisten anderen Problemen im Bereich des maschinellen Lernens ein Problem, mit dem Webprogrammierer bei ihrer täglichen Arbeit häufig konfrontiert werden. Der Kunde bittet Sie möglicherweise, irgendwo ein Suchfeld bereitzustellen, und dann schreiben Sie eine SQL-Anweisung wie WHERE title LIKE %:query%, um die Suchfunktion zu implementieren. Am Anfang war das kein Problem, bis der Kunde eines Tages zu Ihnen kam und sagte: „Bei der Suche ist ein Fehler aufgetreten!“
Natürlich ist an der Suche eigentlich nichts „falsch“, nur entsprechen die Suchergebnisse nicht den Wünschen des Kunden. Normale Benutzer wissen nicht, wie man einen exakten Abgleich durchführt, daher sind die Suchergebnisse, die sie erhalten, von schlechter Qualität. Um das Problem zu lösen, entscheiden Sie sich für die Volltextsuche. Nach einer Zeit langweiligen Lernens haben Sie den FULLTEXT-Index von MySQL aktiviert und eine erweiterte Abfragesyntax wie „MATCH() ... AGAINST()“ verwendet.
Okay, das Problem ist gelöst und die Blumen sind fertig! Dies ist kein Problem, wenn die Datenbankgröße klein ist.
An diesem Punkt kommen Sie nicht umhin, sich zu fragen: Warum ist Lucene so großartig?
Dieser Artikel (hauptsächlich Einführung in TF-IDF, Okapi BM-25 und gewöhnliche Relevanzbewertung) und der nächste Artikel (hauptsächlich Einführung in die Indizierung) erklären Ihnen die Grundkonzepte der Volltextsuche.
Relevanz
Für jede Suchanfrage definieren wir ganz einfach einen „Relevanzwert“ für jedes Dokument. Wenn Benutzer suchen, können wir Relevanzbewertungen anstelle der Erscheinungszeit des Dokuments zum Sortieren verwenden. Auf diese Weise wird das relevanteste Dokument an erster Stelle gereiht, unabhängig davon, wie lange seine Erstellung zurückliegt (manchmal hängt dies natürlich auch mit der Erstellungszeit des Dokuments zusammen).Es gibt viele, viele Möglichkeiten, die Korrelation zwischen Wörtern zu berechnen, aber wir beginnen mit der einfachsten, statistikbasierten Methode. Diese Methode erfordert kein Verständnis der Sprache selbst, sondern ermittelt einen „Relevanzwert“, indem Wortverwendung, Übereinstimmung und Gewichtung basierend auf der Verbreitung eindeutiger Wörter im Dokument gezählt werden.
Dieser Algorithmus heißt
TF-IDF
Term Frequency, oder kurz „TF“, ist eine sehr einfache Metrik: die Häufigkeit, mit der ein bestimmtes Wort in einem Dokument vorkommt. Sie können diesen Wert durch die Gesamtzahl der Wörter im Dokument dividieren, um eine Punktzahl zu erhalten. Wenn das Dokument beispielsweise 100 Wörter enthält und das Wort „the“ achtmal vorkommt, beträgt die TF von „the“ 8 oder 8/100 oder 8 % (je nachdem, wie Sie es ausdrücken möchten).Inverse Document Frequency, kurz „IDF“, ist etwas komplizierter: Je seltener ein Wort, desto höher ist dieser Wert. Man erhält ihn, indem man die Gesamtzahl der Dokumente durch die Anzahl der Dokumente dividiert, die den Begriff enthalten, und dann den Quotienten logarithmiert. Je seltener das Wort, desto höher ist der „IDF“, den es erzeugt.
Wenn Sie diese beiden Zahlen miteinander multiplizieren (TF*IDF), erhalten Sie die Gewichtung eines Wortes im Dokument. „Gewicht“ ist definiert als: Wie selten ist das Wort und wie oft kommt es im Dokument vor?
Sie können dieses Konzept für Suchabfragen zu Dokumenten verwenden. Berechnen Sie für jedes Schlüsselwort in der Abfrage den TF-IDF-Score und addieren Sie ihn. Das Dokument mit der höchsten Punktzahl ist das Dokument, das der Abfrageanweisung am besten entspricht.
Wie cool!
Okapi BM25
Der obige Algorithmus ist ein verwendbarer Algorithmus, aber er ist nicht perfekt. Es liefert einen statistisch basierten Korrelationsbewertungsalgorithmus, den wir weiter verbessern können.Okapi BM25 gilt als einer der bisher fortschrittlichsten Ranking-Algorithmen (daher der Name
Um „Worthäufigkeitssättigung“ intuitiv zu verstehen, stellen Sie sich bitte zwei Artikel ähnlicher Länge vor, in denen es um Baseball geht. Nehmen wir außerdem an, dass alle Dokumente (außer diesen beiden) nicht viel Baseball-bezogenen Inhalt haben, sodass das Wort „Baseball“ einen hohen IDF hat – es ist äußerst selten und wichtig. In beiden Artikeln geht es um Baseball, und beide widmen ihm viel Raum, aber der eine verwendet das Wort „Baseball“ häufiger als der andere. Hat also in diesem Fall ein Artikel wirklich eine ganz andere Punktzahl als ein anderer Artikel? Da es in beiden Dokumenten um Baseball im Allgemeinen geht, spielt es keine Rolle, ob das Wort „Baseball“ 40-mal oder 80-mal vorkommt. Tatsächlich sollte die Obergrenze bei 30 liegen!
Dies ist „Worthäufigkeitssättigung“. Der native TF-IDF-Algorithmus kennt kein Konzept der Sättigung, sodass ein Dokument, in dem „Baseball“ 80 Mal vorkommt, eine doppelt so hohe Punktzahl hat wie eines, das 40 Mal vorkommt. Manchmal ist es das, was wir wollen, aber manchmal wollen wir das nicht
Darüber hinaus verfügt Okapi BM25 auch über einen k1-Parameter, der zur Anpassung der Sättigungsänderungsrate verwendet wird. Der Wert des Parameters k1 liegt im Allgemeinen zwischen 1,2 und 2,0. Je niedriger der Wert, desto schneller erfolgt der Sättigungsprozess. (Das bedeutet, dass die beiden oben genannten Dokumente die gleiche Punktzahl haben, da beide das Wort „Baseball“ häufig enthalten.)
Feldlängennormalisierung reduziert die Länge des Dokuments auf die durchschnittliche Länge aller Dokumente. Dies ist bei Einzelfeldsammlungen (wie unserer) nützlich, um Dokumente unterschiedlicher Länge auf die gleichen Vergleichskriterien zu vereinheitlichen. Dies ist sinnvoller für Sammlungen mit zwei Feldern (z. B. „Titel“ und „Text“), wodurch auch die Felder „Titel“ und „Text“ auf dieselben Vergleichskriterien vereinheitlicht werden. Die Reduzierung der Feldlänge wird durch b dargestellt, der einen Wert zwischen 0 und 1 hat, wobei 1 vollständige Reduzierung und 0 keine Reduzierung bedeutet.
Algorithmus
Sie können mehr über die Formel des Okapi-Algorithmus in Okapi BM25 Wikipedia erfahren. Da wir nun wissen, was jeder Begriff in der Formel ist, muss er leicht zu verstehen sein. Erwähnen wir also die Formel nicht und gehen wir direkt zum Code über:
BM25.Tokenize = function(text) {
text = text
.toLowerCase()
.replace(/\W/g, ' ')
.replace(/\s+/g, ' ')
.trim()
.split(' ')
.map(function(a) { return stemmer(a); });
// Filter out stopStems
var out = [];
for (var i = 0, len = text.length; i < len; i++) {
if (stopStems.indexOf(text[i]) === -1) {
out.push(text[i]);
}
}
return out;
};
Wir definieren eine einfache statische Methode Tokenize(), um Zeichenfolgen in ein Array von Tokens zu analysieren. Das war's, wir schreiben alle Token in Kleinbuchstaben (um die Entropie zu reduzieren). Wir führen den Porter-Stemmer-Algorithmus aus, um die Entropiemenge zu reduzieren und gleichzeitig den Grad der Übereinstimmung zu verbessern („Walking“- und „Walk“-Matching sind gleich). Und wir filtern auch Stoppwörter (sehr häufige Wörter) heraus, um die Entropie weiter zu reduzieren. Bevor ich mich zu sehr mit den Konzepten befasse, über die ich schreibe, haben Sie bitte Verständnis, wenn ich diesen Abschnitt zu sehr erkläre.
BM25.prototype.addDocument = function(doc) {
if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); };
if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); };
// Raw tokenized list of words
var tokens = BM25.Tokenize(doc.body);
// Will hold unique terms and their counts and frequencies
var _terms = {};
// docObj will eventually be added to the documents database
var docObj = {id: doc.id, tokens: tokens, body: doc.body};
// Count number of terms
docObj.termCount = tokens.length;
// Increment totalDocuments
this.totalDocuments++;
// Readjust averageDocumentLength
this.totalDocumentTermLength += docObj.termCount;
this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;
// Calculate term frequency
// First get terms count
for (var i = 0, len = tokens.length; i < len; i++) {
var term = tokens[i];
if (!_terms[term]) {
_terms[term] = {
count: 0,
freq: 0
};
};
_terms[term].count++;
}
// Then re-loop to calculate term frequency.
// We'll also update inverse document frequencies here.
var keys = Object.keys(_terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
// Term Frequency for this document.
_terms[term].freq = _terms[term].count / docObj.termCount;
// Inverse Document Frequency initialization
if (!this.terms[term]) {
this.terms[term] = {
n: 0, // Number of docs this term appears in, uniquely
idf: 0
};
}
this.terms[term].n++;
};
// Calculate inverse document frequencies
// This is SLOWish so if you want to index a big batch of documents,
// comment this out and run it once at the end of your addDocuments run
// If you're only indexing a document or two at a time you can leave this in.
// this.updateIdf();
// Add docObj to docs db
docObj.terms = _terms;
this.documents[docObj.id] = docObj;
};
Hier erscheint auf magische Weise die Methode addDocument(). Wir erstellen und pflegen grundsätzlich zwei ähnliche Datenstrukturen: this.documents und this.terms.
This.documentsis ist eine Datenbank, die alle Dokumente speichert. Sie speichert den gesamten Originaltext des Dokuments, die Längeninformationen des Dokuments und eine Liste, die alle Wörter im Dokument sowie deren Anzahl und Häufigkeit speichert die Worte. Mithilfe dieser Datenstruktur können wir die folgenden Fragen einfach und schnell beantworten (ja, sehr schnell, es ist nur eine Hash-Tabellen-Abfragezeit mit einer Zeitkomplexität von O(1) erforderlich): Gehen Sie in Dokument Nr. 3 wie oft durch Wort erscheint?
Wir verwenden auch eine andere Datenstruktur, this.terms. Es repräsentiert alle Wörter im Korpus. Durch diese Datenstruktur können wir in O(1)-Zeit die folgenden Fragen beantworten: In wie vielen Dokumenten kommt das Wort „walk“ vor? Wie lautet ihre ID?
Abschließend erfassen wir die Länge jedes Dokuments und erfassen die durchschnittliche Länge der Dokumente im gesamten Korpus.
Beachten Sie, dass im obigen Code idf auf 0 initialisiert und die updateidf()-Methode auskommentiert ist. Dies liegt daran, dass diese Methode sehr langsam läuft und nach der Indizierung nur einmal ausgeführt werden muss. Da eine einmalige Ausführung die Anforderungen erfüllen kann, ist es nicht erforderlich, sie 5.000 Mal auszuführen. Es kann viel Zeit sparen, wenn Sie es zuerst auskommentieren und nach einer großen Anzahl von Indizierungsvorgängen ausführen. Hier ist der Code für diese Funktion:
BM25.prototype.updateIdf = function() {
var keys = Object.keys(this.terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
var num = (this.totalDocuments - this.terms[term].n + 0.5);
var denom = (this.terms[term].n + 0.5);
this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
}
};
Dies ist eine sehr einfache Funktion, aber da sie alle Wörter im gesamten Korpus durchlaufen und die Werte aller Wörter aktualisieren muss, ist sie etwas langsam. Diese Methode wird mithilfe der Standardformel für die inverse Dokumenthäufigkeit implementiert (diese Formel finden Sie auf Wikipedia): Teilen Sie die Gesamtzahl der Dokumente durch die Anzahl der Dokumente, die das Wort enthalten, und logarithmieren Sie dann den Quotienten get. Ich habe einige Änderungen vorgenommen, sodass der Rückgabewert immer größer als 0 ist.
BM25.prototype.search = function(query) {
var queryTerms = BM25.Tokenize(query);
var results = [];
// Look at each document in turn. There are better ways to do this with inverted indices.
var keys = Object.keys(this.documents);
for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
var id = keys[j];
// The relevance score for a document is the sum of a tf-idf-like
// calculation for each query term.
this.documents[id]._score = 0;
// Calculate the score for each query term
for (var i = 0, len = queryTerms.length; i < len; i++) {
var queryTerm = queryTerms[i];
// We've never seen this term before so IDF will be 0.
// Means we can skip the whole term, it adds nothing to the score
// and isn't in any document.
if (typeof this.terms[queryTerm] === 'undefined') {
continue;
}
// This term isn't in the document, so the TF portion is 0 and this
// term contributes nothing to the search score.
if (typeof this.documents[id].terms[queryTerm] === 'undefined') {
continue;
}
// The term is in the document, let's go.
// The whole term is :
// IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
// IDF is pre-calculated for the whole docset.
var idf = this.terms[queryTerm].idf;
// Numerator of the TF portion.
var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
// Denomerator of the TF portion.
var denom = this.documents[id].terms[queryTerm].count
+ (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));
// Add this query term to the score
this.documents[id]._score += idf * num / denom;
}
if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
results.push(this.documents[id]);
}
}
results.sort(function(a, b) { return b._score - a._score; });
return results.slice(0, 10);
};
Schließlich durchläuft die Methode search() alle Dokumente, gibt die BM25-Bewertung für jedes Dokument aus und sortiert sie dann in absteigender Reihenfolge. Natürlich wäre es unklug, bei der Suche jedes Dokument im Korpus durchzugehen. Dieses Problem wird im zweiten Teil (Invertierte Indizes und Leistung) behandelt.
Der obige Code ist gut kommentiert und der Kerninhalt lautet wie folgt: Berechnen Sie den BM25-Score für jedes Dokument und jedes Wort. Der IDF-Score des Wortes wurde vorberechnet und Sie müssen ihn nur abfragen, wenn Sie ihn verwenden. Worthäufigkeiten werden ebenfalls im Rahmen der Dokumenteigenschaften vorberechnet. Danach sind nur noch vier einfache Rechenoperationen nötig. Fügen Sie schließlich jedem Dokument eine temporäre Variable _score hinzu, sortieren Sie es dann in absteigender Reihenfolge nach der Punktzahl und geben Sie die Top-10-Ergebnisse zurück.
Beispiele, Quellcode, Hinweise und nächste Schritte
Es gibt viele Möglichkeiten, das obige Beispiel zu optimieren, wir werden sie im zweiten Teil von „Volltextsuche“ vorstellen, bitte bleiben Sie dran. Ich hoffe, dass ich es in ein paar Wochen fertigstellen kann. Nachfolgend finden Sie eine Liste der Dinge, die beim nächsten Mal erwähnt werden:
Für diese Demonstration habe ich einen kleinen Wikipedia-Crawler geschrieben, der zum ersten Absatz einiger (85.000) Wikipedia-Artikel gecrawlt hat. Da die Indizierung aller 85-KByte-Dateien etwa 90 Sekunden dauert, habe ich sie auf meinem Computer halbiert. Ich möchte nicht, dass Sie die Leistung Ihres Laptops nur für eine einfache Volltextpräsentation verschwenden.
Da die Indizierung ein schwerer, modularer CPU-Vorgang ist, behandle ich sie als Netzwerkarbeiter. Die Indizierung läuft in einem Hintergrundthread –Den vollständigen Quellcode finden Sie hier. Sie finden auch Quellcode-Verweise auf den Stemming-Algorithmus und meine Stoppwortliste. Die Codelizenz ist für Bildungszwecke weiterhin kostenlos und nicht für kommerzielle Zwecke.
Endlich die Demo. Sobald der Index vollständig ist, versuchen Sie, nach zufälligen Dingen und Phrasen zu suchen, und Wikipedia wird davon erfahren. Beachten Sie, dass nur 40.000 Segmente indiziert sind. Vielleicht möchten Sie also einige neue Themen ausprobieren.
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
