3

レーベンシュタイン距離を使用して、ユーザーが入力したものに最も近い結果を判別するストアドプロシージャがあります。速度に実際に影響するのは、距離が最も短いレコードを選択する前に、すべてのレコードのレーベンシュタイン距離を計算する関数だけです（これは、レーベンシュタイン関数の呼び出しの代わりに0を付けることで確認しました）。テーブルには150万のレコードがあるため、わずかな調整でも数秒短縮される可能性があります。現在、すべてが10分以上実行されています。これが私が使用している方法です：

ALTER function dbo.Levenshtein
( 
    @Source nvarchar(200), 
    @Target nvarchar(200) 
) 
RETURNS int
AS
BEGIN
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000)

SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0

WHILE @j <= @Target_len
BEGIN
    SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1
END

WHILE @i <= @Source_len
BEGIN
    SELECT @Source_char = SUBSTRING(@Source, @i, 1), @Dist = @i, @Distv0 = CAST(@i AS binary(2)), @j = 1

WHILE @j <= @Target_len
BEGIN
    SET @Dist = @Dist + 1
    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j-1, 2) AS int) +
                  CASE WHEN @Source_char = SUBSTRING(@Target, @j, 1) THEN 0 ELSE 1 END

    IF @Dist > @Dist_temp
    BEGIN
        SET @Dist = @Dist_temp
    END

    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j+1, 2) AS int)+1

    IF @Dist > @Dist_temp SET @Dist = @Dist_temp
    BEGIN
        SELECT @Distv0 = @Distv0 + CAST(@Dist AS binary(2)), @j = @j + 1
    END
END

SELECT @Distv1 = @Distv0, @i = @i + 1
END

RETURN @Dist
END

ここからどこへ行けばいいの？

4

1 に答える 1

6

私が過去にこれを行った方法は、「データベース」(実際には、スペル修正プログラム用の単語の辞書) をトライとして格納することです。

次に、分岐限定ルーチンを使用して、最も近い一致するエントリを検索しました。短い距離の場合、かかる時間は距離の指数関数的です。距離が長い場合、今見ているように、辞書のサイズに比例します。

分枝限定法は、基本的にトライの深さ優先のツリー ウォークですが、エラー バジェットがあります。各ノードで、現在のレーベンシュタイン距離を追跡し、それが予算を超えている場合は、ツリーのその枝を剪定します。

まず、予算ゼロで散歩をします。これにより、完全一致のみが検索されます。一致するものが見つからない場合は、予算 1 で実行します。これにより、距離 1 で一致が検出されます。一致が見つからない場合は、予算 2 で実行します。以下同様です。これは非効率に思えますが、各歩行には前の歩行よりもはるかに多くの時間がかかるため、時間は最後に行った歩行によって支配されます。

追加: コードの概要 (私の C を許してください):

// dumb version of trie node, indexed by letter. You can improve.
typedef struct tnodeTag {
  tnodeTag* p[128];
} tnode;

tnode* top; // the top of the trie

void walk(tnode* p, char* s, int budget){
  int i;
  if (*s == 0){
    if (p == NULL){
      // print the current trie path
    }
  }
  else if (budget >= 0){
    // try deleting this letter
    walk(p, s+1, budget-1);
    // try swapping two adjacent letters
    if (s[1]){
      swap(s[0], s[1]);
      walk(p, s, budget-1);
      swap(s[0], s[1]);
    }
    if (p){
      for (i = 0; i < 128; i++){
        // try exact match
        if (i == *s) walk(p->p[i], s+1, budget);
        // try replacing this character
        if (i != *s) walk(p->p[i], s+1, budget-1);
        // try inserting this letter
        walk(p->p[i], s, budget-1);
      }
    }
  }
}

基本的に、文字をスキップして同じノードを検索することで、文字の削除をシミュレートします。s を進めずにトライを下降させることで、文字の挿入をシミュレートします。文字が一致しない場合でも、文字が一致するかのように振る舞うことで、文字の置換をシミュレートします。コツをつかめば、0 を O に、1 を L や I に置き換えるなど、他の可能な不一致を追加できます。

おそらく、文字配列引数を追加して、トライで見つけている現在の単語を表すことをお勧めします。

于 2010-05-27T11:36:47.070 に答える