一种查找常用编辑的算法

Question

我有两个单词列表,一个例子:

 list 1  list 2

 foot    fuut
 barj    kijo
 foio    fuau
 fuim    fuami
 kwim    kwami
 lnun    lnun
 kizm    kazm

我想找

o ? u # 1 and 3
i ? a # 3 and 7
im ? ami # 4 and 5

这应按发生次数排序,因此我可以过滤那些不经常出现的那些.

这些列表目前包含35k字,平均服务器上的计算时间约为6h.

Answer 1

像LCS方法一样编辑距离算法和Levenshtein距离是有益的.但它们用于将一个单词更改为另一个单词,通过这些方法,您可以了解如何将一个单词更改为另一个单词,并且更改量最少.但它们对于在两个词典中找到最小量的更改没有用.

最长的公共子序列(LCS)问题是找到一组序列中所有序列共有的最长子序列(通常只有两个).请注意,子序列与子字符串不同,请参阅substring与subsequence.它是一个典型的计算机科学问题,是diff等文件比较程序的基础,并且在生物信息学中有应用.

通过使用LCS或任何其他方法,对于list1中的每个单词,找到该单词如何变为列表2中的另一个单词.例如,在foot&feet之间:LCS = FT,difference = oo => ee.你应该制作一个二分图,第一部分由差异词组成,第二部分由list1组成.第二部分中的每个节点在第一部分中连接到它自己的相关差异.

我认为长度和单词的总数是有限的.

我们可以用图表来模拟这个问题.将每个更改分配给一个节点.例如,e→i(确定其中一个变化)是一个节点的标签.例如,如果形式p→q的所有操作都设置为二分图中的一个部分,并且每对字的总差异等于1,则定义边缘集合,即边缘uv连接顶点U到V字(u)(第二个)部分)更改为正确的单词需要V的更改.您在第一部分中有一个最大25*26节点(对于此示例).如果在你的情况下长度> = 1,那么你需要设置一个限制.我假设每个单词的最大部分变化是相等的3.因此我们在第一部分中有3*35K的最大节点.现在你可以通过选择第二部分中可以覆盖最大单词的第一部分中的节点集来解决问题(你选择的应该发生单词更改为正确的单词).

在此图中找到最小顶点切割,找到它们可以提供请求的节点集.并重复切割顶点算法,直到获得良好答案.

你可以使用某种界限来减小图形的大小,例如删除第一部分中具有度数的所有节点1,因为这个节点只连接到一个单词,所以它们似乎没用.

此图模拟可以解决您的问题.使用当前的问题陈述,此算法边界正常工作.

例如:

它是此图中边界的示例(删除操作部分中的所有节点,它们具有1个边):

1 - 删除节点4,因为它只连接到(nod),然后删除节点(节点)2 - 删除节点2,因为它只连接到(sghoul),然后删除节点(sghoul)3 - 现在删除节点3,因为它只连接到(goud)[sghoul被移除最后一步],然后删除节点(goud)

现在你有一个操作oo => ee,你可以选择这个.

我会考虑更多,并尝试编辑此文本.

Answer 2

我的最终解决方案是使用mosesdecoder。我将单词拆分为单个字符并将它们用作平行语料库并使用提取的模型。我比较了苏尔西万和瓦拉德。

export IRSTLM=$HOME/rumantsch/mosesdecoder/tools/irstlm
export PATH=$PATH:$IRSTLM/bin

rm -rf corpus giza.* model
array=("sur" "val")
for i in "${array[@]}"; do
    cp "raw.$i" "splitted.$i"
    sed -i 's/ /@/g' "splitted.$i"
    sed -i 's/./& /g' "splitted.$i"
    add-start-end.sh < "splitted.$i" > "compiled.$i"
    build-lm.sh -i "compiled.$i" -t ./tmp -p -o "compiled.lm.$i"
    compile-lm --text yes "compiled.lm.$i.gz" "compiled.arpa.$i"
done

../scripts/training/train-model.perl --first-step 1 --last-step 5 -root-dir . -corpus splitted -f sur -e val -lm 0:3:$PWD/compiled.arpa.sur -extract-options "--SentenceId" -external-bin-dir ../tools/bin/

$HOME/rumantsch/mosesdecoder/scripts/../bin/extract $HOME/rumantsch/mosesdecoder/rumantsch/splitted.val $HOME/rumantsch/mosesdecoder/rumantsch/splitted.sur $HOME/rumantsch/mosesdecoder/rumantsch/model/aligned.grow-diag-final $HOME/rumantsch/mosesdecoder/rumantsch/model/extract 7 --SentenceId --GZOutput

zcat model/extract.sid.gz | awk -F '[ ][|][|][|][ ]' '$1!=$2{print $1, "|", $2}' | sort | uniq -c | sort -nr | head -n 10 > results