这是我正在尝试做的事情:我想使用 bash 测量两个字符串之间的 Levensthein 距离。我找到了 LD here 的实现.
现在,假设我有一些像这样的玩具数据:
1 The brown fox jumped The green fox jumped
0 The red fox jumped The green fox jumped
1 The gray fox jumped The green fox jumped
假设这存储在 data.test
中。
然后我通过一个简单的 awk
命令来过滤掉以 1
开头的行,如下所示:
awk -F '\t' '{if ($1>0) print $2,t,$3}' data.test
这个简单命令的第一个输出将是:
The brown fox jumped The green fox jumped
我现在想测量这两个句子之间的 Levensthein 距离,方法是将此输出直接输送到此函数(从上面的链接中提取):
function levenshtein {
if (( $# != 2 )); then
echo "Usage: $0 word1 word2" >&2
elif (( ${#1} < ${#2} )); then
levenshtein "$2" "$1"
else
local str1len=${#1}
local str2len=${#2}
local d
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
del=$(( d[(i-1)+str1len*j]+1 ))
ins=$(( d[i+str1len*(j-1)]+1 ))
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
}
我知道你可以做到这一点,但我被两个需要传递的参数和我正在传递序列的事实所困扰。
我尝试过使用各种版本的 this建议,提倡这样获取输入:
function levenshtein {
# Grab input.
declare input1=${1:-$(</dev/stdin)};
declare input2=${2:-$(</dev/stdin)};
.
.
.
}
这是我无法完成的部分。
最佳答案
你根本不需要awk
:
while IFS=$'\t' read num first second; do
[[ $num -gt 0 ]] || continue
levenshtein "$first" "$second"
done < data.txt
(没错,awk
处理大文件的速度比 bash
快,但是如果您在 bash
中实现 Levenshtein 算法首先,速度可能不是问题。)
顺便说一句,通过使用以“元组”作为键的关联数组,不需要太多索引算法的更简单(尽管经过最低限度测试)实现。
levenshtein () {
if (( ${#1} < ${#2} )); then
levenshtein "$2" "$1"
return
fi
local str1len str2len cost m a b i j
local -A d
str1len=${#1}
str2len=${#2}
for ((i=0;i<=strlen1;i++)); do
d[$i,0]=0
done
for ((j=0;j<=strlen2;j++)); do
d[0,$j]=0
done
for ((j=1; j<=str2len; j++)); do
for ((i=1; i<=str1len; i++)); do
a=${1:i-1:1}
b=${2:j-1:1}
[ "$a" = "$b" ] && cost=0 || cost=1
del=$(( $d[$((i-1)),$j] + 1 ))
ins=$(( $d[$i,$((j-1))] + 1 ))
alt=$(( $d[$((i-1)),$((j-1))] + cost ))
# Compute the min without forking
m=$del; ((ins < m)) && m=$ins; ((alt < m)) && m=$alt
d[$i,$j]=$m
done
done
echo ${d[$str1len,$str2len]}
}
关于bash - 将输出管道输出到具有多个输入的 bash 函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56062722/