Discussion :

[Skyba01]

Bonjour, je débute en Perl et j'aimerais utiliser une fonction qui renvoie le nombre de lettres différentes entre deux mots.

Par exemple :
dupont - dupond : renvoirait 1
lumiere - laniere : renvoirait 2
appeler - apeler : renvoirait 1

Vous m'avez compris
J'ai beau chercher sur internet, je n'ai pas trouvé.

Merci de votre aide!!

[Philou67430]

Un lettre absente compte comme une lettre différente ?

[Skyba01]

Idéalement, oui.
On peut aussi poser la question autrement : Combien il y a-t-il de caractères identiques dans le même ordre ? (En sautant quelques caractères, si nécéssaire).
Ou encore : quelle est le pourcentage de similarité entre deux chaînes ?

Ce sont 3 questions différentes, mais on peut arriver à la réponse de la 1ere en bidouillant un peu. IMPORTANT : Dans les deux chaines que je cherche à comparer, il peut y avoir des lettres, mais aussi d'autres caractères. Ils sont traités également.

Perl doit être capable de faire ca non ? ^^

Merci

[Philou67430]

Perl doit être capable de faire ca non ? ^^

Merci

Perl peut tout faire à qui s'en donne la peine

Je veux dire que votre question est plus d'ordre algorithmique que de programmation en perl.

Une idée de départ : ranger chaque occurrence de lettre dans un hash dont la clé est la lettre et la valeur son nombre d'occurrence.
De là, compter les écarts...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
use 5.10.0;
my (%mot1, %mot2);
$mot1{$_}++ foreach split //, $mot1;
$mot2{$_}++ foreach split //, $mot2;
my $distance = 0;
foreach my $car (keys %mot1, keys %mot2) {
  $distance += abs(($mot1{$car} // 0) - ($mot2{$car} // 0));
}
print "distance: ", $distance, "\n";

J'ai jeté l'algo "en live". Je ne sais ni s'il est correct, ni s'il compile ou s'exécute.

[Philou67430]

Le script précédent traite le 1 et le 2 de "mot1" et "mot2" comme étant deux différences (1 n'est pas dans mot2, et 2 n'est pas dans mot1).

[Philou67430]

Une meilleure approximation de la distance :
(int($distance/2)+($distance % 1))

Précision : l'algo précédent ne tient pas compte de l'ordre des caractères. S'il faut tenir compte de l'ordre, je ne vois alors qu'un algorithme linéaire qui parcoure en parallèle chaque caractère :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
my @mot1 = split //, $mot1;
my @mot2 = split //, $mot2;
my $distance = 0;
foreach my $car (@mot1) {
  $distance += $car ne (shift(@mot2) // "");
}
$distance += @mot2;
print "distance=", $distance, "\n,";

[Philou67430]

Cette dernière version me semble parfaite

[Skyba01]

Merci pour ta réponse Philou.
J'ai essayé d'éxécuter ton programme, mais il me dit (ayant auparavant défini mot1 et mot2) :
Use of uninitialized value in concatenation (.) or string at levenshtein.pl line 7.
Unmatched ) before HERE mark in regex m/ 0) << HERE - ( / at levenshtein.pl line 7.
Hmmm je ne sais que faire xD

Quelqu'un ma indiqué que le nombre que je cherchais s'appelle la distance de Levenshtein.
J'ai donc cherché un peu, et j'ai trouvé un script qui semble marcher :
http://www.mgilleland.com/ld/ldperl2.htm

C'est donc bon

Merci encore. Plus besoin de se casser la tête ^^
Bonne journée

EDIT : Tu avais posté ton nouveau programme avant même que j'avais fini ma réponse ^^. Il me semble bien, mais il me dit

Search pattern not terminated at levenshtein.pl line 10. (c'est la ligne de l'instruction dans la boucle foreach).
Si il arrive au même résultat que le programme que j'ai trouvé sur internet, chapeau ^^ car il est bcp plus court

[Philou67430]

Et voila, quand on sait de quoi l'on parle, il existe un module tout fait en perl : voir Text::Levenshtein

Cela dit, j'ai testé mes scripts, qui fonctionnent en perl 5.10 ; ton problème vient sans doute du fait que tu n'est qu'en 5.8.
Pour corriger, il faut remplacer les expressions du type $toto // 0 par (defined $toto ? $toto : 0)

[Philou67430]

Cela dit, je suis surpris de la complexité des deux algos Levenshtein à coté du mien... je serais intéressé par connaitre l'écart entre le mien et le Levenshtein (les quelques exemples que j'ai pris donnent pour l'instant des résultats identiques)...

[Philou67430]

Je crois en fait que mon algo se rapproche (ou est) la distance de Hamming, qui est un majorant de la distance de Levenshtein.