7

2 つの文字列シーケンス間の類似度を測定するにはどうすればよいですか?

私は2つのテキストファイルを持っており、ファイルにはシーケンスが次のように書かれています

最初のファイル:

AAA BBB DDD CCC GGG MMM AAA MMM

2 番目のファイル:

BBB DDD CCC MMM AAA MMM

文字列の順序に関してこれら 2 つのファイルの類似性を測定するにはどうすればよいですか?

たとえば、上記の例では、文字列の順序が同じであるため、両方のファイルに類似性がありますが、ファイル 2 では一部の文字列が欠落しています。この問題を解決するのに最適なアルゴリズムはどれですか?2 つの文字列の頻度ではなく、文字列の順序がどの程度類似しているかを測定できますか?

4

2 に答える 2

8

レーベンスタイン距離アルゴリズムを使用できます。ある文字列を別の文字列に変換するために必要な編集の回数を分析します。この記事ではそれについてかなり詳しく説明しており、サンプルの実装が提供されています。

Codeprojectからコピーして貼り付けます:

1.  Set n to be the length of s. ("GUMBO")
    Set m to be the length of t. ("GAMBOL")
    If n = 0, return m and exit.
    If m = 0, return n and exit.
    Construct two vectors, v0[m+1] and v1[m+1], containing 0..m elements.
2.  Initialize v0 to 0..m.
3.  Examine each character of s (i from 1 to n).
4.  Examine each character of t (j from 1 to m).
5.  If s[i] equals t[j], the cost is 0.
    If s[i] is not equal to t[j], the cost is 1.
6.  Set cell v1[j] equal to the minimum of:
    a. The cell immediately above plus 1: v1[j-1] + 1.
    b. The cell immediately to the left plus 1: v0[j] + 1.
    c. The cell diagonally above and to the left plus the cost: v0[j-1] + cost.
7.  After the iteration steps (3, 4, 5, 6) are complete, the distance is found in the cell v1[m].
于 2012-06-01T05:58:00.100 に答える
6

SequenceMatcher.ratio範囲内のフロートとしてシーケンスの類似性を測定する python の関数を使用できます[0, 1]。Tが両方のシーケンスの要素の総数であり、Mが一致の数である場合、これはです2.0 * M / T。主なコードは次のとおりです。

from difflib import SequenceMatcher
text1 = 'AAA BBB DDD CCC GGG MMM AAA MMM'
text2 = 'BBB DDD CCC MMM AAA MMM'
s = SequenceMatcher(None, text1, text2)
similarity = s.ratio() * 100

これがお役に立てば幸いです。

于 2015-02-19T08:00:03.687 に答える