2つの文字列の類似度を測定するアルゴリズム

Question

2つの文字列の類似度をどのように測定できますか？

私は2つのテキストファイルがあり、ファイルであっシーケンスが

まずファイルのように書かれています：

AAA BBB DDD CCC GGG MMM AAA MMM

セカンドファイル：

BBBDDCCC MMM AAA MMM

これら2つのファイルの類似性を文字列の順番で測定する方法は？

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

Answer 1

Levenstein Distanceアルゴリズムを使用できます。ある文字列を別の文字列に変換するために必要な編集回数を分析します。 Thisの記事でそれを説明し、サンプルの実装が提供されています。 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]. 

Answer 2

あなたは範囲[0, 1]のfloatとしてシーケンス類似性を測定PythonのSequenceMatcher.ratio機能を使用することができます。 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 

私はこれがあなたを助けることを望みます！