Introduction détaillée à l'exemple de code de notation de pertinence pour la recherche en texte intégral JavaScript

La recherche en texte intégral, contrairement à la plupart des autres problèmes dans le domaine de l'apprentissage automatique, est un problème que les programmeurs Web rencontrent souvent dans leur travail quotidien. Le client peut vous demander de fournir un champ de recherche quelque part, puis vous écrirez une instruction SQL telle que WHERE title LIKE %:query% pour implémenter la fonction de recherche. Au début, cela ne posait aucun problème, jusqu'au jour où le client est venu vous voir et vous a dit : "Il y a eu une erreur dans la recherche !"

Bien sûr, il n'y a pas eu d'"erreur" dans la recherche, c'était simplement que les résultats de la recherche ne correspondaient pas à ce que souhaitait le client. L'utilisateur moyen ne sait pas comment effectuer une correspondance exacte, les résultats de recherche obtenus sont donc de mauvaise qualité. Pour résoudre le problème, vous décidez d'utiliser la recherche en texte intégral. Après une période d'apprentissage ennuyeux, vous avez activé le FULLTEXT index de MySQL et utilisé une syntaxe de requête plus avancée, telle que "MATCH() ... AGAINST( )".

Bon, le problème est résolu et les fleurs sont terminées ! Cela ne pose aucun problème lorsque la taille de la base de données est petite.

Mais lorsque vous avez de plus en plus de données, vous constaterez que votre base de données devient de plus en plus lente. MySQL n'est pas unoutil de recherche en texte intégral très facile à utiliser. Vous décidez donc d'utiliser ElasticSearch, de refactoriser votre code et de déployer un cluster de recherche en texte intégral optimisé par Lucene . Vous constaterez que cela fonctionne très bien, rapidement et avec précision.

À ce stade, vous ne pouvez pas vous empêcher de vous demander : pourquoi Lucene est-elle si géniale ?

Cet article (présente principalement TF-IDF, Ok

api BM-25 et les scores de pertinence ordinaires) et l'article suivant (présente principalement l'indexation) vous parleront de la recherche en texte intégral Le concept de base derrière tout cela.

Pertinence

Pour chaque requête de recherche, il est facile de définir un « score de pertinence » pour chaque document. Lorsque les utilisateurs effectuent une recherche, nous pouvons utiliser les scores de pertinence pour trier au lieu de l'heure d'apparition du document. De cette façon, le document le plus pertinent sera classé en premier, quelle que soit la date de sa création (bien sûr, cela est parfois également lié à l'heure de création du document).

Il existe de très nombreuses façons de calculer la corrélation entre du texte, mais nous commencerons par la méthode la plus simple, basée sur les statistiques. Cette méthode ne nécessite pas de compréhension de la langue elle-même, mais détermine un « score de pertinence » en comptant l'utilisation des mots, la correspondance et la pondération en fonction de la prévalence des mots uniques dans le document.

Cet algorithme ne se soucie pas de savoir si le mot est un nom ou un verbe, ni de la signification du mot. La seule chose qui l'intéresse, c'est de savoir quels mots sont courants et lesquels sont rares. Si une requête de recherche contient à la fois des mots courants et des mots rares, vous feriez mieux d'attribuer un score plus élevé au document contenant les mots rares tout en réduisant le poids des mots courants.

Cet algorithme s'appelle Okapi BM25. Il contient deux concepts de base : la fréquence des mots (

fréquence du terme), abrégée en fréquence du terme (« TF ») , et la fréquence inverse du document (inverse fréquence du document), abrégée en (« IDF ») . Leur regroupement s'appelle « TF-IDF », qui est une mesure statistique utilisée pour indiquer l'importance d'un terme dans un document.

TF-IDF

Term Frequency (

Term Frequency), appelé « TF », est une métrique très simple : le nombre de fois qu'un mot spécifique apparaît dans un document. Vous pouvez diviser cette valeur par le nombre total de mots du document pour obtenir un score. Par exemple, s’il y a 100 mots dans le document et que le mot « le » apparaît 8 fois, alors le TF du « le » est de 8 ou 8/100 ou 8 % (selon la façon dont vous souhaitez l’exprimer).

Inverse Document Frequency (

Inverse Document Frequency), appelée « IDF », est un peu plus compliquée : plus un mot est rare, plus cette valeur est élevée. Il s'obtient en divisant le nombre total de documents par le nombre de documents contenant le terme, puis en prenant le logarithme du quotient. Plus le mot est rare, plus le « Tsahal » qu’il produira sera élevé. Si vous multipliez ces deux nombres ensemble (TF*IDF), vous obtiendrez le poids d'un mot dans le document. Le « poids » est défini comme : quelle est la rareté du mot et à quelle fréquence apparaît-il dans le document ?

Vous pouvez utiliser ce concept pour les requêtes de recherche sur des documents. Pour chaque mot-clé de la requête, calculez leur score TF-IDF et additionnez-les. Le document ayant le score le plus élevé est celui qui correspond le mieux à l'instruction de requête.

