4

おやすみなさい、

私はしばらくの間、ファジー文字列マッチングに取り組んでおり、C をいくつかのポインターと共に使用して、2 つの文字列間のレーベンシュタイン距離の非常に高速な (私のニーズに合わせた) 実装を作成できました。unsafe コードとfixedキーワードを使用してコードを C# に移植しようとしましたが、パフォーマンスが大幅に低下しました。そこで、C++ dll をビルドして使用することにしました。[DllImport]C# から、すべての文字列を自動的にマーシャリングします。問題は、プロファイリングの後、これが私のプログラムの中で最も時間のかかる部分であり続け、プログラムの総実行時間の 50 ～ 57% を占めていることです。約 300 万のデータベース レコードから取得したテキスト フィールドの多くの部分文字列を処理する必要があると思うので、レーベンシュタイン距離にかかる時間はほとんど許容できないと思います。ということで、以下のコードに対してアルゴリズムまたはプログラミング関連の提案があるかどうか、またはこの距離を計算するためのより良いアルゴリズムを知っているかどうかを知りたいです。

#define Inicio1  (*(BufferVar))
#define Inicio2  (*(BufferVar+1))
#define Fim1  (*(BufferVar+2))
#define Fim2  (*(BufferVar+3))
#define IndLinha (*(BufferVar+4))
#define IndCol  (*(BufferVar+5))
#define CompLinha (*(BufferVar+6))
#define TamTmp  (*(BufferVar+7))

int __DistanciaEdicao (char * Termo1, char * Termo2, int TamTermo1, int TamTermo2, int * BufferTab, int * BufferVar)
{
 *(BufferVar) = *(BufferVar + 1) = 0;
    *(BufferVar + 2) = TamTermo1 - 1;
    *(BufferVar + 3) = TamTermo2 - 1;

 while ((Inicio1 <= *(BufferVar + 2)) && (Inicio2 <= *(BufferVar + 3)) && *(Termo1 + Inicio1) == *(Termo2 + Inicio2))
  Inicio1 = ++Inicio2;

  if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);

 while ((Fim1 >= 0) && (Fim2 >= 0) && *(Termo1 + Fim1) == *(Termo2 + Fim2))
  { Fim1--; Fim2--;}

  if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);

 TamTermo1 = Fim1 - Inicio1 + 1;
 TamTermo2 = Fim2 - Inicio2 + 1;
 CompLinha = ((TamTermo1 > TamTermo2) ? TamTermo1 : TamTermo2) + 1;

 for (IndLinha = 0; IndLinha <= TamTermo2; *(BufferTab + CompLinha * IndLinha) = IndLinha++);
 for (IndCol = 0; IndCol <= TamTermo1; *(BufferTab + IndCol) = IndCol++);

 for (IndCol = 1; IndCol <= TamTermo1; IndCol++)
  for (IndLinha = 1; IndLinha <= TamTermo2; IndLinha++)
   *(BufferTab + CompLinha * IndLinha + IndCol) = ((*(Termo1 + (IndCol + Inicio1 - 1)) == *(Termo2 + (IndLinha + Inicio2 - 1))) ? *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)) : ((*(BufferTab + CompLinha * (IndLinha - 1) + IndCol) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) : ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)))) + 1);

 return *(BufferTab + CompLinha * TamTermo2 + TamTermo1);
}

