レーベンシュタイン距離の計算
1. 序章
このチュートリアルでは、2つのストリング間のレーベンシュタイン距離を計算するためのさまざまなオプションについて学習します。 基本的な実装の複雑さを検討し、改善する方法について説明します。
ただし、その前に、レーベンシュタイン距離に関する基本事項を更新しましょう。
2. 非公式の定義
レーベンシュタイン距離は、ある文字列を別の文字列に変換するために必要な編集操作の最小数です。編集操作には、挿入、削除、および置換が含まれます。
次の例では、「INTENTION」という単語を「EXECUTION」という単語に変換するために5つの操作を実行する必要があります。したがって、これら2つの単語間のレーベンシュタイン距離は5です。
レーベンシュタイン距離は、距離の編集として知られる距離メトリックのファミリーの中で最も人気のあるメトリックです。 これらの兄弟距離メトリックは、変換を実行できる基本操作のセットが異なります。 ハミング距離は置換のみを許可します。 ダメラウ・レーベンシュタイン距離では、レーベンシュタイン距離で定義されたセットに加えて、文字の転置が可能です。 これは、同じ名前で古典的なレーベンシュタイン距離の代わりに一般的に使用されます。
古典的なレーベンシュタイン距離では、すべての操作に単位コストがあります。 特殊なバージョンでは、操作に異なるコストが割り当てられる場合があります。また、キャラクターに応じてコストが割り当てられる場合もあります。 文字の視覚的または音声的類似性を表すために、このような複雑な操作コスト関数を定義したい場合があります。
3. 正式な定義とプロパティ
2つの弦の間のレーベンシュタイン距離は次の式で与えられます。
この式では、インジケーター関数は0に等しく、それ以外の場合は1になります。 文字列の長さを示します。
文字列プレフィックス間の距離です–の最初の文字との最初の文字。
この式の最初の部分は、プレフィックスを空の文字列に、またはその逆に変換するための挿入または削除のステップ数を示します。
2番目のブロックは再帰式で、最初の行は削除を表し、2番目の行は挿入を表します。 最後の行は置換を担当します。
レーベンシュタイン距離には次の特性があります。
- 2つの文字列が等しい場合にのみゼロになります
- 対称的です：
- 値は最大で長い文字列の長さです。
- 値は、少なくとも文字列のサイズの違いです。
- 三角不等式– 2つのストリング間の距離は、別のストリングからの距離の合計以下です。
これらのプロパティは、計算アルゴリズムがどのように機能するかを理解し、アプリケーションでそれらを使用することの両方を念頭に置くのに役立ちます。
三角不等式プロパティは、距離空間を構築するための主要な要件であるため、特定のタスクに非常に役立ちます。距離空間は、距離ツリー構造で効率的にインデックス付けできます。 これらには、とりわけ、BKツリーとVPツリーが含まれます。
4. アルゴリズム
レーベンシュタイン距離とその基本的な特性がわかったので、次にそれを計算する方法を見てみましょう。 最も些細な、そして非効率的なアルゴリズムから始めて、改善するためのオプションを見ていきます。
以下に定義されているすべてのアルゴリズムは、ゼロベースの文字列インデックスを使用しています。
4.1. 定義による再帰
この定義を使用して、単純な再帰アルゴリズムを作成できます。
この関数は、要素で始まる部分文字列を返します。
この実装では、まったく同じプレフィックスの距離が複数回再計算されるため、非常に非効率的です。
4.2. フルマトリックスで反復
レーベンシュタイン距離の特性を知っているので、位置の値を含むサイズの行列を作成できることがわかります。 このマトリックスの最初の行と最初の列は、定義上、それぞれ範囲との値を持つものとして知られています。
動的計画法を使用して、この行列をフラッドフィルして、結果の距離として最終的な右下の要素を取得できます。この実装は、 Wagner–Fischerアルゴリズムとして知られています。
「INTENTION」から「EXECUTION」への変換サンプルでこのアルゴリズムを実行すると、プレフィックス距離の結果マトリックスが生成されます。
このマトリックスの右下の要素は、以前に観察した5つの操作とまったく同じです。
4.3. 2行で反復
最終値のみを取得したい場合は、マトリックス全体の割り当てを回避するために、上記の実装を簡単に変更できます。 先に進むには、現在更新している行と前の行の2行だけが必要です。
この最適化により、実際の一連の編集操作を読み取ることができなくなります。 Hirschbergのアルゴリズムは、動的計画法と分割統治法の両方を使用してこの問題に対処します。
4.4. 1行で反復
さらに、特定の行の位置で値を計算するために必要な値は、左に1つ、真上に1つ、最後の1つが対角線の3つだけであるという事実を観察できます。
したがって、関数を変更して、2行ではなく1行と2つの変数のみを割り当てることができます。この変更により、メモリ要件がさらに緩和されます。
5. 複雑さと最適化
上記のすべての反復アルゴリズムの時間計算量はです。 完全なマトリックス実装のスペースの複雑さは、通常、使用することを非現実的にします。 2行と1行の両方の実装は、線形空間の複雑さを提供します。 ソースとターゲットを入れ替えて計算行の長さを減らすと、さらに短くなります。
強い指数時間仮説が偽でない限り、レーベンシュタイン距離は準二次時間で計算できないことが示されています。
幸い、これは最悪の場合の複雑さにのみ適用されます。
実用的な目的で、問題のデータセットの距離計算を可能にするために不可欠であることが判明する可能性のあるいくつかの最適化を導入する場合があります。
最後の単一行の実装では、スペースの割り当てを減らす方法の調査をすでに開始しています。 それでは、実際の実行時間をさらに短縮できるかどうかを見てみましょう。
5.1. 一般的なプレフィックスとサフィックス
「INTENTION」から「EXECUTION」への変換の例を見ると、これらの単語の両方に共通の接尾辞-TIONが付いていることがわかります。 この接尾辞がレーベンシュタイン距離に影響を与えないことは明らかです。
通常、最初の不一致文字位置を取得する関数は非常に効率的であるため、最も長い一般的な接尾辞と接頭辞を削除して、文字列部分を減らして完全な2次計算を実行する場合があります。
次の実装には、上記のスペースの複雑さを提供するために、上記のソースとターゲットのスワップも含まれています。
5.2. 上限と最小距離
比較的長い文字列があり、かなり類似した文字列のみを比較することに関心があるとします。 名前のつづりが間違っています。 このような場合、完全なレーベンシュタイン計算では、実際には必要のない右上隅と左下隅の高い値を含め、行列全体をトラバースする必要があります。 これにより、しきい値を使用した最適化の可能性がわかります。境界を超えるすべての距離は、単に範囲外として報告されます。 したがって、制限された距離の場合、幅の対角線のストライプの値のみを計算する必要があります。ここで、は距離のしきい値です。
文字列「SYDENYMEIER」と「SYDNYMEYER」をしきい値2で比較しているとしましょう。 赤で強調表示されている、対角セルの両側のセルにまたがるストライプのセルの値を計算する必要があります。
言い換えれば、レーベンシュタイン距離が境界より上にある場合、実装はあきらめます。
このアプローチにより、の時間計算量が得られ、長いが類似した文字列に対して許容可能な実行時間が提供されます。
さらに、距離は少なくとも文字列の長さの差であることがわかっているため、選択したしきい値を超えた場合は計算をスキップできます。
ここで、境界を使用して2行アルゴリズムの変更を実装できます。
実用的な目的で、この関数を使用して、最初にしきい値1の距離を計算し、次に実際の制限に達するか距離が見つかるまで、毎回しきい値を2倍にすることができます。
5.3. テクニックの組み合わせ
特定のアプリケーションによっては、上記の最適化手法によって達成された結果に満足する場合があります。 それでも、二次計算になってしまう可能性があるため、特に類似性の低い長い文字列の場合は、実行時間を考慮する必要があります。
レーベンシュタイン距離以外にも、バッグ距離、ジャロウィンクラー距離、q-gramなど、直線的な走行時間を持つ多くの指標があります。これらの手法のいずれかを使用して、許容範囲から一致を除外できます。類似範囲。 選択したおおよそのメトリックに基づいて一致の小さなセットができたら、実際のレーベンシュタイン距離を実行してそれらをランク付けします。
6. オートマトン
特定の辞書でファジーテキスト検索を実行できるようにする別のアプローチは、レーベンシュタインオートマトンを使用することです。基本的な考え方は、有限状態オートマトンを構築することです。文字列からのレーベンシュタイン距離が。以下の文字列のセットを正確に受け入れる文字列と数値。
構築されたオートマトンに任意の単語をフィードすることにより、この単語からターゲット文字列までの距離が、オートマトンによって受け入れられたか拒否されたかに基づいて、指定されたしきい値よりも大きいかどうかを定義できます。
FSAの性質上、実行時間はテスト対象の単語の長さに比例します。
オートマトンの構築自体は計算コストが非常に高くなる可能性がありますが、で可能であることが示されています。
7. アプリケーション
レーベンシュタイン距離は、編集距離のファミリーからのその兄弟とともに、幅広いアプリケーションを見つけます。
近似文字列マッチングは、ファジーテキスト検索とも呼ばれ、多くの場合、レーベンシュタイン距離に基づいて実装されます。これは、スペルチェッカー、修正システムなどのさまざまなアプリケーションで使用されます。光学式文字認識、音声認識、スパムフィルタリング、レコードリンケージ、重複検出、自然言語翻訳支援、計算生物学におけるRNA / DNAシーケンス、およびあいまい検出などに使用されます。
Javaのいくつかのフレームワークには、 Hibernate Search 、 Solr 、 Elasticsearch など、何らかの形で実装されています。
また、言語学では、レーベンシュタイン距離を使用して、言語または方言が互いにどの程度異なるかを示す指標である言語間距離を決定する場合があります。
8. 結論
このチュートリアルでは、レーベンシュタイン距離を実装するためのさまざまなアルゴリズムについて説明しました。
最悪の場合の複雑さは2次式であることがわかりました。したがって、可能な最適化の問題は、使用可能な実装を提供するための取り組みにとって非常に重要です。
最後に、計算コストを直接削減するためのいくつかの手法に加えて、議題のタスクに対処するためにさまざまなアプローチを使用できることを確認しました。
