Calcul de la distance de Hamming Fermé

Question

Hello !

Je cherche un algo pour calculer la distance de Hamming (distance entre 2 mots, pratique pour trouver les mots "proches".)


Il y a 4 cas:

manger
menger
1 lettre différente -->  +1

manger
magner
2 lettre interverties ---> +1

manger
mnger 
manque 1 lettre ----> +1

manger
maniger
1 lettre en plus ----> +1


Mon soucis, c'est que tous les algos de Hamming que j'ai trouvé ne gère que le premier cas.
Je cherche un algo qui gèrerait les 4 cas.

Est-ce que quelqu'un aurait une adresse ?


Merci.

Reivax962 · Answer

Petite question : l'interversion ne doit-elle concerner que des lettres consécutives ? Quelle serait la distance de Hamming de "manger" et "ganmer" ? 1 pour une inversion, 2 pour deux lettres changées ? Voire 3 pour une inversion à une distance de 3 ? Je pense que si c'est "2 pour deux lettres changées", on peut inclure un test simple dans un algorithme linéaire, mais sinon, on risque de devoir exécuter plusieurs algorithmes, pour gérer chaque cas... Par exemple : 1 - algo qui calcule le solde au sens 1 2 - algo qui recherche les interversions, et qui enlève 1 pour chacune (et non pas qui rajoute ! Car une interversion a déjà été comptée deux fois dans le premier algo) 3 - ça, sincèrement, ça me parait compliqué à mettre en place ! Il faudrait voir ce qui est utilisé dans les algorithmes de diff qui sont notamment intégrés aux outils de travail collaboratif (subversion, cvs...) Dans tous les cas, c'est à intégrer au 1er algorithme, sinon la distance explosera et il sera compliqué de la corriger. 4 - idem

sebsauvage · Answer

l'interversion ne doit-elle concerner que des lettres consécutives ? 

En principe oui.

Mais on devrait pouvoir calculer plusiers interversion consécutives:

manger
mganer
le g est décalé 2 fois vers la gauche ---> +2


on risque de devoir exécuter plusieurs algorithmes, pour gérer chaque cas... 

C'est un peu ça qui m'inquiète, avec l'explosion combinatoire.

Reivax962 · Answer

Le problème, c'est qu'arrivé à un certain niveau, j'ai peur qu'on se retrouve avec plusieurs distances pour deux chaines de caractères, puisque une modification peut-être obtenue par diverses combinaisons des différents critères... J'imagine que dans ce cas, on prend le min des distances... J'espère que tu ne veux pas calculer la distance de Hamming de deux romans, parce que là, ce serait vraiment ingérable à moins d'avoir un Cray à ta disposition ^^'

sebsauvage · Answer

J'espère que tu ne veux pas calculer la distance de Hamming de deux romans

:-)

Non, heureusement.

helene · Answer

peut etre tu peux esseyer utiliser l'algorithme Wagner et Fischer.

Calcul de la distance de Hamming

5 réponses

Discussions similaires