Algorithme pour trouver des articles avec un texte similaire

J’ai de nombreux articles dans une firebase database (avec titre, texte), je cherche un algorithme pour trouver les articles les plus similaires aux X, quelque chose comme “Questions connexes” de Stack Overflow lorsque vous posez une question.

J’ai essayé de googler pour cela, mais j’ai seulement trouvé des pages sur d’autres problèmes de “texte similaire”, quelque chose comme comparer chaque article avec tous les autres et stocker une similitude quelque part. SO le fait “en temps réel” sur le texte que je viens de taper.

Comment?

La distance de modification n’est pas un candidat probable, car elle dépendrait de l’orthographe et de l’ordre des mots, et serait beaucoup plus coûteuse en calculs que Will vous en fait croire, compte tenu de la taille et du nombre de documents qui vous intéresseraient.

Quelque chose comme Lucene est la voie à suivre. Vous indexez tous vos documents, puis, lorsque vous souhaitez rechercher des documents similaires à un document donné, vous transformez votre document en requête et recherchez l’index. En interne, Lucene utilisera tf-idf et un index inversé pour que l’ensemble du processus prenne un certain temps proportionnel au nombre de documents pouvant éventuellement correspondre, et non au nombre total de documents de la collection.

Cela dépend de votre définition de similitude.

L’algorithme d’ édition-distance est l’algorithme standard pour les suggestions de dictionnaires (de langue latine) et peut fonctionner sur des textes entiers. Deux textes sont similaires s’ils contiennent essentiellement les mêmes mots (eh) dans le même ordre. Donc, les deux critiques de livres suivantes seraient assez similaires:

1) “C’est un bon livre”

2) “Ce ne sont pas de grands livres”

(Le nombre de lettres à supprimer, insérer, supprimer ou modifier pour tourner (2) en (1) est appelé «distance de modification».)

Pour mettre en œuvre cela, vous voudriez visiter chaque revue par programmation. Ce n’est peut-être pas aussi coûteux que cela en a l’air, et si c’est trop coûteux, vous pouvez faire les comparaisons en tâche de fond et stocker le n-most-similiar dans un champ de firebase database lui-même.

Une autre approche consiste à comprendre quelque chose de la structure des langues (latines). Si vous dépouillez des mots courts (non capitalisés ou cités) et atsortingbuez des poids à des mots (ou préfixes) communs ou uniques, vous pouvez effectuer une comparaison bayésienne. Les deux critiques de livres suivantes peuvent être simulées et trouvées similaires:

3) “La révolution française était bla bla la guerre et la paix bla bla France.” -> France / Français (2) Révolution (1) Guerre (1) Paix (1) (notez qu’un dictionnaire a été utilisé pour combiner la France et le français)

4) “Ce livre est bla bla une révolution dans la cuisine française.” -> France (1) Révolution (1)

Pour l’implémenter, vous devez identifier les «mots clés» dans une critique lors de sa création / mise à jour et rechercher des avis similaires utilisez ces mots clés dans la clause where d’une requête (idéalement une recherche en «texte intégral» si la firebase database le prend en charge) ), avec peut-être un post-traitement du jeu de résultats pour la notation des candidats trouvés.

Les livres ont aussi des catégories – les thrillers en France sont-ils similaires aux études historiques de la France, etc.? Des métadonnées au-delà du titre et du texte pourraient être utiles pour garder les résultats pertinents.

Le tutoriel sur ce lien ressemble à ce dont vous avez besoin. Il est facile à suivre et fonctionne très bien.

Son algorithme récompense à la fois les sous-chaînes communes et un ordre commun de ces sous-chaînes et devrait donc bien choisir les titres similaires.

Je suggère d’indexer vos articles à l’aide d’ Apache Lucene , une bibliothèque de moteurs de recherche de texte hautes performances et complète, entièrement écrite en Java. Il s’agit d’une technologie adaptée à presque toutes les applications nécessitant une recherche en texte intégral, en particulier sur plusieurs plates-formes . Une fois indexé, vous pouvez facilement trouver des articles connexes.

Un algorithme commun utilisé est la carte auto-organisasortingce . C’est un type de réseau neuronal qui classera automatiquement vos articles. Ensuite, vous pouvez simplement trouver l’emplacement d’un article en cours dans la carte et tous les articles à proximité sont liés. La partie importante de l’algorithme est la façon dont vous devez quantifier vos entrées par vecteur . Il y a plusieurs façons de faire avec du texte. Vous pouvez hacher votre document / titre, vous pouvez compter les mots et les utiliser comme vecteur à n dimensions, etc. J’espère que cela vous aidera, même si j’ai peut-être ouvert une boîte de Pandore pour un voyage sans fin en IA.

SO ne fait la comparaison que sur le titre, pas sur le corps du texte de la question, donc uniquement sur des chaînes plutôt courtes.

Vous pouvez utiliser leur algorithme (aucune idée de ce à quoi il ressemble) sur le titre de l’article et les mots-clés. Si vous avez plus de temps cpu à graver, également sur les résumés de vos articles.

Appuyant la suggestion de Lucene pour le texte intégral, mais notez que Java n’est pas une exigence; un port .NET est disponible . Voir également la page principale de Lucene pour des liens vers d’autres projets, y compris Lucy, un port C.

Peut-être que ce que vous recherchez est quelque chose qui paraphrase . Je n’ai qu’une connaissance superficielle de cela, mais la paraphrase est un concept de traitement du langage naturel pour déterminer si deux passages de texte signifient réellement la même chose – même si des mots peuvent être entièrement différents.

Malheureusement, je ne connais aucun outil qui vous permette de le faire (bien que cela m’intéresserait d’en trouver un)