BufferVar と BufferTab は 2 つの外部int *(この場合、int[]C# からマーシャリングされる変数) であり、プロセス全体を高速化するためにすべての関数呼び出しでインスタンス化しないことに注意してください。それでも、このコードは私のニーズに対してかなり遅いです。誰かが私にいくつかの提案をしてもらえますか、可能であれば、より良いコードを提供してもらえますか?

編集：距離を制限することはできません。実際の距離が必要です。

どうもありがとうございました、

4

3 に答える 3

5

1.ブルートフォース

Python でのレーベンシュタイン距離の実装を次に示します。

def levenshtein_matrix(lhs, rhs):
  def move(index): return (index+1)%2

  m = len(lhs)
  n = len(rhs)

  states = [range(n+1), [0,]*(n+1)]

  previous = 0
  current = 1

  for i in range(1, m+1):
    states[current][0] = i

    for j in range(1,n+1):
      add = states[current][j-1] + 1
      sub = states[previous][j] + 1
      repl = states[previous][j-1] + abs(cmp(lhs[i-1], rhs[j-1]))

      states[current][j] = min( repl, min(add,sub) )

    previous = move(previous)
    current = move(current)

  return states[previous][n]

これは典型的な動的計画法アルゴリズムであり、最後の行のみが必要なため、一度に 2 行だけ保持するだけで十分であることを利用しています。

C++ 実装の場合、LLVM のもの(70 ～ 130 行目) を見ると、固定サイズのスタック割り当て配列が使用されており、必要な場合にのみ動的に割り当てられた配列に置き換えられていることに注意してください。

コードを追跡して診断することはできません...それで、迎え角を変更しましょう。距離をマイクロ最適化する代わりに、アルゴリズムを完全に変更します。

2. 改善: 辞書の使用

あなたが直面している問題の 1 つは、もっとうまくやれるはずだということです。

最初の注意点は、距離が対称的であるということです。ただし、全体的な複雑さは変わりませんが、必要な時間は半分になります。

2 つ目は、既知の単語の辞書を実際に持っているため、それを基に構築できるということです。「actor」と「actual」は共通の接頭辞 (「act」) を共有しているため、最初の段階を再計算する必要はありません。

これは、Trie (またはその他のソートされた構造) を使用して単語を保存することで悪用される可能性があります。次に、1 つの単語を取得し、プレフィックスを利用して、辞書に格納されているすべての単語との相対的な距離を計算します。

例を挙げてみましょうdic = ["actor", "actual", "addict", "atchoum"]。距離を計算しますword = "atchoum"(この時点で辞書から削除します)。

  1. 「atchoum」という単語の行列を初期化します。matrix = [[0, 1, 2, 3, 4, 5, 6, 7]]
  2. 次の単語「俳優」を選んでください
  3. プレフィックス = "a"、マトリックス =[[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6]]
  4. プレフィックス = "ac"、マトリックス =[[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6], [2, 1, 1, 2, 3, 4, 5, 6]]
  5. プレフィックス = "act"、マトリックス =[[..], [..], [..], [..]]
  6. 「俳優」まで続けて、あなたの距離があります
  7. 次の単語 "actual" を選び、接頭辞が単語の接頭辞になるまで、ここでは "act" まで行列を巻き戻します。
  8. プレフィックス = "actu"、マトリックス =[[..], [..], [..], [..], [..]]
  9. 「実際」まで続ける
  10. 他の言葉を続ける

ここで重要なのは巻き戻しステップです。前の単語に対して行われた計算を保持することで、適切な長さのプレフィックスを共有することで、多くの作業を効果的に節約できます。

これは単純なスタックで自明に実装され、再帰呼び出しを必要としないことに注意してください。

于 2010-11-24T09:01:19.427 に答える
4

最初に単純なアプローチを試してみてください - ポインターや安全でないコードを使用しないでください - 普通の C# をコーディングするだけです... しかし正しいアルゴリズムを使用してください。

ウィキペディアには、動的計画法を使用して O(n*m) を実行する単純で効率的なアルゴリズムがあります。ここで、n と m は入力の長さです。そこで説明されているように、最初にそのアルゴリズムを実装してみることをお勧めします。実装してパフォーマンスを測定し、不十分であることが判明してから最適化を開始してください。

可能な改善のセクションも参照してください。

行の代わりに対角線を調べ、遅延評価を使用することで、O(m (1 + d)) 時間 (d はレーベンシュタイン距離) でレーベンシュタイン距離を見つけることができます。距離が小さい

問題がどこにあるかを推測する必要がある場合は、おそらく、2 つのループ内で実行される次の行を確認することから始めます。

*(BufferTab + CompLinha * IndLinha + IndCol) = ((*(Termo1 + (IndCol + Inicio1 - 1)) == *(Termo2 + (IndLinha + Inicio2 - 1))) ? *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)) : ((*(BufferTab + CompLinha * (IndLinha - 1) + IndCol) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) : ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)))) + 1);

何が起こっているのかを正確に特定するのは難しいですが、そこには多くの重複があるようです. そのいくつかを因数分解していただけますか？そして、間違いなく読みやすくする必要があります。

于 2010-11-23T20:12:04.307 に答える
2

レーベンシュタイン距離アルゴリズムを使用して、考えられるすべての単語を試してはいけません。別のより高速なメトリックを使用して、可能性のある候補を除外し、次にレーベンシュタインを使用してあいまいさを取り除く必要があります。最初のふるいは、n-gram（トリグラムがよく機能する）頻度ヒストグラムまたはハッシュ関数に基づくことができます。

于 2010-11-23T20:36:54.177 に答える