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 ?