Newsgroup: it.comp.lang.perl
Titolo: Similitudine di due stringhe

Buonasera a tutti,
mi domandavo se esistesse un qualche cosa in grado di definire la
similitudine di due stringhe.
Traduco: date le stringhe testuali $a e $b come posso sapere che grado
di similitudine esiste fra le due ?
Un ringraziamento anticipato e un saluto.
-- 
Dario Centofanti
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 di similitudine esiste fra le due ?
Ciao,
  magari dovresti chiarire cosa intendi per 'similitudine' di due
stringhe... Il termine č un attimino ambiguo. 
-- 
Leo TheHobbit  | It snow food and rain drink. |
IRCnet #roma2  |         Hobbit saying        |
ICQ 56656060   |                              |  a.d. IX Kal. Mai. MMDCCLV AUC

 di similitudine esiste fra le due ?
La tua domanda ingenera in me ulteriori inquietanti domande per le quali 
non ho, attualmente, risposte, quali: "Cos'e` una similitudine tra 
stringhe"? Il CPAN fornisce alcuni moduli apparentemente correlati alla 
tua domanda, come, per esempio, Text::Soundex. HTH!
-- 
Baci,
Mony

 "Cos'e` una similitudine tra stringhe"? 
Ottima domanda... a cui purtroppo non ho una valida risposta...
cerchero' comunque di cavarmela con un esempio:
Soundex lavora per 'similitudine' fonetica in lingua inglese mentre io
sarei alla ricerca di una 'similitudine' indipendente dalla pronuncia
del testo... un qualche cosa che mi dica che "dario" e "mario" sono
simili ad esempio all' 80% mentre "paolo" e "marco" lo sono al 20% 
Lo scopo finale e' scovare all'interno di un elenco di nomi, cognomi ed
email alcune entry che possano contenere dati molto simili anche se non
identici.
Un saluto


 Un saluto
 
Salve,
 ti puoi basare sulla distanza di Hamming, che è il numero di caratteri
differenti in due stringhe.
Il modulo che segue la calcola.
---cut here---------
package Hamming;
use strict;
use Exporter;
use vars qw($VERSION @ISA @EXPORT @EXPORT_OK);
$VERSION = "1.01";
@ISA = qw(Exporter);
@EXPORT = ();
@EXPORT_OK = qw(distance);
sub distance {
  my ($x,$y) = @_;
  my $result = abs (length($x) - length($y));
  my $len = (length($x) < length($y)) ? length($x) : length($y);
  $x = substr($x,0,$len);
  $y = substr($y,0,$len);
  foreach my $i (0..$len-1) {
    $result++ if substr($x,$i,1) ne substr($y,$i,1);
  }
  return $result;
}
__END__
=head1 NAME
Hamming - Implements Hamming distance
=head1 SYNOPSIS
   use Hamming qw(distance);
   print distance("abcxtaz","axczt");
   # prints 4
=head1 DESCRIPTION
The Hamming distace of two strings is defined as the number of
caracters differents in the two strings. 
=head1 AUTHOR
Leo Cacciari aka TheHobbit, E<lt>theh...@altern.orgE<gt>
=head1 COPYRIGHT
Copyright (c) 2002 Leo Cacciari. All rights reserved.  This program is
free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
=cut
 
-- 
Leo TheHobbit |  One Ring to rule them all.   |
IRCnet #roma2 |      One Ring to find them,   |
ICQ 56656060  |  One Ring to bring them all   |
              |  and in the darkness bind them|
              |     In the Land of Mordor     |
              |      where the Shadows lie.   |  a.d. IX Kal. Mai. MMDCCLV AUC

 simili ad esempio all' 80% mentre "paolo" e "marco" lo sono al 20% 
Se e` una mera conta di caratteri uguali, potrebbe bastare creare due 
array associativi che contengano i caratteri (senza o con) ripetizioni 
che costituiscono le due stringhe e poi assegnare un peso al fatto che i 
  due array abbiano elementi simili. Qualcosa del genere:
<code>
	# no repeats
	$w=0;
	map { $hstr1{$_}=1 } split //,$str1;
	map { $hstr2{$_}=1 } split //,$str2;
	foreach $key (keys %hstr1) { $w++ if defined $hstr2{$key} }
</code>
ovviamente ottimizzabile. Altrimenti potresti cercare la piu` corta 
sottostringa dell'una stringa data che sia presente nell'altra stringa 
data. In questo caso, e` troppo tardi perche` possa scriverti un esempio 
decente. ;)
-- 
Baci,
Mony

 </code>
Non son d'accordo... :) da quello che dice il post originale, tenderei a
dire che sole e leso sono diversi al 50%, mentre con il tuo calcolo sono
identiche.
Ciao
-- 
Leo TheHobbit |It feels so good, It's a marginal risk, |
IRCnet #roma2 |   when I clear off windows with fdisk  |
ICQ 56656060  |                                        |a.d. IX Kal. Mai. MMDCCLV AUC

 dire che sole e leso sono diversi al 50%, 
100% ovviamente.....
 
-- 
Leo TheHobbit |  I am the "ILOVEGNU" signature virus.  |
IRCnet #roma2 |     Just copy me to your signature.    |
ICQ 56656060  |This email was infected under the terms |
              |   of the GNU General Public License.   |a.d. IX Kal. Mai. MMDCCLV AUC

 identiche.