Vous pouvez utiliser l’index de texte intégral SQL Server pour obtenir la comparaison intelligente, je crois que SO utilise un appel ajax, qui effectue une requête pour renvoyer les questions similaires.

Quelles technologies utilisez-vous?

Si vous cherchez des mots qui vous blessent, vous pouvez convertir en soundex et les mots soundex pour correspondre … travaillé pour moi

J’ai essayé une méthode, mais aucune ne fonctionne bien. On peut obtenir un résultat relativement satisfaisant comme celui-ci: Premièrement: obtenez un code Google SimHash pour chaque paragraphe de tout le texte et stockez-le dans la firebase database. Deuxièmement: Index du code SimHash. Troisièmement: traitez votre texte à comparer comme ci-dessus, obtenez un code SimHash et recherchez tout le texte par un index SimHash qui forme une distance de Hamming de 5 à 10. Comparez ensuite la simulation avec le terme vecteur. Cela peut fonctionner pour les données volumineuses.

Le lien dans la réponse de @ alex77 pointe vers le coefficient Sorensen-Dice qui a été découvert indépendamment par l’auteur de cet article – l’article est très bien écrit et mérite d’être lu.

J’ai fini par utiliser ce coefficient pour mes propres besoins. Cependant, le coefficient d’origine peut donner des résultats erronés

  • des paires de mots de trois lettres qui contiennent une faute d’orthographe, par exemple [and,amd] et
  • trois paires de mots qui sont des anagrammes, par exemple [and,dan]

Dans le premier cas, Dice signale à tort un coefficient de zéro, tandis que dans le second cas, le coefficient atteint 0,5, ce qui est trompeur.

Une amélioration a été suggérée qui consiste essentiellement à prendre le premier et le dernier caractère du mot et à créer un bigramme supplémentaire.

À mon avis, l’amélioration n’est vraiment nécessaire que pour les mots de 3 lettres – en d’autres termes, les autres bigrammes ont un effet tampon qui couvre le problème. Mon code qui implémente cette amélioration est donné ci-dessous.

 function wordPairCount(word) { var i,rslt = [],len = word.length - 1; for(i=0;i < len;i++) rslt.push(word.substr(i,2)); if (2 == len) rslt.push(word[0] + word[len]); return rslt; } function pairCount(arr) { var i,rslt = []; arr = arr.toLowerCase().split(' '); for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i])); return rslt; } function commonCount(a,b) { var t; if (b.length > a.length) t = b, b = a, a = t; t = a.filter(function (e){return b.indexOf(e) > -1;}); return t.length; } function myDice(a,b) { var bigrams = [], aPairs = pairCount(a), bPairs = pairCount(b); debugger; var isct = commonCount(aPairs,bPairs); return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); } $('#rslt1').text(myDice('WEB Applications','PHP Web Application')); $('#rslt2').text(myDice('And','Dan')); $('#rslt3').text(myDice('and','aMd')); $('#rslt4').text(myDice('abracadabra','abracabadra')); 
 *{font-family:arial;} table { width:80%; margin:auto; border:1px solid silver; } thead > tr > td { font-weight:bold; text-align:center; background-color:aqua; } 
  
Phrase 1 Phrase 2 Dice
WEB Applications PHP Web Application
And Dan
and aMd
abracadabra abracabadra

Étant donné un exemple de texte, ce programme répertorie les textes de référentiel classés par similarité: implémentation simple de sac de mots en C ++ . L’algorithme est linéaire dans la longueur totale de l’exemple de texte et des textes du référentiel. De plus, le programme est multi-thread pour traiter les textes de référentiel en parallèle.

Voici l’algorithme de base:

 class Statistics { std::unordered_map _counts; int64_t _totWords; void process(std::ssortingng& token); public: explicit Statistics(const std::ssortingng& text); double Dist(const Statistics& fellow) const; bool IsEmpty() const { return _totWords == 0; } }; namespace { const std::ssortingng gPunctStr = ".,;:!?"; const std::unordered_set gPunctSet(gPunctStr.begin(), gPunctStr.end()); } Statistics::Statistics(const std::ssortingng& text) { std::ssortingng lastToken; for (size_t i = 0; i < text.size(); i++) { int ch = static_cast(text[i]); if (!isspace(ch)) { lastToken.push_back(tolower(ch)); continue; } process(lastToken); } process(lastToken); } void Statistics::process(std::ssortingng& token) { do { if (token.size() == 0) { break; } if (gPunctSet.find(token.back()) != gPunctSet.end()) { token.pop_back(); } } while (false); if (token.size() != 0) { auto it = _counts.find(token); if (it == _counts.end()) { _counts.emplace(token, 1); } else { it->second++; } _totWords++; token.clear(); } } double Statistics::Dist(const Statistics& fellow) const { double sum = 0; for (const auto& wordInfo : _counts) { const std::ssortingng wordText = wordInfo.first; const double freq = double(wordInfo.second) / _totWords; auto it = fellow._counts.find(wordText); double fellowFreq; if (it == fellow._counts.end()) { fellowFreq = 0; } else { fellowFreq = double(it->second) / fellow._totWords; } const double d = freq - fellowFreq; sum += d * d; } return std::sqrt(sum); } 

Le moyen le plus simple et le plus rapide de comparer la similarité entre les résumés est probablement d’utiliser le concept d’ensemble. Convertissez d’abord les textes abstraits en un ensemble de mots. Ensuite, vérifiez combien chaque ensemble se chevauche. La fonction set de Python permet d’effectuer cette tâche très facilement. Vous seriez surpris de voir à quel point cette méthode se compare aux options «similaires / apparentées» proposées par GScholar, ADS, WOS ou Scopus.