Bonjour

Je reviens de vacances, et comme j'avais de la route, j'ai pensé à prendre un livre à la BU (Bibliothèque Universitaire) histoire de m'occuper. Je pensais naïvement que la mention 2ième et 3ième cycle universitaire signifiait licence 2ième et 3ième année, mais non, c'est juste master et doctorat. Honte sur moi. Je rentre en licence 2ième année, un sacré décallage. Mais ça ne m'a pas arrêté. Je me suis quand même attaquer au livre.

Il est carrément intéressant, même si un peu dur tout de même. Il traite de l'Algorithmique du Texte. Et ça m'a donné pleins d'idées pour ne rien vous cacher .

J'aimerais ici qu'on réfléchisse sur différentes façons d'améliorer un moteur de recherches interne à un site. Pour pouvoir s'exprimer plus facilement, on va utiliser des notations formelles. On va utiliser 2 notations simples pour l'instant : X serait le motif, et y serait le mot qui contient l'information qu'on recherche.

Bien. Commençons. Quand on veut faire un moteur de recherches, on utilise le plus souvent la commande LIKE d'SQL. Mais cette commande est beaucoup trop restrictive. Même si l'utilisation du symbole % permet de rechercher un occurence dans une autre, ce n'est pas encore le top. On pourrait alors utiliser des expressions régulières sur toutes les données de la table. Mais là encore, les expressions régulières ne seraient pas assez puissante.

Un moteur de recherches doit pouvoir permettre de chercher X dans y si :

• X est un mot de y ;
  X se trouve dans un mot de y ;
  X s'approche d'un mot de y.

On en vient à mon problème. J'aimerais savoir comment vous, vous procéderiez pour faire une localisation de motifs approchés dans un texte. J'ai ma petite idée sur le sujet, mais je ne veux ni vous influencer, ni orienter le débat. Je préfère voir vos réactions, elles seraient peut être mieux que les miennes.

Enfin, j'aimerais savoir qu'est-ce qu'il faudrait dans un bon moteur de recherches interne au site ? Est-ce qu'on en aurait réellement besoin ? Etc etc.

Bonjour,
je ne l'utilise pas, car je n'ai aps eu à le faire, mais je croit que certain utilise cette fonction de mysql:
http://dev.mysql.com/doc/refman/4.1/en/ ... on_soundex
Après, je ne sais pas exactement comment c'est implémenté...
hop un petit lien: http://sqlpro.developpez.com/cours/soundex/

Hmm très intéressant. Merci beaucoup pour ce lien.
Une autre idée ?

Avant toute chose, plutôt que de créer son propre moteur de recherche, je ne saurais trop recommander d'utiliser celui de MySQL ou mieux encore Sphinx qui est très très puissant et dans une certaine mesure intégrable à MySQL (tout ça nécessite d'avoir un accès shell à son serveur, pas de mutualisé).

Pour en revenir au sujet, même si ma connaissance en algorithmie de texte est très limitée (lire "quasi-inexistante") je suis certain d'une chose : tu ne pourras rien implémenter de tout cela en PHP pour des raisons de performances. Les structures de données requises ne se marrient pas vraiment avec ce que propose PHP ou SQL, et tu te retrouveras à devoir choisir entre un code plein de hacks (= difficile à maintenir) avec des performances médiocres, ou un code clean avec des performances désastreuses. Je ne cherche pas à te convaincre d'arrêter tes recherches, mais je te recommande fortement de ne pas trop t'investir non plus.

Oups, j'allais me lancer dans un truc plus long quand je me suis aperçu que je n'allais peut-être pas parler de la même chose, quand tu dis "X est un mot de y", X est un mot, mais y c'est quoi ?

Ah au fait, je n'arrive plus à mettre la main sur la page précise, mais si tu t'aventures du côté de http://labs.google.com tu devrais trouver pas mal de trucs. Notamment, Google proposait une grosse collection de mots les plus couramment mal-orthographiés.

Hey

Merci pour tes conseils. Je me doute bien que les performances de PHP sont lamentables. Et c'est pourquoi je pensais à autre chose. Si on faisait le script en Perl, ce serait sûrement plus rapide non ? Pourrait-on alors, lancer ce script dans PHP, et transférer des données de Perl à PHP. C'était une piste à laquelle j'avais penser.

