• Publicidad

Saber la similaridad en cadenas de textos

¿Apenas comienzas con Perl? En este foro podrás encontrar y hacer preguntas básicas de Perl con respuestas aptas a tu nivel.

Saber la similaridad en cadenas de textos

Notapor preiddy » 2007-07-24 08:14 @384

Hola nuevamente, estoy tratando de hacer un paquete que tome una cadena de texto/numérica, cuente cuántas veces se repite y luego se compare con el resto de cadenas a ver en cuanto por ciento se parecen, o no.

La primera parte, el conteo, lo sé hacer: creo un hash con clave y frecuencia y voy añadiendo valores. Él mismo está ordenado de mayor a menor por frecuencia de aparición.

Mi problema surge cuando una vez tengo ese hash, no sé cómo hacer para que el segundo se compare con el primero y me diga cuánto se parecen y así hasta n comparaciones, siempre el de abajo con todos los de arriba.

ejemplo:
    pentium comp dell 25
    comp dell pentium 10
    pentium comp ibm 12
    ibm pentium comp 22
Lo ideal sería tener una lista final que fuera así:
    pentium comp dell 25 = comp dell pentium 10 | 100%
    pentium comp ibm 12 = ibm pentium comp 22 | 100%
    pentium comp dell 25 = pentium comp ibm 12 | 80%
    pentium comp dell 25 = ibm pentium comp 22 | 80%
y así hasta el final del hash.

He probado con ngramas pero no lo consigo. El hecho de contar con la frecuencia es bueno porque se puede usar para luego cambiar una forma por la otra, si pentium comp dell aparece 25 veces y comp dell pentium aparece 10 y entre ambas hay un 100% de similaridad me quedo con la de mayor frecuencia.

Espero que puedan darme una manito y gracias.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Publicidad

Notapor monoswim » 2007-07-24 09:02 @418

¿Por qué las últimas 2 tienen un 80% de similitud? tienen 2 palabras de 3, sería un 66%, o no estoy entendiendo bien esa parte...

¿Quieres comparar cada palabra de un array en el otro?

Saludos
MonoSwim
Perl Programming Language
Avatar de Usuario
monoswim
Perlero nuevo
Perlero nuevo
 
Mensajes: 452
Registrado: 2003-11-18 16:13 @717
Ubicación: Buenos Aires

Notapor kidd » 2007-07-24 09:26 @434

Hola:

En perlmonks.org hay un par de ejemplos que te muestran como puedes encontrar la unión, intersección y diferencia de dos arrays:
http://perlmonks.org/?node_id=2461

También te recomiendo checar el módulo List::Compare.

Saludos
Uriel Lizama Perl programmer fundador de Perl en Español
Perl Programming Language
Avatar de Usuario
kidd
Creador de Perl en Español
Creador de Perl en Español
 
Mensajes: 1166
Registrado: 2003-10-15 16:52 @744
Ubicación: México

Notapor preiddy » 2007-07-24 13:00 @584

EL tanto por ciento lo puse a ojo, pero sí sería como un 0.66 la similaridad y uno en vez de 100.
Me leeré los ejemplos que sugiere Kidd y luego les comentaré.
Muchas Gracias.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Notapor explorer » 2007-07-25 04:05 @212

Depende un poco de cómo sean las frases a comparar.

Si están compuestos de palabras sueltas, como en el ejemplo, bastaría con hacer un bucle de comparación de ellas por las de una frase en una expresión regular hecha con or ('|') y ver cuántas coincidencias aparecen (una línea Perl). Eso se relaciona con el número total de palabras de la frase, y listo.

El problema es si las palabras no son exactamente iguales. Por ejemplo, cuando se comparan nombres propios, puede haber variaciones en la interpretación de como escribirlos o abreviarlos. Una María Antonia De La Fuente puede aparecer de 6 formas distintas (o más). Para estos casos usamos algoritmos de comparación de textos, como el Text::WagnerFischer y el Text::Metaphone. También probamos en el pasado el String::Approx y el Text::Soundex, pero con los primeros bastó.

Entonces la pregunta es cómo son las frases a comparar. Si son como en el ejemplo, de palabras sueltas, o es algo más complicado.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14482
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Notapor preiddy » 2007-07-25 14:04 @627

Más que frases son líneas de direcciones las que pretendo comparar.

La parte conceptual creo que la tengo clara, jajjaa. :D

El proceso se inicia identificando el país de la dirección, aunque muchas no tienen país. Una vez identificado el país se quiere agrupar las mismas direcciones escritas de maneras diferentes (en su mayoría por errores de transcripción) en una sola.

Por ejemplo:
[listyq]UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
UCV, FAC CIENCIAS,CTR BIOL CELULAR.[/list:uyq]
No sé si con esto aclaro más lo que estoy tratando de hacer.

Estoy leyendo las sugerencias de kidd y explorer, pero de momento no creo que sea lo que busco.

Muchas Gracias, :lol:
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Notapor kidd » 2007-07-25 17:22 @765

Me parece bastante interesante el ejercicio y aquí va un primer intento. Con el script se comparan cada una de las frases y se saca el porcentaje de aproximación de una a otra:

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
#!/usr/bin/perl -w

use strict;