Se "paolo" e "marco" sono simili al venti per cento, allora "sole" e 
"leso" sono identiche. Comunque, sono d'accordo che non sia la mia la 
soluzione al problema, specialmente se questo e` riconoscere indirizzi 
di posta elettronica potenzialmente della stessa persona.
-- 
Baci,
Mony

Mony Vibescu scripsit:

Salve,
paolo a marco sono simili al 40% (e non al 20%) perché hanno 2 caratteri uguali e
nella stessa posizione su 5 (la a in seconda pos. e la o alla fine). La
similitudine può essere definita (per due stringhe di stessa lunghezza)
da
use Hamming; #vedi mio post precedente
sub similitudine {
  my ($a,$b) = @_;
  return undef unless length($a) == length($b);
  return (length ($a) - Hamming::distance($a,$b)) / length($a);
}
Questo è conforme con l'altro esempio del post
d63004b95822a8bf7...@mygate.mailgate.org
 secondo cui dario
e mario sono simili all'80%
A presto
-- 
Leo TheHobbit | in a world without fences,  |
IRCnet #roma2 |who needs Windows and Gates? |
ICQ 56656060  |                             |  a.d. VIII Kal. Mai. MMDCCLV AUC

 paolo a marco sono simili al 40% (e non al 20%) 
Nell'esempio di Dario sono uguali al venti per cento.
-- 
Baci,
Mony

 Nell'esempio di Dario sono uguali al venti per cento.
 
Lo so, ma qualcuno mi deve allora spiegare secondo quale definizione di
'simili' paolo e marco sono simili al 20% e dario e mario all'80%.... Io
personalmente non riesco a trovarla:)))
Ciao
-- 
Leo TheHobbit |  One Ring to rule them all.   |
IRCnet #roma2 |      One Ring to find them,   |
ICQ 56656060  |  One Ring to bring them all   |
              |  and in the darkness bind them|
              |     In the Land of Mordor     |
              |      where the Shadows lie.   |a.d. VIII Kal. Mai. MMDCCLV AUC

 personalmente non riesco a trovarla:)))
Non posso certo essere io a dirlo. Per me hanno due caratteri in comune 
(tre su cinque per "paolo" e due su cinque per "marco") oppure due 
caratteri uguali alla stessa posizione (la "a" e la seconda "o"). 
Parlare di percentuali e` comunque reso possibile solo dal caso 
particolare che le due stringhe abbiano la stessa lunghezza, e gia` 
cosi`, nel primo caso, dire "venti per cento" o "quaranta per cento" e` 
una forzatura (quaranta per cento di cosa?).
Secondo me, il metodo migliore di "pesare" la similitudine tra due 
stringhe, nel caso presentato da Dario, e` misurare la lunghezza della 
piu` lunga sottostringa presente in entrambe. Egli, infatti, necessita 
di trovare "all'interno di un elenco di nomi, cognomi ed email alcune 
entry che possano contenere dati molto simili anche se non identici" e 
cioe`, cose del genere:
 
mvib...@yahoo.com
       # reference string, length=18
 
m.vi...@yahoo.com
      # 17/18 (
vib...@yahoo.com
)
 
mvib...@yahoo.it
        # 15/18 (mvibescu@yahoo)
	mvib...@NOSPAMyahoo.com # 9/18  (mvibescu || 
yahoo.com
)
 
mony.v...@yahoo.com
   # 17/18 (
vib...@yahoo.com
)
Il che, come vedi, non e` elementare e la prima idea che mi viene in 
mente e` una pessima doppia iterazione di binding tra la stringa in 
ingresso e quella data intesa come RE, diminuendo man mano i caratteri 
considerati di quest'ultima, una volta a partire dal primo ed una a 
partire dal secondo. Orripilante.
Ma prometto che un po' di tempo glielo dedico, in giornata, per lo meno 
a navigare il CPAN alla ricerca di qualcosa di simile... ;)
-- 
Baci,
Mony

 grado di similitudine esiste fra le due ?
un altra possibilità, rispetto a quelle già date, è di andare su
search.cpan.org
 e cercare String::Approx.
il modulo usa l'algoritmo di Levenshtein e dà la 'edit distance'
tra due stringhe. maggiori info nella documentazione del modulo.
cheers,
Aldo
__END__
$_=q,just perl,,s, , another ,,s,$, hacker,,print;

 cioe`, cose del genere:
Salve,
 la più lunga sottostringa comune è facile da trovare.... Se $a e $b
contengono le stringhe e se sei sicuro che il carattere '%' non appare
nelle stringhe (rimpiazzare % con un qualsiasi carattere per cui ciò sia
vero) allora la più lunga sottostringa comune si ha con
$_ = $a."%".$b;
my @tmp = /(.+).*%.*\1/;
return $tmp[0];
Saluti


 return $tmp[0];
Stupendo. :)
-- 
Baci,
Mony

 Stupendo. :)
 
Peccato che mi sono sbagliato :)))) Non funziona :(((
La funzione seguente invece si
sub longest_common_substring {
  my ($first,$second) = @_;
 
  #strings do not contains \n...
  my $tmp = $first . "\n" . $second;
  my $len = 1;
  my $string = "";
  while ($tmp =~ /(.{$len}).*\n.*\1/) {
    $len++;
    $string = $1;
  }
  $len--;
 
  #returns a reference to an hash containing informations
  #about the longest substring.
  return {length => $len, string => $string};
}
Le regexp di Perl a volte sono troppo voraci :-/
Ciao
-- 
Leo TheHobbit |It snow food and rain drink. |
IRCnet #roma2 |        Hobbit saying        |
ICQ 56656060  |                             |  a.d. VIII Kal. Mai. MMDCCLV AUC

 
search.cpan.org
 e cercare String::Approx.
Colgo l'occasione di questo ultimo messaggio di Aldo per ringraziare
di tutte le possibili soluzioni proposte anche Mony Vibescu e Frodo
Baggins.
String::Approx sembra fornire una buona soluzione al mio problema (e
dalla documentazione vedo che e' stata realizzata con la collaborazione
dello stesso Aldo).
Grazie di nuovo,
Un saluto
