1. 序章

このチュートリアルでは、文字列類似性メトリックで説明されているトークンベースの文字列類似性メトリックについて詳しく説明します。

このカテゴリに分類されるアルゴリズムは、多かれ少なかれ、セット類似性アルゴリズムであり、セットは文字列トークンで構成されています。 このチュートリアルでは、次のアルゴリズムについてもう少し詳しく説明します。

  • Qグラム
  • オーバーラップ係数
  • ジャッカードの類似性
  • ダイス係数

後者の3つの測定値は、セットの類似性に基づいています。

2. トークンメソッド

文字列類似度のトークンメソッドのセットには、基本的に次の3つのステップがあります。

  1. トークン：比較するテキスト文字列を調べて、文字列のセットを意味するトークンのセットを定義します
  2. Count ：比較する各文字列内のこれらのトークンの数をカウントします
  3. Measure ：これらのカウントを使用して距離または類似度を計算します

q-gramなどの一部のメソッドには、トークンを生成する特定の方法があり、他のメソッドでは、適切と思われる方法でトークンを定義できます。 たとえば、通常のテキストでは、個々の単語を選択できます。

比較するテキストでトークンを「カウント」する方法はいくつかあります。 1つの方法で、text内でのそのトークンの出現回数をカウントします。 テキストの類似性は、これらの違いによって表されます。

集合論を使用して、テキスト内のトークンの使用を説明することもできます。 ここでのメジャーは、セット類似性のクラスにあります。 メジャーは、2つのセット間の類似度を計算します。 この場合、セットはトークンで構成されています。

トークンのカウントを組み合わせて最終的な類似度を形成する方法が、メソッドを区別する主な方法です。 すべてのメソッドは、との間の単一の数値を生成します。

3. テキストの近似

すべてのトークンメソッドに共通する1つのプロパティは、テキストをトークンのセットと見なすという事実に基づいており、その結果、これらのトークンがテキストのどこにあるかは気になりません。

たとえば、テキストがある場合：

「HelloWorld」

トークンとして「Hello」と「World」を使用します。 テキスト：

「ワールドハロー」

同じスコアを受け取ります。 同じトークンが両方のテキストにあります。 変化するのは、テキストの中でそれらが見つかった場所です。 これは、テキストの比較と類似性を簡単に実装でき、比較的高速な方法で支払う価格です。

4. Qグラム

この方法では、トークンの作成は非常に具体的で明確に定義されています。 これらのトークンを数え、テキスト間の出現の違いを調べます。

このメソッドで使用するトークンは、長さの文字列であるq-gramです。 この方法では、2つの文字列を見て、それぞれに特定の長さの文字列が何回出現するかを質問します。 次に、これら2つの数値をどのように比較するか、つまり、絶対距離を取得してこれらの距離を合計するかどうかを尋ねます。 これが、2つのストリング間の類似性または距離の測定値です。 数字が小さいほど、文字列は類似しています。

2つの文字列がまったく同じである場合、トークンカウントは同じになり、差はゼロになります。 同じトークンがない場合、違いは大きな数になります（基本的には各文字列のトークンの出現の合計）。

2つの文字列が同じではないが、トークンのセットの順序が異なる場合、合計はゼロのままであることがわかると、これはおおよその方法であることがわかります。

もう少し数学的に言えば、テキスト文字列内のq-gramの出現回数とします。 2つの弦の間の距離測度は次のとおりです。

5. 類似性を設定する

類似性の測定の1つのセットは、トークン資産の調査に基づいています。 調査している各文字列のトークンのセットを比較し、メジャーを計算します。これらのメジャーはセット類似度です。

設定された類似度は、トークンの定義方法を正確に指定していません。 トークンの作成方法は実装に任されており、トークンのセットとしてn-gramを使用することもできます。

5.1. 計算を設定する

トークンを定義したら、セット理論的な方法でトークンをカウントして、セット間の違いを見つけます。 メジャーによって使用されるセットに基づくいくつかの計算があります。

トークンのセット全体から、テキストで実際に見つかったこれらのトークンの数を数えることができます。これは、数学的に次のように表すことができます。

これは、テキストで見つかったトークンのセットであるセットのサイズを表します。

もう1つの重要な計算は、2つのセット間のオーバーラップです。 2つのセットに共通するトークンの数について質問します。 2つのセット、、が与えられた場合、これを数学的に次のように表します。

記号はセット間の交差を表します。

3番目の量は、両方のセットで使用されたトークンのセットをカウントすることです。 2つのセット、およびが与えられた場合、これは次のように表されます。

ここで、記号はセット間のユニオンを表します。 どちらのセットでも使用されていないトークンは、このカウントに含まれません。

5.2. 類似性を設定する

セットの類似性測度は、ほとんどの場合、2つのセット間で共通するトークンの数、つまりセット間の共通部分を決定します。 メジャーは基本的に、「正規化」、、つまり、カウントをとの間の数値にする方法のみが異なります。 文字列と文字列の類似性の尺度は、基本的に、それらが共通して持つトークンの数を正規化係数で割ったものです。

オーバーラップ係数の設定された類似度は次のとおりです。

ここで、はのトークン数との最小トークン数です。

ジャッカード係数は、係数オーバーラップメジャーに似ていますが、差が項の正規化方法です。 ジャッカード係数の場合、トークンのオーバーラップを、両方を組み合わせた一意のトークンの数で正規化（除算）します。

ある意味で、これは重複するトークンのパーセンテージと考えることができます。

ジャッカード距離もあります。これは次のように定義されます。

ダイス係数（またはソーレンセン-ダイス係数とも呼ばれる）は、ジャッカード係数と同様です。

もう一度、用語の正規化が異なります。

6. 例

2つの簡単なテキストがあるとします。

A ：「勇敢な新世界」

B ：「helloworld」

C：「こんにちは新しい世界」

2つのトークン化手法を使用します。 最初のものについては、単語を分離します。

2つ目は、2グラムを使用します。

まず、単語のカウントの表を作成します。

また、n-gramの表を作成します。

 

メジャーに必要な量を計算します。最初に次の単語を使用します。

正確な数は異なりますが、すべてのメジャーが同じ傾向を示していることがわかります。 「bravenewworld」と「hellonewworld」が最も近く、「helloworld」が最も異なると全員が予測しました。

7. 概要

トークンの類似性測度（およびメソッド）は、文字列の類似性メソッドの特殊なケースです。 これは、文字列を分割してトークンに比較することに基づいています。 関連する計算は、比較的単純なカウントアルゴリズムです。

トークンを使用したいくつかの文字列類似度を調べて比較しました。 3つの方法、オーバーラップ係数、ジャッカード係数、およびダイス係数は、設定された類似度に基づいていました。 それらはすべて異なる正規化係数を使用するという点で実際の結果が異なります。 これらのメソッドは、テキストからトークンを作成する方法を指定していませんでした。

n-gramメソッドは、トークンと特定のメジャーを作成するための特定の方法を提供しました。 ただし、トークン化方式は他の手段と一緒に使用できます。

この例では、すべての測定値が期待される類似性の結果を正しく生成していることがわかりました。