¿Existe algún programa para la coincidencia de cadenas difusas, que proporcione una puntuación de coincidencia?

17

Tengo una lista de cadenas en archivo Ay archivo B. Quiero tomar cada cadena en el archivo A y encontrar la cadena más similar en el archivo B.

Para esto, estoy buscando una herramienta que proporcione una comparación difusa.

por ejemplo:

$ fuzzy_compare "Some string" "Some string"
100

Donde 100 es alguna relación de igualdad. Por ejemplo, la distancia de Levenshtein .

¿Hay alguna utilidad? No quiero reinventar la rueda.

c0rp
fuente
1
Edité su pregunta para mejorar la claridad, pero la cambié para preguntar sobre la comparación de cada cadena en el archivo A con las del archivo B y no solo la primera. Supuse que eso era lo que querías decir, pero corrígeme si me equivoqué.
terdon
@muru no, eso es solo para coincidencias difusas, el OP necesita un puntaje.
terdon

Respuestas:

23

Encontré esta página que proporciona implementaciones del algoritmo de distancia de Levenshtein en diferentes idiomas. Entonces, por ejemplo en bash, podrías hacer:

#!/bin/bash
function levenshtein {
    if [ "$#" -ne "2" ]; then
        echo "Usage: $0 word1 word2" >&2
    elif [ "${#1}" -lt "${#2}" ]; then
        levenshtein "$2" "$1"
    else
        local str1len=$((${#1}))
        local str2len=$((${#2}))
        local d i j
        for i in $(seq 0 $(((str1len+1)*(str2len+1)))); do
            d[i]=0
        done
        for i in $(seq 0 $((str1len))); do
            d[$((i+0*str1len))]=$i
        done
        for j in $(seq 0 $((str2len))); do
            d[$((0+j*(str1len+1)))]=$j
        done

        for j in $(seq 1 $((str2len))); do
            for i in $(seq 1 $((str1len))); do
                [ "${1:i-1:1}" = "${2:j-1:1}" ] && local cost=0 || local cost=1
                local del=$((d[(i-1)+str1len*j]+1))
                local ins=$((d[i+str1len*(j-1)]+1))
                local alt=$((d[(i-1)+str1len*(j-1)]+cost))
                d[i+str1len*j]=$(echo -e "$del\n$ins\n$alt" | sort -n | head -1)
            done
        done
        echo ${d[str1len+str1len*(str2len)]}
    fi
}

while read str1; do
        while read str2; do
                lev=$(levenshtein "$str1" "$str2");
                printf '%s / %s : %s\n' "$str1" "$str2" "$lev"
        done < "$2"
done < "$1"

Guarde eso como ~/bin/levenshtein.sh, hágalo ejecutable ( chmod a+x ~/bin/levenshtein.sh) y ejecútelo en sus dos archivos. Por ejemplo:

$ cat fileA
foo
zoo
bar
fob
baar
$ cat fileB
foo
loo
baar
bob
gaf
$ a.sh fileA fileB
foo / foo : 0
foo / loo : 1
foo / baar : 4
foo / bob : 2
foo / gaf : 3
zoo / foo : 1
zoo / loo : 1
zoo / baar : 4
zoo / bob : 2
zoo / gaf : 3
bar / foo : 3
bar / loo : 3
bar / baar : 1
bar / bob : 2
bar / gaf : 2
fob / foo : 1
fob / loo : 2
fob / baar : 4
fob / bob : 1
fob / gaf : 3
baar / foo : 4
baar / loo : 4
baar / baar : 0
baar / bob : 3
baar / gaf : 3

Eso está bien para algunos patrones, pero será muy lento para archivos más grandes. Si eso es un problema, pruebe una de las implementaciones en otros idiomas. Por ejemplo Perl:

#!/usr/bin/perl 
use List::Util qw(min);

sub levenshtein
{
    my ($str1, $str2) = @_;
    my @ar1 = split //, $str1;
    my @ar2 = split //, $str2;

    my @dist;
    $dist[$_][0] = $_ foreach (0 .. @ar1);
    $dist[0][$_] = $_ foreach (0 .. @ar2);

    foreach my $i (1 .. @ar1) {
        foreach my $j (1 .. @ar2) {
            my $cost = $ar1[$i - 1] eq $ar2[$j - 1] ? 0 : 1;
            $dist[$i][$j] = min(
                            $dist[$i - 1][$j] + 1, 
                            $dist[$i][$j - 1] + 1, 
                            $dist[$i - 1][$j - 1] + $cost
                             );
        }
    }

    return $dist[@ar1][@ar2];
}
open(my $fh1, "$ARGV[0]");
open(my $fh2, "$ARGV[1]");
chomp(my @strings1=<$fh1>);
chomp(my @strings2=<$fh2>);

foreach my $str1 (@strings1) {
    foreach my $str2 (@strings2) {
        my $lev=levenshtein($str1, $str2);
        print "$str1 / $str2 : $lev\n";
    }
}

Como arriba, guarde el script como ~/bin/levenshtein.ply hágalo ejecutable y ejecútelo con los dos archivos como argumentos:

~/bin/levenstein.pl fileA fileB

Incluso en los archivos muy pequeños utilizados aquí, el enfoque de Perl es 10 veces más rápido que el bash:

$ time levenshtein.sh fileA fileB > /dev/null

real    0m0.965s
user    0m0.070s
sys     0m0.057s

$ time levenshtein.pl fileA fileB > /dev/null
real    0m0.011s
user    0m0.010s
sys     0m0.000s
terdon
fuente
Para agregar más explicaciones sobre los resultados: citando wikipedia, la distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (es decir, inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra . Eso significa que cuanto menor sea el número, mejor será la coincidencia. Un número de cero significa una combinación perfecta. También tenga en cuenta que la distancia de Levenshtein maneja las ediciones de cada personaje por igual, lo que significa que "foo" y "Foo" conducen a la misma distancia que "foo" y "fox".
scai