10

我有两个单词列表，一个例子：

 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 字组成，在平均服务器上计算大约需要 6 小时。

4

3 回答 3

10

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

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

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

我想单词的长度和总部分是有限的。

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

在此图中找到最小顶点切割，以找到他们可以提供您的请求的节点集。并重复切割顶点算法，直到得到好的答案。

您可以使用某种边界来减小图形的大小，例如删除第一部分中具有 degree 的所有节点1，因为这些节点只连接到一个单词，所以它们似乎没用。

这个图形模拟可以解决你的问题。对于当前的问题陈述，这个算法范围可以正常工作。

例如：在此处输入图像描述

这是此图中边界的示例（删除操作部分中具有 1 条边的所有节点）：

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

现在你有一个操作 oo=>ee 并且你可以选择这个。

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

于 2012-05-24T23:22:01.020 回答
3

您可以使用编辑距离算法，例如Levenshtein distance。可能需要对算法进行一些小的更改以记录精确的修改。

于 2012-05-19T14:31:47.020 回答
2

我的最终解决方案是使用 mosesdecoder。我将单词拆分为单个字符并将它们用作并行语料库并使用提取的模型。我比较了 Sursilvan 和 Vallader。

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
于 2012-06-05T12:03:25.157 回答