48

次のようにスミスのテーブルを検索して、1つの分散内にあるすべてのものを取得できるようにしたいと思います。

データ：

オブライエン
スミス
ドラン
スマス
ウォン
スモス
ガンサー
Smiht

レーベンシュタイン距離の使用を検討しましたが、これを実装する方法を知っている人はいますか？

4

9 に答える 9

12

レーベンシュタイン距離を使用して効率的に検索するには、bk-treeなどの効率的で特殊なインデックスが必要です。残念ながら、MySQLを含め、私が知っているデータベースシステムはbkツリーインデックスを実装していません。行ごとに1つの用語だけでなく、全文検索を探している場合、これはさらに複雑になります。一方で、レーベンシュタイン距離に基づいて検索できるように全文索引を作成できる方法は考えられません。

于 2009-03-13T11:17:17.667 に答える
8

レーベンシュタイン距離関数の mysql UDF 実装があります

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

これは C で実装されており、schnaader が言及した「MySQL レーベンシュタイン距離クエリ」よりも優れたパフォーマンスを発揮します。

于 2013-11-12T03:38:07.207 に答える
5

上記の levenshtein <= 1 に指定された関数は正しくありません。たとえば、"bed" や "bid" に対して誤った結果が返されます。

上記の「MySQLレーベンシュタイン距離クエリ」を最初の回答で変更し、「制限」を受け入れて少し高速化しました。基本的に、レーベンシュタイン <= 1 のみを気にする場合は、制限を「2」に設定すると、0 または 1 の場合、関数は正確なレーベンシュタイン距離を返します。正確なレーベンシュタイン距離が 2 以上の場合は 2。

この mod を使用すると、15% から 50% 高速になります。検索語が長いほど、利点が大きくなります (アルゴリズムが早く回避できるため)。 「くすくす笑い」、元のラップトップでは 3 分 47 秒かかりましたが、「制限」バージョンでは 1:39 でした。もちろん、これらはどちらもリアルタイムで使用するには遅すぎます。

コード：

DELIMITER $$
CREATE FUNCTION levenshtein_limit_n( s1 VARCHAR(255), s2 VARCHAR(255), n INT) 
  RETURNS INT 
  DETERMINISTIC 
  BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0; 
    IF s1 = s2 THEN 
      RETURN 0; 
    ELSEIF s1_len = 0 THEN 
      RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
      RETURN s1_len; 
    ELSE 
      WHILE j <= s2_len DO 
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
      END WHILE; 
      WHILE i <= s1_len and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it
        SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1; 
        WHILE j <= s2_len DO 
          SET c = c + 1; 
          IF s1_char = SUBSTRING(s2, j, 1) THEN  
            SET cost = 0; ELSE SET cost = 1; 
          END IF; 
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
          IF c > c_temp THEN SET c = c_temp; END IF; 
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
            IF c > c_temp THEN  
              SET c = c_temp;  
            END IF; 
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
            IF c < c_min THEN
              SET c_min = c;
            END IF; 
        END WHILE; 
        SET cv1 = cv0, i = i + 1; 
      END WHILE; 
    END IF;
    IF i <= s1_len THEN -- we didn't finish, limit exceeded    
      SET c = c_min; -- actual distance is >= c_min (i.e., the smallest value in the last computed row of the matrix) 
    END IF;
    RETURN c;
  END$$
于 2014-08-03T19:21:33.917 に答える
5

Damerau-Levenshtein 距離の実装は、次の場所にあります。 Damerau-Levenshtein アルゴリズム: 転置を伴うレーベンシュタイン 純粋なレーベンシュタイン距離の改善点は、文字の交換が考慮されることです。schnaaderのリンクのコメントで見つけました、ありがとう！

于 2009-03-13T11:48:34.707 に答える
3

Gonzalo Navarro と Ricardo Baeza-yates による論文に基づいて、インデックス付きテキストを複数回検索するために、Levenshtein または Damerau-Levenshtein (おそらく後者) に基づく検索を設定しています:リンク テキスト

接尾辞配列を作成した後 ( wikipedia を参照)、検索文字列との不一致が最大で k 個ある文字列に関心がある場合は、検索文字列を k+1 個に分割します。それらの少なくとも 1 つが無傷である必要があります。接尾辞配列に対して二分探索によって部分文字列を見つけてから、一致した各部分の周囲のパッチに距離関数を適用します。

于 2009-05-02T23:43:23.707 に答える
3

この機能を使用できます

CREATE FUNCTION `levenshtein`( s1 text, s2 text) RETURNS int(11)
    確定的
始める
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char CHAR;
    cv0、cv1 テキストを宣言します。
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
      リターン 0;
    ELSEIF s1_len = 0 THEN
      RETURN s2_len;
    ELSEIF s2_len = 0 THEN
      RETURN s1_len;
    そうしないと
      WHILE j <= s2_len DO
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
      終了まで;
      WHILE i <= s1_len DO
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
        WHILE j <= s2_len DO
          セット c = c + 1;
          IF s1_char = SUBSTRING(s2, j, 1) THEN  
            コストを設定 = 0; ELSE SET コスト = 1;
          END IF;
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + コスト;
          IF c > c_temp THEN SET c = c_temp; END IF;
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
            IF c > c_temp THEN  
              SET c = c_temp;  
            END IF;
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
        終了まで;
        SET cv1 = cv0, i = i + 1;
      終了まで;
    END IF;
    戻る c;
  終わり

XX％として取得するには、この関数を使用します

CREATE FUNCTION `levenshtein_ratio`( s1 text, s2 text ) RETURNS int(11)
    確定的
始める
    DECLARE s1_len、s2_len、max_len INT;
    SET s1_len = 長さ(s1), s2_len = 長さ(s2);
    IF s1_len > s2_len THEN  
      SET max_len = s1_len;  
    そうしないと  
      SET max_len = s2_len;  
    END IF;
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
  終わり
于 2011-04-29T21:04:31.047 に答える
0

k-distance searchの特殊なケースがあり、MySQLにDamerau-Levenshtein UDFをインストールした後、クエリに時間がかかりすぎることがわかりました。私は次の解決策を思いついた：

  • 非常に制限された検索スペースがあります（9文字の文字列は数値に制限されています）。

ターゲットフィールドの各文字位置の列を含む新しいテーブルを作成します（またはターゲットテーブルに列を追加します）。すなわち。VARCHAR（9）は、最終的に9つのTINYINT列+ 1つのId列になり、メインテーブルと一致します（各列にインデックスを追加します）。メインテーブルが更新されたときにこれらの新しい列が常に更新されるように、トリガーを追加しました。

k-distanceクエリを実行するには、次の述語を使用します。

（Column1 = s [0]）+（Column2 = s [1]）+（Column3 = s [2]）+（Column4 = s [3]）+ ...> = m

ここで、sは検索文字列であり、mは必要な一致する文字数です（または、私の場合はm = 9-dで、dは返される最大距離です）。

テストの結果、平均4.6秒かかっていた100万行を超えるクエリが、1秒未満で一致するIDを返していることがわかりました。メインテーブルの一致する行のデータを返す2番目のクエリも、同様に1秒未満かかりました。（これら2つのクエリをサブクエリまたは結合として組み合わせると、実行時間が大幅に長くなり、理由はわかりません。）

これはダメラウ・レーベンシュタインではありませんが（代用は考慮されていません）、私の目的には十分です。

このソリューションは、より大きな（長さの）検索スペースではおそらく適切に拡張できませんが、この制限のあるケースでは非常にうまく機能しました。

于 2012-04-16T04:39:26.960 に答える