Discussion :

[Avatar36]

Bonjour,
Je cherche à faire une fonction de recherche en c++ (avec ou sans Qt) permettant de trouver une suite de caractère ou une suite similaire. Un peu comme fait Google:si on tape un mot proche, il trouve quand même le bon résultat. C'est un peu ça que je veux faire. Avec peut être un did you mean fait maison avec les données de ma base de données. J'avais dans l'idée de faire une fonction qui compare deux chaînes en calculant le pourcentage de ressemblance, et gardant les résultat avec 90% de ressemblance par exemple. Mais je suis sur qu'on peut d'aire mieux. Est ce que vous pouvez me réorienter vers des algorithmes ou des tutos svp? Je n'ai rien trouvé de très parlant mis à part des informations générales, rien de technique.
Cordialement

[foetus]

Je te donne une [petite] piste: Distance de Levenshtein

Regardes les liens en bas, c'est un sujet vaste

[Avatar36]

Oui je me doute c'est pour ça que je pose la question ^^.
Merci je vais y jeter un oeil

[phi1981]

Une autre façon de voir les choses consiste à écrire une fonction de recherche la plus rapide possible, sans aucune notion de tolérance ou pourcentage de similarité. Par exemple en utilisant un hash des chaînes stockées dans ta base de recherche, ou un algorythme à la Boyer-Moore (si tu n'as pas de prétraitement).
Une fois que tu as cette fonction la plus rapide possible, alors ça veut dire qu'il est relativement peu couteux de générer toi même les variantes et utiliser ta fonction rapide pour savoir si cette variante existe. Dans certains cas ce sera même plus rapide que de calculer la distance entre ta chaine recherchée et les différents candidats.

L'avantage, c'est que tu peux alors générer des variantes plus intelligentes qu'une bête distance. Par exemple, tu peux générer les différentes flexions d'un verbe, ou utiliser une table de synonymes pour remplacer un des mots.

Suivant ton objectif, ça peut être une piste.

[Avatar36]

Pour le moment, le principe de la distance me suffit, le but étant que l'utilisateur cherche quelque chose de spécifique et entre un nom approximatif dans le champ de recherche (c'est pour des films). Mais effectivement je me pencherai sur cet algorithme qui fera très certainement partie d'une mise à jour que je ferai quand mon logiciel fera les fonctions principales.