Comme c'est cool !

Okapi BM25

L'algorithme ci-dessus est un algorithme utilisable, mais il n'est pas parfait. Il donne un algorithme de score de corrélation basé sur des statistiques, que nous pouvons encore améliorer.

Okapi BM25 est considéré jusqu'à présent comme l'un des algorithmes de classement les plus avancés (il s'appelle donc ElasticSearch). Okapi BM25 ajoute deux paramètres réglables, k1 et b, basés sur TF-IDF, qui représentent respectivement le « terme saturation de fréquence » et la « spécification de longueur de champ ». Qu'est-ce que c'est que ça ?

Pour comprendre intuitivement la « saturation de la fréquence des mots », imaginez deux articles de longueur similaire traitant du baseball. Supposons également que tous les documents (sauf ces deux-là) n’ont pas beaucoup de contenu lié au baseball, donc le mot « baseball » aura un IDF élevé – c’est extrêmement rare et important. Les deux articles discutent du baseball et y consacrent tous deux une place considérable, mais l’un utilise le mot « baseball » plus que l’autre. Alors dans ce cas, un article a-t-il vraiment un score très différent d’un autre article ? Puisque les deux documents parlent du baseball en général, peu importe que le mot « baseball » apparaisse 40 ou 80 fois. En fait, 30 fois devrait être le plafond !

Il s'agit de la "saturation de fréquence des mots". L'algorithme natif TF-IDF n'a aucune notion de saturation, donc un document avec "baseball" apparaissant 80 fois a un score deux fois plus élevé qu'un document qui apparaît 40 fois. Parfois, à ce moment-là, ce que nous voulons, mais parfois nous ne le voulons pas. De plus, l'Okapi BM25 dispose également d'un paramètre k1, qui sert à ajuster le taux de changement de saturation. La valeur du paramètre k1 est généralement comprise entre 1,2 et 2,0. . Plus la valeur est faible, plus le processus de saturation est rapide (ce qui signifie que les deux documents ci-dessus ont le même score, car ils contiennent tous deux un grand nombre du mot « baseball »)

Réduction de la longueur du champ ( Field-length). la normalisation réduit la longueur d'un document à la longueur moyenne de tous les documents. Ceci est utile pour les collections à champ unique (comme la nôtre) pour unifier les documents de longueurs différentes selon les mêmes critères de comparaison. Cela est plus significatif pour les collections à deux champs ( tels que "titre" et "corps"). Il peut également unifier les champs de titre et de corps selon la même condition de comparaison. La réduction de la longueur du champ est représentée par b et sa valeur est 0. Entre Savoir ce qu'est chaque terme de la formule. , c'est définitivement facile à comprendre, nous ne mentionnerons donc pas la formule et passerons directement au code :

Nous définissons une méthode simple

Statique

Tokenize(), le but. consiste à analyser la

chaîne

dans le

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;
};

tableau

de jetons De cette façon, nous réduisons tous les jetons (pour réduire l'entropie). L'algorithme de Porter Stemmer est utilisé pour réduire la quantité d'entropie et améliorer. le degré de correspondance ("marche" et "marche" sont les mêmes). Et nous filtrons également les mots vides (mots très courants) pour réduire davantage la valeur d'entropie. Veuillez me supporter si j'explique trop cette section avant d'entrer dans le vif du sujet. C'est là que la méthode addDocument() opère sa magie. Deux structures de données similaires : this.documents et this.terms this.documents est une base de données qui enregistre tous les documents originaux. le texte du document, les informations sur la longueur du document et une liste, la liste stocke le nombre et la fréquence de tous les mots et mots du document, en utilisant cette structure de données, nous pouvons facilement et rapidement (oui, très rapidement, seulement exiger. une complexité temporelle de O(1)). Nous utilisons également une autre structure de données, this.terms. Il représente tous les mots du corpus. Grâce à cette structure de données, nous pouvons répondre aux questions suivantes en temps O(1) : Dans combien de documents le mot « marcher » apparaît-il ? Quelle est leur identité ? Enfin, nous enregistrons la longueur de chaque document et enregistrons la longueur moyenne des documents sur l'ensemble du corpus.

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&#39;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&#39;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;
};

Notez que dans le code ci-dessus, idf est initialisé à 0 et la méthode updateidf() est

commentée

. En effet, cette méthode s'exécute très lentement et ne doit être exécutée qu'une seule fois, après l'indexation. Puisque l’exécuter une fois peut répondre aux besoins, il n’est pas nécessaire de l’exécuter 5 000 fois. Le commenter d’abord et l’exécuter après un grand nombre d’opérations d’indexation peut faire gagner beaucoup de temps. Voici le code de cette

fonction

:

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&#39;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&#39;t in any document.
            if (typeof this.terms[queryTerm] === &#39;undefined&#39;) {
                continue;
            }

            // This term isn&#39;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] === &#39;undefined&#39;) {
                continue;
            }

            // The term is in the document, let&#39;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段的索引，所以你可能要尝试一些新的话题。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!