Pour répondre à ta question, y est également un mot (comme il peut être un groupe de mot, si on ne considère pas l'espace comme un caractère qui sépare les mots). Mes connaissances en algorithmique du texte sont toutes récentes et donc pauvres également. C'est juste qu'en lisant ce livre, ça m'a donné pas mal d'idées, et je trouve ça dommage de ne pas en profiter ^^.

Sur Google, j'ai trouvé ceci : http://research.google.com/pubs/papers.html#category1. Ca pourrait sûrement être utile, mais j'ai pas le temps de lire tous ces livres proposés ^^. Je vais donc me tourner du côté de Sphinx, voir un peu ce qu'ils ont fait . Merci pour le lien.

J'attends d'autres avis.

y est également un mot (comme il peut être un groupe de mot, si on ne considère pas l'espace comme un caractère qui sépare les mots)

Ah, ben dans ce cas tu peux rechercher "bigram" ou "n-gram", et je ne sais pas comment les détecter/représenter.

Pour Perl vs PHP, je doute que Perl soit suffisamment rapide, c'est plutôt dans le C qu'il faudrait taper...

Si tu veux que je te fasse un 'tit cours d'algorithmique de texte, je peux, mais je ne le ferai pas sur le forum. Je prépare un petit PDF en LaTeX qui explique 2 ou 3 choses en ce moment. C'est juste pour ma mémoire, rien de formelle.

Muè, bon, ok, en PHP, on ne pourra jamais faire de recherches correctement donc ? Sauf si on passe par un programme intermédiaire comme Sphinx (pas mal du tout, j'ai commencé à regarder les codes hier soir).

En passant par la racinification (stemming) on obtient de très bon résultats. Je retrouverai ça au boulot j'en ai complété un existant qui m'a donné assez bonne satisfaction.

Pour rappel, la recherche par racine consiste en deux parties :
1. L'indexation. On prend la racine de chaque mot d'un texte, et en base on stocke un triplet (document, racine, nombre d'occurrences) pour chacune d'elle.
2. La recherche. On prend la racine de chaque mot de la recherche, et on fait une recherche sur cette racine, en considérant le nombre d'occurrences par document comme un indicateur de conformité à la recherche.

Exemple : si je cherche "archéologue", je trouverai aussi bien un texte intitulé "archéologie" quand bien même le mot exact d'"archéologue" ne figurerait nulle part.
Autre avantage, les analphabète pourront chercher archéologien ça marchera aussi

Ouais problème, comment tu détermines la racine du mot, si ce n'est avec un dictionnaire très exhaustif ?

Très simplement, selon la langue, en supprimant les "e" à la fin, les "ist", les "ogu", etc… Toute une liste de règles consistant à dire "si mot finit par XXX ou commence par YYY alors remplacer par ZZZ", certaines règles étant "finales" (dès qu'on applique cette règle, on n'en applique pas d'autre).

Pour le stemming, la référence du genre s'appelle Snowball. Tu verras sur leur site, toutes les règles sont clairement* expliquées. Attention, le stemming augmente le recall au prix de la pertinence, à vous de voir ce qui vous intéresse le plus... J'imagine que sur un site marchand on voudra avoir un super recall pour proposer le plus de produits/services pouvant correspondre, alors que sur un site de news (ou toute autre grosse banque de données), on voudra les résultats les plus pertinents.

Si tu veux que je te fasse un 'tit cours d'algorithmique de texte, je peux

C'est sympa, mais ma connaissance actuelle me suffit : j'en sais juste assez pour savoir que c'est un boulot à plein temps pour être vraiment bon



* clairement, pour un ordinateur. Pour un humain, ça dépend un peu plus

Bah en pondérant les résultats par le nombre d'occurrences, on arrive à des résultats assez satisfaisants. J'entends bien *assez satisfaisant* *pour un système facile à mettre en place et à comprendre*.

Les algos plus puissants sont tellement lourds et complexes, qu'ils sont hors de propos en général pour nos applications.

Hmm c'est très intéressant. J'en apprends beaucoup, merci.

Je lirais tous les liens demain matin, jsuis trop naze ce soir. En revanche, en algorithmique du texte, on est censé pouvoir détecter un suffixe, un préfixe, des bords, des périodicités etc. Ca pourrait peut-être être utile. On est également censé savoir faire une recherche par motifs approchés. Je l'ai testé sur papier sur mes genoux à la frontière Finlandaise, ça marchait .

Le soucis qu'on a avec les motifs approchés, c'est qu'on doit travailler sur les données de la base lors de la recherche. SQL ne sait pas faire ça, c'est bien dommage. Mais peut être quand faisant un bon algo, on pourrait espérer le mettre en oeuvre. Je ferai un petit test demain, et je vous soumettrais l'algo avec les explications (si j'ai le temps, sinon ce sera dans quelques jours).

Bonne nuit à tous et merci pour vos infos' .

La vous parlez qu'en Français en plus.
Si faut changer l'algo pour chaque langue, pas sorti de l'auberge.

La vous parlez qu'en Français en plus.
Si faut changer l'algo pour chaque langue, pas sorti de l'auberge.

Pas forcément, après on peut utiliser une couche d'abstraction qui permettra d'obtenir des résultats différends sans pour autant avoir a refaire tout l'algo.
C'est sur qu'après, pour les langues a déclinaison comme l'allemand, ca risque d'être comique