1. 序章

これは、文字列類似性メトリックに関する概要記事の続きです。 このチュートリアルは、前述のシーケンスベースの方法に焦点を当てています。

  • 最長の共通部分文字列
  • 最長共通部分列
  • Gestaltパターンマッチング

最長共通部分文字列と最長共通部分列は、最長共通部分文字列アルゴリズムの点でのみ異なります。 「シーケンス」は連続する文字に制限されています。 最長共通部分列は、連続する部分文字列のグループを検索します。

これらの2つの方法では、2つの文字列の類似性は共通の長さに基づいています。

gestaltパターンのマッチングでは、最も長い共通のサブストリングを再帰的に使用して、類似性の尺度を確立します。

次のセクションでは、さらに詳しく説明します。

2. 最長の共通部分文字列

文字列の類似性に使用できるツールの1つは、最長の共通部分文字列（LCS）を見つけることです。 共通のサブストリングが最も長いほど、2つのストリングは類似しています。 最長の共通部分文字列を次のように定義します。

2つの文字列「X」と「Y」が与えられた場合、最長の共通部分文字列の長さを見つけます。

最長の共通部分文字列を見つけることは、最初と後続の残りの文字列（LCSにない文字）でLCSを再帰的に見つけることにより、文字列類似性メソッドの基礎として使用できます。 これがGestaltパターンマッチングの基礎です。

2つの文字列のLCSを見つけるための概念的に最も単純なアプローチは、最初に長さ1の（最小の）文字列のすべての部分文字列を見つけることです。 これは時間内に行うことができます。 これらの文字列のそれぞれについて、それが長さ.の2番目の文字列の部分文字列であるかどうかを判別します。 これは時間内に行うことができます。 合計時間計算量はです。

このメソッドの実装は、複雑さも示しており、文字を繰り返さずに最長の部分文字列を見つけるアルゴリズムの複雑さを改善する1つの方法は、動的計画法[を使用することです。 X249X]。 このメソッドは、文字のオーバーラップのマトリックスを作成します。

2.1. 動的計画法

動的計画法を使用することの複雑さは、単純なアプローチよりもはるかに優れています。 つまり、、ここで、およびは比較する文字列の長さです。 このメソッドの中心は、行と列がそれぞれ各文字列の文字であるby行列を作成することです。 このメソッドでは、最も長い共通の接尾辞を見つけます。これは、同じ末尾の両方の文字列の中で最も長い部分文字列を意味します。

サイズの文字列とサイズの文字列に対してこれを行うには、最初に次のプロパティを持つサイズの行列を作成します。

たとえば、2つの文字列と、がある場合、作成するマトリックスは次のようになります。

最大数はであるため、最も長い一般的な部分文字列は4文字の長さであることがわかります。 サブストリング自体を見つけるには、この場合は最大数から始めて、次のようにカウントダウンします。

このアルゴリズムの複雑さは、文字のループによって支配されていることがわかります。

3. 最長共通部分列

最長共通シーケンスと最長共通サブストリングの違いは、サブストリングとは異なり、「シーケンス」は元のシーケンス内の連続した位置を占める必要がないことです。 一致しない文字にギャップがある可能性があります。たとえば、次の2つの文で：

キツネは高い柵を飛び越えた

速い茶色のキツネが柵を飛び越えた。

最長の部分文字列は次のとおりです。

キツネは飛び越えた

ただし、最長のサブシーケンスは次のとおりです。

キツネは柵を飛び越えた

最長共通シーケンスを見つけるための動的計画法は、両方で文字重複行列が作成されるという点で最長共通部分文字列に似ています。 マトリックスは同じ方法で作成されます。 違いは、この行列をトラバースして共通部分列を見つける方法にあります。 以前と同じようにカウントダウンしますが、最大のサブシーケンスを見つけるために、次に小さいカウントにトラバースすることはマトリックスで隣接している必要はありません。

4. Gestaltパターンマッチング

Ratcliff / Obershelpパターン認識としても知られるゲスタルトパターンマッチングは、この記事で最初に公開されたパターン類似性手法です。 パターンマッチング：博士のゲシュタルトアプローチ。 ドブの日記 。 ゲシュタルトという言葉は、自然のシステムとその特性をパーツの緩いコレクションとしてではなく全体として見る必要があるという考えを意味し、文字列全体が一緒に分析されることを強調するために使用されます。 ゲシュタルトアプローチは、人間の分析に近い方法であることが意図されています。

2つの文字列、およびが与えられた場合の主要な式は次のとおりです。

ここで、は文字列内の一致する文字の数であり、は2つの文字列の長さです。 類似度メトリックは、文字列間の一致なしと同一の一致の間の値です。 一致する文字は、最初に最長の共通部分文字列（LCS）を見つけ、次に再帰的に、両方の文字列の一致しない領域で一致する文字を（LCSを再度使用して）見つけることによって決定されます。

このアルゴリズムを、「Pennsylvania」および「Pencilvaneya」という単語を使用した元のアルゴリズムで使用された例で説明します。 2つの文字列のLCSは「lvan」です：「Pennsy lvan ia」、「Penci lvaneya」。 したがって、イニシャルはです。

次に、一致した部分の左右に残っている2つの残りのペア、[‘Pennsy’、’Penci’]と[‘ia’、’eya’]を続けます。 「Pen nsy」、「 Pen ci」という単語が見つかり、「Pen」と共通して一致し、に増加します。

残りのペア[nsy、ci]には共通の文字がないため、こちら側で完了です。 [‘i a ‘、’ey a ‘]を続けると、共通の文字’ a’が1つあることがわかり、に増加します。 残りの文字列[‘i’、’ey’]には文字がないことがわかるので、これで完了です。 したがって、合計のスコアは次のとおりです。

このアルゴリズムの実装は、Ratcliffの記事の Cおよびアセンブラーにありますが、元のアルゴリズムに基づく Python の実装、さらにはScalaの実装もあります。[X221X ]

ゲシュタルトアルゴリズムの複雑さの根本は、最も長い一般的な部分文字列アルゴリズムに依存していることがわかります。 事実上、これにより、最悪の場合の複雑さが、最良の場合のになります。

5. 概要

この記事では、2つの文字列の類似性を分析する一般的な分野でシーケンスベースの方法を検討しました。 最も長い一般的な部分文字列メソッドは、それ自体が類似性メソッドであるだけでなく、Gestaltパターンマッチングアルゴリズム内の主要なアルゴリズムでもあることがわかりました。 また、動的計画法を使用すると、アルゴリズムの複雑さが大幅に改善されることもわかりました。