my @lineas = (
              'UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.',
              'LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.',
              'CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.',
              'UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.',
              'UCV, FAC CIENCIAS,CTR BIOL CELULAR.'
             );



my %Frase;


for my $linea(@lineas){
    my @palabras = split /[ ,.]+/, lc($linea);
    $Frase{$linea} = \@palabras;
}


for my $key( keys %Frase ){

    print "Similares a: $key\n";

    my $size = @{ $Frase{$key} };

        while( my ($fr, $wrd) = each %Frase ){

            next if $fr eq $key;

            my %tmphash;
            my $ocurrencias = 0;

            map { $tmphash{$_}++ } @{ $Frase{$key} }, @{ $wrd };

            for( values %tmphash ){
                $ocurrencias++ if $_ > 1;
            }

            if( $ocurrencias ){
                my $aprox = sprintf("%.2f", ($ocurrencias/$size) * 100);
                print "\t ($aprox) $fr\n";
            }
            else{
                print "\t (SIN OCURRENCIAS) $fr\n";
            }
        }


    print " \n";

}
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4



El resultado que me arroja es el siguiente:

Código: Seleccionar todo
Similares a: UCV, FAC CIENCIAS,CTR BIOL CELULAR.
         (SIN OCURRENCIAS) CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
         (16.67) LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (16.67) UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (83.33) UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.

Similares a: CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
         (SIN OCURRENCIAS) UCV, FAC CIENCIAS,CTR BIOL CELULAR.
         (25.00) LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (25.00) UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (37.50) UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.

Similares a: LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (9.09) UCV, FAC CIENCIAS,CTR BIOL CELULAR.
         (18.18) CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
         (100.00) UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (27.27) UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.

Similares a: UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (9.09) UCV, FAC CIENCIAS,CTR BIOL CELULAR.
         (18.18) CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
         (100.00) LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (27.27) UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.

Similares a: UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
         (62.50) UCV, FAC CIENCIAS,CTR BIOL CELULAR.
         (37.50) CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
         (37.50) LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
         (37.50) UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.



Dentro de los paréntesis está el porcentaje de aproximación que tiene la frase indicada con cada una de las otras frases.

Lógicamente el código se puede mejorar, y pues lo hice en unos 20min., pero creo que te puede indicar más o menos el camino que puedes seguir.


Saludos
Uriel Lizama Perl programmer fundador de Perl en Español
Perl Programming Language
Avatar de Usuario
kidd
Creador de Perl en Español
Creador de Perl en Español
 
Mensajes: 1166
Registrado: 2003-10-15 16:52 @744
Ubicación: México

Notapor explorer » 2007-07-25 20:09 @881

Yo también quiero poner mi granito de arena.
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
#!/usr/bin/perl
use strict;
use warnings;

use String::Approx 'adist';

my @lineas = (
    'UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.',
    'LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.',
    'CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.',
    'UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.',
    'UCV, FAC CIENCIAS,CTR BIOL CELULAR.'
);

foreach my $l (@lineas) {
    print "$l\n",'='x80,"\n";

    my @dist = adist($l,@lineas);

    for( my $i = 0; $i < @dist; $i++ ) {
        print "$dist[$i] : $lineas[$i]\n";
    }

    print "\n";
}
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4
Sale:
Código: Seleccionar todo
UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
================================================================================
0 : UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
10 : LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
-55 : CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
-56 : UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
-56 : UCV, FAC CIENCIAS,CTR BIOL CELULAR.

LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
================================================================================
5 : UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
0 : LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
-54 : CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
-56 : UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
-56 : UCV, FAC CIENCIAS,CTR BIOL CELULAR.

CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
================================================================================
36 : UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
34 : LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
0 : CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
-30 : UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
-37 : UCV, FAC CIENCIAS,CTR BIOL CELULAR.

UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
================================================================================
32 : UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
33 : LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
25 : CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
0 : UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
-17 : UCV, FAC CIENCIAS,CTR BIOL CELULAR.

UCV, FAC CIENCIAS,CTR BIOL CELULAR.
================================================================================
23 : UNIV LOS ANDES, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
22 : LOS ANDES UNIV, FAC MED, NEUROENDOCRINOL LAB, DPTO FISIOPATOL, MERIDA, VENEZUELA.
22 : CENT UNIV VENEZUELA, INST ZOOL TROP, CARACAS 1041A.
4 : UNIV CENT VENEZUELA,FAC CIENCIAS,CTR BIOL CELULAR.
0 : UCV, FAC CIENCIAS,CTR BIOL CELULAR.
Los números indican la 'distancia' en caracteres (cambiados, añadidos, borrados), por lo que se puede tomar para decir que una entrada es parecida a otra (cuanto menos distancia, más se parecen).
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14482
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Notapor preiddy » 2007-07-26 07:49 @368

Muy interesante las respuestas, estoy digeriendo cada una, jajaja.
Luego les comento como me ha ido.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Notapor preiddy » 2007-07-26 08:08 @380

explorer, me he bajado el eclipse y le instalé el plugin de epic y genial, lo único que hecho en falta con respecto al emacs es el uso del tab, que me ajusta las líneas automáticamente, no importa donde este el cursor.

Gracias por compartir tan buenos comentarios y sugerencias.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Siguiente

Volver a Básico

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado

cron