Apakah ada program untuk pencocokan string fuzzy, yang memberikan skor kecocokan?

17

Saya memiliki daftar string dalam file Adan file B. Saya ingin mengambil setiap string dalam file A dan menemukan string yang paling mirip di file B.

Untuk ini, saya mencari alat yang menyediakan perbandingan fuzzy.

sebagai contoh:

$ fuzzy_compare "Some string" "Some string"
100

Di mana 100 adalah beberapa rasio kesetaraan. Misalnya jarak Levenshtein .

Apakah ada utilitas? Saya tidak ingin menemukan kembali roda.

c0rp
sumber
1
Saya mengedit pertanyaan Anda untuk meningkatkan kejelasan tetapi mengubahnya untuk bertanya tentang membandingkan setiap string dalam fileA dengan yang ada di fileB dan tidak hanya yang pertama. Saya berasumsi bahwa itulah yang Anda maksudkan tetapi mohon perbaiki jika saya salah.
terdon
@muru tidak, itu hanya untuk pencocokan fuzzy, OP perlu skor.
terdon

Jawaban:

23

Saya menemukan halaman ini yang menyediakan implementasi algoritma jarak Levenshtein dalam berbagai bahasa. Jadi, misalnya dalam bash, Anda dapat melakukan:

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

Simpan itu sebagai ~/bin/levenshtein.sh, membuatnya dapat dieksekusi ( chmod a+x ~/bin/levenshtein.sh) dan jalankan di dua file Anda. Sebagai contoh:

$ 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

Itu bagus untuk beberapa pola tetapi akan menjadi sangat lambat untuk file yang lebih besar. Jika itu masalah, coba salah satu implementasi dalam bahasa lain. Misalnya 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";
    }
}

Seperti di atas, simpan skrip sebagai ~/bin/levenshtein.pldan buat itu dapat dieksekusi dan jalankan dengan dua file sebagai argumen:

~/bin/levenstein.pl fileA fileB

Bahkan dalam file yang sangat kecil yang digunakan di sini, pendekatan Perl 10 kali lebih cepat daripada yang 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
sumber
Untuk menambahkan beberapa penjelasan lebih lanjut tentang hasilnya: mengutip wikipedia, jarak Levenshtein antara dua kata adalah jumlah minimum dari pengeditan karakter tunggal (yaitu penyisipan, penghapusan atau penggantian) yang diperlukan untuk mengubah satu kata ke kata lain . Itu berarti semakin rendah angkanya, semakin baik pertandingan. Sejumlah nol berarti pasangan yang sempurna. Perhatikan juga bahwa jarak Levenshtein menangani setiap karakter yang diedit secara sama, yang berarti "foo" dan "Foo" mengarah ke jarak yang sama dengan "foo" dan "fox".
scai