Calcul de la distance de Hamming
sebsauvage
Messages postés
32893
Date d'inscription
Statut
Modérateur
Dernière intervention
-
helene -
helene -
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.
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.
A voir également:
- Calcul de la distance de Hamming
- Allumer pc à distance - Guide
- Calcul moyenne excel - Guide
- Calcul km marche à pied gratuit - Télécharger - Sport
- Calcul charpente bois gratuit - Télécharger - Architecture & Déco
- Logiciel gratuit calcul valeur nutritionnelle - Télécharger - Santé & Bien-être
5 réponses
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 <ital>diff</i> 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
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 <ital>diff</i> 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
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.
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.
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 ^^'
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question