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 rien de « mal » avec la recherche, c’est juste que les résultats de la recherche ne correspondent pas à ce que veut le client. Les utilisateurs ordinaires ne savent pas comment effectuer une correspondance exacte, les résultats de recherche qu'ils obtiennent 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é l'index FULLTEXT de MySQL et utilisé une syntaxe de requête plus avancée, telle que "MATCH() ... AGAINST()".
Voilà, 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 un outil de recherche en texte intégral très simple à 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ésentant principalement TF-IDF, Okapi BM-25 et la notation de pertinence ordinaire) et le prochain article (présentant principalement l'indexation) vous expliqueront les concepts de base derrière la recherche en texte intégral.
Pertinence
Pour chaque requête de recherche, nous définissons facilement 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 les mots, 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 et de réduire le poids des mots courants.
Cet algorithme s'appelle Okapi BM25. Il contient deux concepts de base : la fréquence des termes (fréquence du terme), abrégée en fréquence du terme ("TF"), et la fréquence inverse du document (en abrégé "IDF"). En les regroupant, on l'appelle "TF-IDF", ce qui est. une mesure statistique utilisée pour indiquer l'importance d'un terme dans un document.
TF-IDF
La fréquence des termes, ou « TF » en abrégé, est une mesure 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, ou « IDF » en abrégé, est un peu plus compliqué : 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 (d'où le nom 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, c'est ce que nous voulons, mais parfois nous ne voulons pas ça.
De plus, l'Okapi BM25 dispose également d'un paramètre k1, qui est utilisé pour 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 beaucoup du mot "baseball")
La normalisation de la longueur du champ réduit la longueur du document à la longueur moyenne de tous les documents. Ceci est utile pour les collections à champ unique (comme la nôtre), afin d'unifier des documents de différentes longueurs selon les mêmes critères de comparaison. Cela a plus de sens pour les collections à deux champs (telles que « titre » et « corps »), qui unifient également les champs titre et corps selon les mêmes critères de comparaison. La réduction de la longueur du champ est représentée par b, qui a une valeur comprise entre 0 et 1, 1 signifiant une réduction complète et 0 signifiant aucune réduction.
Algorithme
Vous pouvez en apprendre davantage sur la formule de l'algorithme Okapi dans Okapi BM25 Wikipedia . Maintenant que nous savons ce qu’est chaque terme de la formule, cela doit être facile à comprendre. Alors ne mentionnons pas la formule et passons directement au code :
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;
};
Nous définissons une méthode statique simple Tokenize() pour analyser les chaînes dans un tableau de jetons. Voilà, nous mettons tous les jetons en minuscules (pour réduire l'entropie). Nous exécutons l'algorithme Porter Stemmer pour réduire la quantité d'entropie tout en améliorant le degré de correspondance (la correspondance "marche" et "marche" sont identiques). Et nous filtrons également les mots vides (mots très courants) pour réduire davantage l'entropie. Avant d’approfondir les concepts sur lesquels j’écris, soyez indulgents avec moi si j’explique trop cette section.
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;
};
C'est ici que la méthode addDocument() apparaît comme par magie. Nous construisons et maintenons essentiellement deux structures de données similaires : this.documents et this.terms.
This.documents est une base de données qui stocke tous les documents. Il stocke tout le texte original du document, les informations sur la longueur du document et une liste qui stocke tous les mots du document ainsi que le nombre et la fréquence d'occurrence de ceux-ci. les mots. En utilisant cette structure de données, nous pouvons répondre facilement et rapidement aux questions suivantes (oui, très rapidement, ne nécessitant qu'un temps de requête de table de hachage d'une complexité temporelle O(1)) : Dans le document n°3, « parcourez » ceci Combien de fois le le mot apparaît-il ?
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 un 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.
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);
}
};
C'est une fonction très simple, mais comme elle doit parcourir tous les mots de l'ensemble du corpus et mettre à jour les valeurs de tous les mots, elle fonctionne un peu lentement. Cette méthode est mise en œuvre en utilisant la formule standard de fréquence inverse des documents (vous pouvez trouver cette formule sur Wikipédia) - divisez le nombre total de documents par le nombre de documents contenant le mot, puis prenez le logarithme du quotient get. J'ai apporté quelques modifications pour que la valeur de retour soit toujours supérieure à 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);
};
Enfin, la méthode search() parcourt tous les documents et donne le score BM25 de chaque document, puis les trie par ordre décroissant. Bien entendu, il ne serait pas judicieux de parcourir tous les documents du corpus lors de la recherche. Ce problème est abordé dans la deuxième partie (Indices inversés et performances).
Le code ci-dessus est bien commenté et l'essentiel est le suivant : Calculez le score BM25 pour chaque document et chaque mot. Le score idf du mot a été pré-calculé et il vous suffit de l'interroger lors de son utilisation. Les fréquences des mots sont également précalculées dans le cadre des propriétés du document. Après cela, seules quatre opérations arithmétiques simples sont nécessaires. Enfin, ajoutez une variable temporaire _score à chaque document, puis triez-la par ordre décroissant selon le score et renvoyez les 10 meilleurs résultats.
Exemples, code source, notes et prochaines étapes
Il existe de nombreuses façons d'optimiser l'exemple ci-dessus, nous les présenterons dans la deuxième partie de "Recherche en texte intégral", restez à l'écoute. J'espère pouvoir le terminer dans quelques semaines. Vous trouverez ci-dessous une liste de choses qui seront mentionnées la prochaine fois :
Pour cette démonstration, j'ai écrit un petit robot d'exploration Wikipédia qui a exploré le premier paragraphe de plusieurs (85 000) articles Wikipédia. Étant donné que l'indexation des 85 000 fichiers prend environ 90 secondes, sur mon ordinateur, j'ai réduit ce délai de moitié. Je ne veux pas que vous gaspilliez la puissance de votre ordinateur portable juste pour une simple présentation en texte intégral.
Étant donné que l'indexation est une opération CPU lourde et modulaire, je la traite comme un travailleur de réseau. L'indexation s'exécute sur un fil d'arrière-plan --Vous pouvez trouver le code source complet ici. Vous trouverez également des références de code source à l'algorithme de stemming et à ma liste de mots vides. Quant à la licence de code, elle est toujours gratuite à des fins pédagogiques et non à des fins commerciales.
Enfin, la démo. Une fois l'index terminé, essayez de rechercher des éléments et des expressions aléatoires et Wikipédia le saura. Notez qu'il n'y a que 40 000 segments indexés, vous souhaiterez peut-être essayer de nouveaux sujets.
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
