10

例として、2つの単語リストがあります。

 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

これは発生量順に並べる必要があるので、頻繁に表示されないものをフィルタリングできます。

リストは現在35,000語で構成されており、平均的なサーバーでの計算には約6時間かかります。

4

3 に答える 3

10

LCS法のように、距離アルゴリズムとレーベンシュタイン距離を編集することは有益です。しかし、それらはある単語を別の単語に変更するために使用されます。これらの方法により、最小限の変更である単語を別の単語に変更する方法を見つけることができます。ただし、2つの辞書で最小限の変更を見つけるのには役立ちません。

最長共通部分列（LCS）の問題は、シーケンスのセット（多くの場合2つだけ）内のすべてのシーケンスに共通する最長のサブシーケンスを見つけることです。サブシーケンスはサブストリングとは異なることに注意してください。サブストリングとサブシーケンスを参照してください。これは古典的なコンピュータサイエンスの問題であり、diffなどのファイル比較プログラムの基礎であり、バイオインフォマティクスに応用されています。

LCSまたはその他の方法を使用して、リスト1の各単語について、その単語がリスト2の別の単語にどのように変化するかを調べます。たとえば、足と足の間：LCS = FT、difference = oo=>ee。最初の部分は異なる単語から作成し、2番目の部分はlist1から作成する2部グラフを作成する必要があります。2番目の部分の各ノードは、最初の部分の関連する違いに接続されています。

単語の長さと全体の部分は限られていると思います。

この問題はグラフでモデル化できます。各変更を1つのノードに割り当てます。たとえば、 e→i（変更の1つを決定する）は1つのノードのラベルです。たとえば、p→qの形式のすべての操作が2部グラフで1つの部分に設定され、単語の各ペアの合計の差が1に等しい場合、Edgeがuv頂点を接続UするEdgeコレクションを定義しますV（2番目に）パート）正しい単語に変更するには、Vの変更が必要です。最初のパートには最大25 * 26ノードがあります（この例の場合）。あなたの場合の長さ>=1の場合、したがって、制限を設定する必要があります。各単語の変更の最大部分は3に等しいと仮定します。したがって、最初の部分には3*35Kの最大ノードがあります。これで、最初の部分で最大の単語をカバーできるノードのセットを選択して問題を解決できます（選択した単語は正しい単語に変更されます）。

このグラフで最小の頂点カットを見つけて、リクエストを提供できるノードのセットを見つけます。適切な答えが得られるまで、カット頂点アルゴリズムを繰り返します。

ある種の境界を使用してグラフのサイズを縮小できます。たとえば、次数を持つ最初の部分のすべてのノードを削除できます1。このノードは正確に1つの単語に接続されているため、役に立たないようです。

このグラフシミュレーションはあなたの問題を解決することができます。現在の問題ステートメントでは、このアルゴリズムの範囲は適切に機能します。

例えば：ここに画像の説明を入力してください

このグラフの境界の例です（1つのエッジを持つ操作部分のすべてのノードを削除します）。

1-ノード4は（nod）にのみ接続されているため削除し、次にノード（nod）を削除します2-ノード2は（sghoul）にのみ接続されているため削除し、次にノード（sghoul）を削除します3-ノード3を削除します（goud）にのみ接続されています[sghoulは最後のステップで削除されます]、次にノード（goud）を削除します

これで、oo => eeの操作が1つあり、これを選択できます。

もっと考えて、このテキストを編集してみます。

于 2012-05-24T23:22:01.020 に答える
3

レーベンシュタイン距離などの距離編集アルゴリズムを使用できます。正確な変更を登録するには、アルゴリズムに若干の変更を加える必要がある場合があります。

于 2012-05-19T14:31:47.020 に答える
2

私の最終的な解決策は、mosesdecoderを使用することです。単語を1文字に分割し、それらを対訳コーパスとして使用し、抽出されたモデルを使用しました。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 に答える