2

2 つの非常に長い一連の単語があります。

それらが異なる場所を見つける必要があります。たとえば、入力が

1st sequence: A B C D E F G
2nd sequence: A X D Y Z W G

(ここでの各文字は単語を表します)

出力は次のようになります。

B C -> X
E F -> Y Z W

私が考えたこと：両方のシーケンスへのインデックスを持つことができました。最初は、両方とも A を指します。両方のインデックスをインクリメントします。これで、最初のインデックスは B を指し、2 番目のインデックスは X を指します。これで、2 番目のシーケンス全体で B を検索できました。見つからなかったので、2 番目のシーケンス全体で C を検索し、次に D を検索しました。D を見つけて、したがって、問題を解決できます。

明らかに、この「強引な」方法はひどいものです。

より良い方法は何ですか？

私は Python でコードを書いており、NLTK を使用しています。したがって、組み込みの NLTK 機能を使用して部分的または完全に解決できれば、(実装が) 高速になります。

4

3 に答える 3

7

difflib.SequenceMatcher.get_opcodesこれを行うことができます。

import difflib

def diff(a, b):
    for tag, i1, i2, j1, j2 in difflib.SequenceMatcher(a=a, b=b).get_opcodes():
        if tag!='equal':
            yield a[i1:i2], b[j1:j2]

>>> d = list(diff('A B C D E F G'.split(), 'A X D Y Z W G'.split()))
>>> d
[(['B', 'C'], ['X']), (['E', 'F'], ['Y', 'Z', 'W'])]
>>> '\n'.join('{} -> {}'.format(*(' '.join(i) for i in l)) for l in d)
B C -> X
E F -> Y Z W

古い答え – 同等の機能:

import difflib

def diff(a, b):
    add, remove = [], []
    for line in difflib.ndiff(a, b):
        d, line = line[0], line[2:]
        if d in '+-':
            (add if d=='+' else remove).append(line)
        elif add or remove:
            yield remove, add
            add, remove = [], []
    if add or remove:
        yield remove, add
于 2012-06-13T10:57:11.917 に答える
1

これは、古典的な編集距離の問題です。私はあなたにそれをグーグルさせて、それがどのように機能するかを理解させるつもりです。これについては担当者は必要ありません。

于 2012-06-13T10:45:03.070 に答える
0

レーベンスタイン距離のウィキペディア ページ にある疑似コードの例を見てください。この例は、必要に応じて簡単に変更できます。

于 2012-06-13T10:58:16.110 に答える