Rédaction d'un algorithme de post-recherche

Question

J'essaie d'écrire un algorithme de recherche de texte libre pour trouver des messages spécifiques sur un mur (un type de mur similaire à celui utilisé par Facebook). Un utilisateur est supposé être capable d'écrire des mots dans un champ de recherche et d'obtenir des résultats positifs sur les messages qui contiennent les mots; avec le meilleur match en haut puis les autres posts en ordre décroissant en fonction du score du match. J'utilise la distance d'édition (Levenshtein) "e (x, y) = e" pour calculer le score de chaque publication par rapport au mot de requête "x" et au mot "y" après: (x, y) = 2^(2 - e) (1 - min (e, | x |)/| x |), où "| x |" est le nombre de lettres dans le mot de requête.

Chaque mot dans un article contribue au score total pour ce poste spécifique. Cette approche semble bien fonctionner lorsque les messages ont à peu près la même taille, mais parfois certains grands messages réussissent à accumuler des points uniquement en ayant beaucoup de mots en eux alors qu'en pratique, ils ne sont pas pertinents pour la requête. Est-ce que j'aborde ce problème de la mauvaise façon ou est-ce qu'il y a un moyen de normaliser le score auquel je n'ai pas pensé?

Answer 1

Oui. Il existe de nombreuses méthodes de normalisation que vous pourriez utiliser. C'est un domaine bien documenté!

Jetez un oeil à the vector space model. TDF/IDF pourrait être pertinent pour ce que vous faites. Ce n'est pas strictement lié à la méthode que vous utilisez mais cela pourrait vous donner des pistes de normalisation. Notez également que la comparaison de chaque message sera O (N) et pourrait devenir très lent. Au lieu de chaîne-distance, vous pouvez avoir de meilleurs résultats avec stemmming. Vous pouvez ensuite mettre cela dans un index VSM inversé.

De nombreuses bases de données (y compris MySQL et Postgres) ont une recherche en texte intégral. C'est probablement plus pratique que de le faire vous-même.