Comment comparer des expressions par similarité?

Question

Lors de la saisie d'une question, stackoverflow vous présente une liste de questions susceptibles, à son avis, de couvrir le même sujet. J'ai déjà vu des fonctionnalités similaires sur d'autres sites ou dans d'autres programmes (systèmes de fichiers d'aide, par exemple), mais je n'ai jamais programmé une telle opération. Maintenant, je suis curieux de savoir quel type d'algorithme on utiliserait pour cela.

La première approche qui me vient à l’esprit est de scinder la phrase en mots et de rechercher des phrases contenant ces mots. Avant de faire cela, vous voudrez probablement jeter des mots insignifiants (comme 'le', 'a', 'le' fait ', etc.), puis vous voudrez classer les résultats.

Hé, attendez - faisons cela pour les pages Web, puis nous pourrons avoir un ... watchamacall ... - un "moteur de recherche", puis nous pourrons vendre des publicités, puis ...

Non, sérieusement, quels sont les moyens habituels de résoudre ce problème?

Answer 1

Une approche est le modèle dit du sac à mots.

Comme vous l'avez deviné, vous comptez tout d'abord le nombre de fois que des mots apparaissent dans le texte (généralement appelé document dans le langage PNL). Ensuite, vous jetez les soi-disant mots vides, tels que "le", "un", "ou" et ainsi de suite.

Il ne vous reste plus que des mots et un nombre de mots. Faites cela pendant un moment et vous obtenez un ensemble complet de mots qui apparaissent dans vos documents. Vous pouvez ensuite créer un index pour ces mots: " aardvark & ??quot; est 1, "pomme" est 2, ..., " z-index " est 70092.

Maintenant, vous pouvez prendre vos sacs de mots et les transformer en vecteurs. Par exemple, si votre document contient deux références pour aardvarks et rien d’autre, il ressemblera à ceci:

[2 0 0 ... 70k zeroes ... 0].

Ensuite, vous pouvez compter l’angle " angle " entre les deux vecteurs avec un produit scalaire . Plus l'angle est petit, plus les documents sont proches.

Ceci est une version simple et d'autres techniques plus avancées. Que la Wikipedia soit avec vous .

Answer 2

@Hanno, vous devriez essayer l'algorithme de distance de Levenshtein. Avec une chaîne d'entrée s et une liste de chaînes t , effectuez une itération pour chaque chaîne u dans t et renvoyez le une avec la distance minimale de Levenshtein.

http://en.wikipedia.org/wiki/Levenshtein_distance

Voir un exemple d'implémentation Java dans http://www.javalobby.org/java /forums/t15908.html

Answer 3

Pour augmenter l’idée du sac de mots:

Il y a plusieurs façons de prêter attention aux n-grammes, des chaînes de deux mots ou plus maintenues en ordre. Vous voudrez peut-être faire cela parce qu'une recherche sur la "complexité de l'espace" est beaucoup plus qu'une recherche d'objets avec "espace" ET "complexité" en eux, puisque le sens de cette phrase est plus que la somme de ses parties; Autrement dit, si vous obtenez un résultat qui parle de la complexité de l'espace et de l'univers, ce n'est probablement pas ce que recherche "la complexité de l'espace". vraiment signifié.

Une des idées clés du traitement du langage naturel ici est celle de la informations mutuelles , qui vous permet (par algorithme) pour déterminer si une phrase est vraiment une phrase spécifique (telle que "complexité de l'espace") ou simplement des mots qui sont adjacents par coïncidence. Mathématiquement, l'idée principale est de demander, de manière probabiliste, si ces mots apparaissent les uns à côté des autres plus souvent que vous ne l'imagineriez par leur seule fréquence. Si vous voyez une phrase avec un score d’information mutuelle élevé dans votre requête de recherche (ou lors de l’indexation), vous pouvez obtenir de meilleurs résultats en essayant de conserver ces mots dans l’ordre.

Answer 4

D'après ma (plutôt petite) expérience de développement de moteurs de recherche en texte intégral: je rechercherais des questions contenant des mots issus d'une requête (dans votre cas, la requête est votre question). Bien sûr, les mots parasites devraient être ignorés et nous pourrions vérifier la requête pour rechercher des mots «forts» tels que «ASP.Net» afin de limiter la portée de la recherche. http://fr.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Les index inversés sont couramment utilisés pour trouver des questions avec des mots qui nous intéressent.

Après avoir trouvé des questions avec des mots à partir d'une requête, nous pourrions vouloir calculer la distance entre les mots qui nous intéressent. Par conséquent, si vous interrogez avec le texte "similarité des expressions", vous obtiendrez un classement plus élevé que celui avec "discussion sur la similarité". 'text.