Die Volltextsuche ist im Gegensatz zu den meisten anderen Problemen im Bereich des maschinellen Lernens ein Problem, mit dem Web-Programmierer 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 gab es keinen „Fehler“ bei der Suche, Es war nur so, dass die Suchergebnisse nicht den Wünschen des Kunden entsprachen. 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 Abfrage-Syntax verwendet, wie zum Beispiel „MATCH() ... AGAINST( )".
Okay, das Problem ist gelöst und die Blumen sind fertig! Dies ist kein Problem, wenn die Datenbankgröße klein ist.
Aber wenn Sie über immer mehr Daten verfügen, werden Sie feststellen, dass Ihre Datenbank immer langsamer wird. MySQL ist kein sehr einfach zu verwendendes Tool für die Volltextsuche. Sie entscheiden sich also für die Verwendung von ElasticSearch, überarbeiten Ihren Code und stellen einen Volltextsuchcluster bereit, der von Lucene unterstützt wird. Sie werden feststellen, dass es sehr gut, schnell und genau funktioniert.
An diesem Punkt kommen Sie nicht umhin, sich zu fragen: Warum ist Lucene so großartig? Dieser Artikel (hauptsächlich eine Einführung in TF-IDF, Okapi BM-25 und gewöhnliche Relevanzbewertungen) und der nächste Artikel (hauptsächlich eine Einführung in die Indizierung) informieren Sie über die Volltextsuche 🎜>Grundkonzept dahinter. Relevanz
Es gibt viele, viele Möglichkeiten, die Korrelation zwischen Texten 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.
Diesem Algorithmus ist es egal, ob das Wort ein Substantiv oder ein Verb ist, noch ist ihm die Bedeutung des Wortes egal. Das Einzige, was es interessiert, ist, welche Wörter häufig und welche selten sind. Wenn eine Suchanfrage sowohl gebräuchliche als auch seltene Wörter enthält, sollten Sie dem Dokument mit den seltenen Wörtern besser eine höhere Punktzahl geben und gleichzeitig die Gewichtung der gebräuchlichen Wörter verringern.
Dieser Algorithmus heißt Okapi BM25. Es enthält zwei Grundkonzepte: Worthäufigkeit (
Begriffshäufigkeit), abgekürzt als Begriffshäufigkeit („TF“), und inverse Dokumenthäufigkeit (inverse Dokument Häufigkeit), abgekürzt als („IDF“) . Die Zusammenstellung dieser Begriffe wird als „TF-IDF“ bezeichnet. Dabei handelt es sich um ein statistisches Maß, das angibt, wie wichtig ein Begriff in einem Dokument ist. TF-IDF
Begriffshäufigkeit (Inverse Document Frequency (
Inverse Document Frequency), auch „IDF“ genannt, 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 Suchanfragen 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 am besten mit der Abfrageanweisung übereinstimmt. Wie cool! Okapi BM25Der 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 wird er ElasticSearch genannt). Okapi BM25 fügt zwei einstellbare Parameter, k1 und b, basierend auf TF-IDF hinzu, die „Termfrequenzsättigung“ bzw. „Feldlängenspezifikation“ darstellen. Was zum Teufel ist das?
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, daher hat ein Dokument, in dem „Baseball“ 80 Mal vorkommt, eine doppelt so hohe Punktzahl wie eines, das 40 Mal vorkommt. Manchmal Zu diesem Zeitpunkt möchten wir, aber manchmal möchten wir dies nicht. Darüber hinaus verfügt Okapi BM25 auch über einen k1-Parameter, der zum Anpassen der Sättigungsänderungsrate verwendet wird. Der Wert des k1-Parameters liegt im Allgemeinen zwischen 1,2 und 2,0 . Je niedriger der Wert, desto schneller ist der Sättigungsprozess (was bedeutet, dass die beiden oben genannten Dokumente die gleiche Punktzahl haben, da sie beide eine große Anzahl des Wortes „Baseball“ enthalten).
Feldlängenreduzierung ( Feldlänge Durch die Normalisierung wird die Länge eines Dokuments auf die durchschnittliche Länge aller Dokumente reduziert. Dies ist nützlich für Sammlungen mit einem Feld (wie unsere), um Dokumente unterschiedlicher Länge auf die gleichen Vergleichskriterien zu vereinheitlichen. B. „Titel“ und „Körper“). Es kann auch die Felder „Titel“ und „Körper“ auf die gleiche Vergleichsbedingung vereinheitlichen. Die Feldlängenreduzierung wird durch b dargestellt und ihr Wert ist 0. Zwischen Wissen, was jeder Begriff in der Formel ist , es ist definitiv leicht zu verstehen, daher werden wir die Formel nicht erwähnen und direkt zum Code gehen:
Wir definieren eine einfache-String
in das
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;
};von Token zu analysieren. Auf diese Weise schreiben wir alle Token in Kleinbuchstaben (um die Entropie zu reduzieren und zu verbessern). der Matching-Grad („Walking“ und „Walk“-Matching sind gleich). Und wir filtern auch Stoppwörter (sehr häufige Wörter) heraus, um den Entropiewert weiter zu reduzieren. Bitte haben Sie Verständnis, wenn ich diesen Abschnitt zu sehr erkläre, bevor ich darauf eingehe Hier wirkt die Methode addDocument(): this.documents und this.terms sind eine Datenbank, die alle Dokumente speichert Der Originaltext des Dokuments, die Längeninformationen des Dokuments und eine Liste. Die Liste speichert die Anzahl und Häufigkeit aller Wörter und Wörter im Dokument. Mit dieser Datenstruktur können wir einfach und schnell (ja, sehr schnell) arbeiten (die Zeitkomplexität beträgt O(1)). Beantworten Sie die folgende Frage: Wie oft kommt das Wort „walk“ in Dokument Nr. 3 vor? 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 wird und die updateidf()-Methode
auskommentiertBM25.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;
};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);
}
};这是一个非常简单的函数，但是由于它需要遍历整个语料库中的所有词语，并更新所有词语的值，这就导致它工作的就有点慢。这个方法的实现采用了逆向文档频率 (inverse document frequency) 的标准公式（你可以在 Wikipedia 上找到这个公式）— 由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。我做了一些修改，让返回值一直大于0。
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);
};最后，search() 方法遍历所有的文档，并给出每个文档的 BM25 分数，然后按照由大到小的顺序进行排序。当然了，在搜索过程中遍历语料库中的每个文档实是不明智。这个问题在 Part Two （反向索引和性能）中得到解决。
上面的代码已经做了很好的注释，其要点如下：为每个文档和每个词语计算 BM25 分数。词语的 idf 分数已经预先计算好了，使用的时候只需要查询即可。词语频率作为文档属性的一部分也已经预先计算好了。之后只需要简单的四则运算即可。最后给每个文档增加一个临时变量 _score，然后根据 score 做降序排列并返回前 10 个结果。
上面的示例有很多方法进行优化，我们将在 “全文搜索”的第二部分中介绍它们，欢迎继续收看。我希望我能在几个星期之后完成它。下面列了下次将要提到的内容：
反向索引和快速搜索
快速索引
更好的搜索结果
为了这个演示，我编了一个小的维基百科爬虫，爬到相当多（85000）维基百科文章的第一段。由于索引到所有85K文件需要90秒左右，在我的电脑我已经削减了一半。不想让你们仅仅为了一个简单的全文本演示浪费你的笔记本电脑电量。
因为索引是一个繁重的、模块化的CPU操作，我把它当成一个网络工作者。索引运行在一个后台线程上–在这里你可以找到完整的源代码。你也会发现到词干算法和我的停用词列表中的源代码参考。至于代码许可，还是一如既往为教育目的而免费，而不用于任何商业目的。
最后是演示。一旦索引完成，尝试寻找随机的东西和短语，维基百科会知道的。注意，只有40000段的索引，所以你可能要尝试一些新的话题。
Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in den Beispielcode zur Relevanzbewertung für die JavaScript-Volltextsuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
