15

10,000 個の電子メール アドレスのリストがあり、このリスト内の最も近い "隣人" を見つけたいとします。これは、リスト内の他の電子メール アドレスに疑わしいほど近い電子メール アドレスとして定義されます。

2 つの文字列間のレーベンシュタイン距離を計算する方法を認識しています ( this questionのおかげで)。これにより、ある文字列を別の文字列に変換するために必要な操作の数のスコアが得られます。

「別の電子メールアドレスに疑わしいほど近い」を、レーベンシュタインスコアが N 未満の 2 つの文字列として定義するとします。

可能なすべての文字列をリスト内の他のすべての文字列と比較する以外に、スコアがこのしきい値よりも低い文字列のペアを見つけるより効率的な方法はありますか? 言い換えれば、この種の問題は よりも早く解決できるO(n^2)でしょうか?

レーベンシュタイン スコアは、この問題のアルゴリズムとして不適切な選択ですか?

4

8 に答える 8

7

うん - BK-Treeを使用すると、文字列から特定の距離内にあるすべての文字列を O(log n) 時間で見つけることができます。距離 n のすべての文字列を生成する代替ソリューションは、レーベンシュタイン距離が 1 の場合は高速になる可能性がありますが、距離が長くなると、作業量が急速に制御不能になります。

于 2009-10-23T13:19:22.627 に答える
6

この問題はクラスタリングとして知られており、より大きな重複排除の問題 (クラスターのどのメンバーが「正しい」メンバーであるかを判断する場所) の一部であり、 merge-purgeとも呼ばれます。

まさにこのトピックに関するいくつかの研究論文を読んだことがあります (名前は以下にあります)。ウィンドウ内のN*N 文字列のみを (編集距離アルゴリズムを使用して) 比較するため、計算の複雑さが軽減されます。2 つの文字列が似ている場合は、(レコードを別のクラスター テーブルに挿入することによって) 1 つのクラスターに結合されました。

リストの最初のパスの後に、ソートされる前に文字列が反転される 2 番目のパスが続きました。このようにして、異なるヘッドを持つ文字列が、同じウィンドウの一部として評価されるのに十分近くなる別の機会がありました。この 2 回目のパスで、文字列がウィンドウ内の 2 つ (またはそれ以上) の文字列に十分近く見え、それらの文字列が (最初のパスで見つかった) 独自のクラスターの一部であった場合、2 つのクラスターは(更新によって)マージされます。クラスタ テーブル)、現在の文字列が新しくマージされたクラスタに追加されます。このクラスタリング アプローチは、union-findアルゴリズムとして知られています。

次に、ウィンドウを上位 X 個の実質的に固有のプロトタイプのリストに置き換えることで、アルゴリズムを改善しました。新しい文字列はそれぞれ、上位 X の各プロトタイプと比較されます。string がプロトタイプの 1 つに十分近い場合、プロトタイプの clusterに追加されます。どのプロトタイプも十分に似ていない場合、文字列は新しいプロトタイプになり、最も古いプロトタイプがトップ X リストから押し出されます。(プロトタイプのクラスタ内のどの文字列をクラスタ全体を表す新しいプロトタイプとして使用するかを決定するために採用されたヒューリスティック ロジックがありました)。繰り返しますが、文字列がいくつかのプロトタイプに似ている場合、それらのクラスターはすべてマージされます。

私はかつて、リストのサイズが約 1,000 万から 5,000 万レコードである名前/住所レコードの重複排除のためにこのアルゴリズムを実装しましたが、非常に高速に動作しました (重複もよく見つかりました)。

このような問題の全体として、もちろん最も難しい部分は、類似性しきい値の適切な値を見つけることです。アイデアは、あまりにも多くの誤検知を生成することなく、すべての重複をキャプチャすることです。異なる特性を持つデータには、異なるしきい値が必要になる傾向があります。編集距離アルゴリズムの選択も重要です。OCR エラーに適したアルゴリズムもあれば、タイプミスに適したアルゴリズムもあれば、音声エラー (電話で名前を取得するときなど) に適したアルゴリズムもあります。

クラスタリング アルゴリズムが実装されたら、それをテストする良い方法は、一意のサンプルのリストを取得し、各サンプルを人為的に変異させてバリエーションを生成することです。ただし、すべてのバリエーションが同じ親に由来するという事実を保持します。このリストはシャッフルされ、アルゴリズムに渡されます。元のクラスタリングと重複排除アルゴリズムによって生成されたクラスタリングを比較すると、効率スコアが得られます。

参考文献:

Hernandez M. 1995、大規模データベースのマージ/パージ問題。

Monge A. 1997 年、ほぼ重複したデータベース レコードを検出するための効率的なドメインに依存しないアルゴリズム。

于 2009-10-23T22:46:24.170 に答える
2

O(n^2) よりもうまくできるとは思いませんが、アプリケーションを使用可能にするのに十分なスピードアップになるいくつかの小さな最適化を行うことができます。

  • 最初にすべての電子メール アドレスを @ の後の部分で並べ替え、それが同じであるアドレスのみを比較できます。
  • 2 つのアドレス間の距離が n より大きくなった場合、距離の計算を停止できます。

編集：実際には、O（n ^ 2）よりもうまくいくことができます。以下のNick Johnsonの回答を見てください。

于 2009-10-22T20:31:10.030 に答える
1

3つの文字列があるとします。

1-"abc" 2-"bcd" 3-"cde"

1と2の間のL距離は2です（「a」を減算し、「d」を加算します）。2と3の間のL距離は2です（「b」を減算し、「e」を加算します）。

あなたの質問は、上記の2つの比較を使用して、1と3の間のL距離を推測できるかどうかです。答えはいいえだ。

1と3の間のL距離は3（すべての文字を置き換えます）です。最初の2つの計算のスコアのため、これを推測する方法はありません。スコアは、削除、挿入、または置換操作が実行されたかどうかを明らかにしません。

ですから、レーベンシュタインは大規模なリストには適していないと思います。

于 2009-10-22T20:36:16.073 に答える
1

10,000 個の電子メール アドレスは多すぎないように思えます。より大きな空間での類似検索には、shinglingとmin-hashingを使用できます。このアルゴリズムは実装が少し複雑ですが、大きなスペースでははるかに効率的です。

于 2009-10-22T20:39:50.117 に答える
1

It's possible to do better, at the condition of reversing the problem.

I suppose here that your 10.000 addresses are pretty 'fixed', otherwise you will have to add an update mechanism.

The idea is to use the Levenshtein distance, but in 'reverse' mode, in Python:

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

The generate_level method generates all possible variations from the previous set, minus the variations that already exist at a previous level. It preserves the 'origin' as the value associated to the key.

Then, you just have to lookup your word in the various set:

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

Doing so, you compute the various sets once (it takes some times... but then you can serialize it and keep it forever).

And then lookup is much more efficient than O(n^2), though giving it exactly is kind of difficult since it depends on the size of the sets that are generated.

For reference, have a look at: http://norvig.com/spell-correct.html

于 2009-10-23T08:10:25.460 に答える