Version imprimable
Salut a tous :)
Comme l'intitulé du sujet l'indique, je cherche un algorithme de recherche approximative de chaine de caractère simple a comprendre et efficace
J'ai beaucoup chercher sur Google , et j'ai trouver pas mal de cours ... mais c'est un peu difficile a comprendre quand même (et vu le temps que j'ai...)
Donc n'importe quel lien de cours facile a comprendre et le bien venu, aussi si cet algorithme est déjà implémenté dans un des langages de programmation
:ccool:
et merci d'avance
Quelle est ta définition de "recherche approximative" ?Citation:
Envoyé par kha_yassine
Pour une chaine donnée, tu cherches toutes les chaines qui lui ressemblent phonétiquement ? textuellement ? autre ?
Excusez moi pour le manque de détail que j'ai mis sur le post
voici un exemple :
Texte : "Algorithmes : Forum d'entraide sur l'algorithmique, l'intelligence artificielle, le traitement numérique d'images et les mathématiques"
chaine a rechercher : "Algoryt fique"
Les erreurs au niveau de la chaine sont fait exprès,
Les résultats de recherche :
- l'indice du mot "Algorithmes" = 1
- l'indice du mot "l'algorithmique" = ...
- l'indice du mot "numérique" = ...
- l'indice du mot "mathématiques" = ...
- l'indice d'autres mot ayant une distance d'édition faible...
Merci d'avance :)
Tu peux calculer la distance de Levenshtein (ou Damerau-Levenshtein) entre ta chaine et chaque sous-chaine (ou mot) de ton texte.
Merci pour ta réponse
Mais cette façon de faire ne va pas marcher, car le texte a traiter est très long, et aussi la chaine de caractère a rechercher peut être longue aussi :calim2:
Les premiers inconvénients que je vois :
1- Le temps de réponse serait énorme.
2- L'algorithme peut me retourner une chaine pas du tout conforme a se que je cherche avant celle que je cherche,
par exemple :
texte = "Algorithme Algérie"
La chaine a rechercher = "Algory"
Le résultat serait : "Algérie" avant "Algorithme"
Bien sur qu'il y a des algorithmes "Approximative String matching" connu aussi sous le nom "fuzzy text searching" qui utilisent la distance de 'Levenshtein' mais ils considèrent que la chaine a rechercher est tout un ensemble a rechercher
Tu peux nous donner un exemple réel de données que tu vas utiliser (chaine cherchée et texte), et du résultat attendu ?
:calim2:
voici un autre exemple :
La chaine a rechercher :Citation:
L'histoire est un récit, c'est la construction d'une image du passé par des hommes (les historiens) qui tentent de décrire, d'expliquer ou de faire revivre des temps révolus. Par delà les époques et les méthodes, et quel que soit le but sous-jacent du travail de l'historien, l'histoire est toujours une construction humaine, inscrite dans l'époque où elle est écrite. Comme le souligne l'historien Antoine Prost, « l'histoire, c'est ce que font les historiens ».
L'histoire est un récit, construit non par intuition intellectuelle, mais à partir de sources. Elle s'attache avec ces sources à reconstruire plusieurs pans du passé. Au cours des siècles, les historiens ont fortement fait évoluer leurs champs d'intervention et réévaluer leurs sources, ainsi que la manière de traiter ces sources.
Source:Wikipedia
Resultats :Citation:
histoir es reci
Resultats de la distance de "Levenshtein" mot par mot, avec une distance maxi = 3:Citation:
"L'histoire est un récit..." début du premier paragraphe
"L'histoire est un récit..." début du deuxième paragraphe
et si je donne une grande marge d'erreur, il va me retourner aussi :
"l'histoire est toujours..." du premier paragraphe
"l'histoire, c'est..." du premier paragraphe
peut être d'autres résultats encore...
rien qu'avec une distance de "Levenshtein" = 3, je suis mal barré !Citation:
"L'hisoire" début du premier paragraphe
"est"
"récit"
"ou" ;) la distance d'édition entre 'es' et 'ou' = 2 donc elle va être rendu comme résultat de recherche
"de" ... et tout les autres mots de deux caractères ou de 3 caractères qui inclus 'e' ou 's'
Je continu ??
J'espère que c'est plus claire maintenant :)
Ok.
Est-ce que la chaine a chercher est toujours dans ce genre là, a savoir qu'elle ressemble phonétiquement au texte cherché ?
Auquel cas, tu as des algos comme Soundex qui te permettent d'encoder tes chaines en phonétique. La recherche avec une distance de Levenshtein devient alors plus pertinente.
Phonétiquement, non pas tout a fait
J'ai vu l'algorithme SoundEx, et c'est pas vraiment se que je cherche, surtout que mon algorithme va être utilisé pour traiter "presque" toute les langues
Je te remercie en tout cas pour ton aide :)
Je continu toujours mes recherches ... c'est pas aussi facile que je pensais :cry:
:D
J'ai trouver ce document, qui a l'air d'être intéressant :
http://www.cs.unc.edu/~weiwang/paper/SSDBM04.pdf
Le BASS-TREE
Mais je trouve pas l'algorithme, même pas sur Google :aie: