Discussion :

[kha_yassine]

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


et merci d'avance

[pseudocode]

Comme l'intitulé du sujet l'indique, je cherche un algorithme de recherche approximative de chaine de caractère simple a comprendre et efficace

Quelle est ta définition de "recherche approximative" ?

Pour une chaine donnée, tu cherches toutes les chaines qui lui ressemblent phonétiquement ? textuellement ? autre ?

[kha_yassine]

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

[pseudocode]

Tu peux calculer la distance de Levenshtein (ou Damerau-Levenshtein) entre ta chaine et chaque sous-chaine (ou mot) de ton texte.

[kha_yassine]

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

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

[pseudocode]

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 ?

[kha_yassine]

voici un autre exemple :

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

La chaine a rechercher :

histoir es reci

Resultats :

"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...

Resultats de la distance de "Levenshtein" mot par mot, avec une distance maxi = 3:

"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 ??

rien qu'avec une distance de "Levenshtein" = 3, je suis mal barré !

J'espère que c'est plus claire maintenant

[pseudocode]

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.

[kha_yassine]

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

[kha_yassine]

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