Existe algum programa para correspondência de seqüência difusa, que fornece uma pontuação de correspondência?

Eu tenho uma lista de seqüências de caracteres em arquivo Ae arquivo B. Quero pegar cada string no arquivo A e encontrar a string mais semelhante no arquivo B.

Para isso, estou procurando uma ferramenta que ofereça comparações fuzzy.

por exemplo:

$ fuzzy_compare "Some string" "Some string"
100

Onde 100 é alguma razão de igualdade. Por exemplo, distância de Levenshtein .

Existe alguma utilidade? Eu não quero reinventar a roda.

Encontrei esta página que fornece implementações do algoritmo de distância de Levenshtein em diferentes idiomas. Então, por exemplo, no bash, você pode fazer:

#!/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"

Salve como ~/bin/levenshtein.sh, torne-o executável ( chmod a+x ~/bin/levenshtein.sh) e execute-o em seus dois arquivos. Por exemplo:

$ 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

Isso é bom para alguns padrões, mas fica muito lento para arquivos maiores. Se isso for um problema, tente uma das implementações em outros idiomas. Por exemplo 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 acima, salve o script como, ~/bin/levenshtein.pltorne-o executável e execute-o com os dois arquivos como argumentos:

~/bin/levenstein.pl fileA fileB

Mesmo nos arquivos muito pequenos usados ​​aqui, a abordagem Perl é 10 vezes mais rápida que a do 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