A
我有文件和文件中的字符串列表B
。我想获取文件 A 中的每个字符串并在文件 B 中找到最相似的字符串。
为此,我正在寻找一种提供模糊比较的工具。
例如:
$ fuzzy_compare "Some string" "Some string"
100
其中 100 是某个相等比率。例如编辑距离。
有用吗?我不想重新发明轮子。
答案1
我发现这一页它提供了不同语言的 Levenshtein 距离算法的实现。因此,例如在 bash 中,您可以执行以下操作:
#!/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"
将其另存为~/bin/levenshtein.sh
,使其可执行(chmod a+x ~/bin/levenshtein.sh
)并在两个文件上运行它。例如:
$ 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
对于一些模式来说,这很好,但会非常对于较大的文件来说速度较慢。如果这是个问题,请尝试使用其他语言的实现之一。例如 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";
}
}
如上所述,将脚本另存为~/bin/levenshtein.pl
并使其可执行,并使用两个文件作为参数运行它:
~/bin/levenstein.pl fileA fileB
即使在这里使用的非常小的文件中,Perl 方法也比 bash 方法快 10 倍:
$ 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
答案2
我知道这是一个非常古老的帖子,但我找到了它,因为我正在寻找同样的东西。我找到了它:
该fstrcmp
命令将准确执行您所要求的操作:
> fstrcmp "Some string" "Some string"
1.0000
> fstrcmp "Some string" "Other string"
0.6957
> fstrcmp "Some string" "Pangalactic garglebalster"
0.2222
根据手册页,结果数字是编辑距离我认为这等同于编辑距离。
答案3
Python 有一个名为“fuzzywuzzy”的模块,可以对两个字符串进行评分匹配。我使用一个 CD 翻录器,它通过将“不雅”的文件名字符替换为下划线来“Linux化”专辑和曲目名称,这样我就不必在命令行中乱用反斜杠或引号了。如果我将目录名称中的所有下划线替换为空格,我就能获得与 CDDB 文件中的实际专辑名称匹配的良好结果。
fuzzywuzzy 可通过 pip 获得。