レーベンシュタイン距離: テキストの類似性を測定するための究極のガイド

レーベンシュタイン距離は、編集距離とも呼ばれ、2 つの文字列間の類似性を評価するための基本的な指標です。ある文字列を別の文字列に変換するために必要な操作の最小数を計算します。これらの操作には次のものが含まれます:

1. 挿入: 文字を追加します。
2. 削除: キャラクターを削除します。
3. 置換: ある文字を別の文字に置き換えます。

この概念は、スペルチェック、あいまい検索、DNA 配列比較など、多くの現代アプリケーションの中心となっています。

数学的概念

長さ ( n ) と ( m ) の 2 つの文字列 ( A ) と ( B ) の間のレーベンシュタイン距離は、動的計画法を使用して計算できます。サイズ ((n 1) 倍 (m 1)) の行列 ( D ) を定義します。ここで、各エントリ ( D[i][j] ) は、( A ) の最初の ( i ) 文字を次のように変換するための最小コストを表します。 ( B ) の最初の ( j ) 文字。

漸化式は次のとおりです。

Pythonの実装

レーベンシュタイン距離を計算するための簡単な Python 実装を次に示します。

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[n][m]

# Example usage
print(levenshtein_distance("kitten", "sitting"))  # Output: 3

実用的なアプリケーション

1. スペルチェック

スペル チェッカーは、レーベンシュタイン距離を使用してタイプミスの修正を提案します。たとえば、「helo」と入力すると、「hello」または「hero」が提案される可能性があります。

2. あいまい検索

検索エンジンでは、ユーザーがタイプミスやスペルミスをした場合でも、レーベンシュタインは結果を返すのに役立ちます。

3. DNA の比較

バイオインフォマティクスでは、この距離は 2 つの DNA 配列間の類似性を測定するのに役立ちます。各操作は潜在的な突然変異を表します。

4. 認証と不正検出

なりすまし詐欺を検出するシステムは、ユーザー入力を既存の記録と比較し、テキストの小さな違いを考慮できます。

最適化: メモリを削減したレーベンシュタイン距離

古典的なアルゴリズムは完全な行列を使用するため、メモリを大量に消費する可能性があります。幸いなことに、各 ( D[i][j] ) は ( D[i-1][j] )、( D[i][j-1] ) にのみ依存するため、メモリの 2 行のみを使用するように最適化できます。 )、および ( D[i-1][j-1] )。

def optimized_levenshtein(a, b):
    n, m = len(a), len(b)
    prev = list(range(m + 1))
    curr = [0] * (m + 1)

    for i in range(1, n + 1):
        curr[0] = i
        for j in range(1, m + 1):
            insert = curr[j - 1] + 1
            delete = prev[j] + 1
            substitute = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else 1)
            curr[j] = min(insert, delete, substitute)
        prev, curr = curr, prev

    return prev[m]

# Example usage
print(optimized_levenshtein("kitten", "sitting"))  # Output: 3

結論

レーベンシュタイン距離は、さまざまな分野で広く使用されている強力で多用途のツールです。把握するのは簡単ですが、その最適化と複雑なアプリケーションにより、最新のシステムにおけるその価値が強調されます。

さらに詳しく調べるために、転置を考慮したダメラウ・レーベンシュタイン距離のような変形を考慮してください。これで、このツールをプロジェクトに統合したり、深い理解を示して同僚に感銘を与えたりする準備が整いました!

レーベンシュタイン距離について質問やアイデアがありますか?コメントでシェアしてください！ ?

以上がレーベンシュタイン距離: テキストの類似性を測定するための究極のガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。