MySQL：文字の違いが1つしかない文字列を効率的に選択する方法は？

Question

MySQLでは、指定された文字列との文字の違いが1つしかないすべての文字列をテーブルから選択できますか？

例えば、 Iphone 5とIphone 5sまたはModel x-1とModels x1

Answer 1

あなたは、あなたがレーベンシュタインの距離を使用することができ、MySQLへのユーザ機能を追加することができ場合。コードについては、this other questionを参照してください。

たとえば、WHERE LEVENSHTEIN(description, 'iphone 5') <= 2を問い合わせることができます。あなたは "iphone 5S"と "ipohne 5"を見つけるでしょう。それはプラスかもしれません。

そうでなければ、の具体的なの場合は簡単です（たとえば、REGEX 'iphone.*'またはそれに近い）が、一般的な場合は実装するのが難しいでしょう。

パフォーマンス

このバージョンでは、第三のパラメータ、MAXCOSTを受け入れるように修正されます。 levenshteinサブルーフのmaxcostに達すると、検索機能は単に中断します。病理学的事例を除いて、実際のコストがわずかにずれていることを覚えておいてください（すなわち、12のコストを除外するとコストが12の文字列を含み、11のコストを持つ文字列は除外できます）。これは、Levenshtein距離は無理です。これらのケースはおそらくあなたにとって興味がありません。

距離が3未満の文字列が必要な場合は、WHERE levenshtein(string1, string2, 4) < 3を使用します。距離が3-4以上の文字列はすべてのすぐに4 を返し、除外されます。

テスト：

mysql> select BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 99)); 
+------------------------------------------------------------------+ 
| BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 99)) | 
+------------------------------------------------------------------+ 
|                0 | 
+------------------------------------------------------------------+ 
1 row in set (2.50 sec) 

mysql> select BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 3)); 
+-----------------------------------------------------------------+ 
| BENCHMARK(1000,levenshtein('PIPPORIDICOLO','LUKASPERICOLO', 3)) | 
+-----------------------------------------------------------------+ 
|                0 | 
+-----------------------------------------------------------------+ 
1 row in set (0.08 sec) 

ここコストは1000件の評価につき80ミリ秒に2500年から減少しています。

これは変更されたコードです。名前を変更しない限り、この新しい関数を定義する前に古い関数を削除する必要があります。

DELIMITER $$ 
CREATE FUNCTION levenshtein(s1 VARCHAR(255), s2 VARCHAR(255), maxcost INTEGER) 
RETURNS INT 
DETERMINISTIC 
BEGIN 
DECLARE s1_len, s2_len, i, j, c, c_temp, cost 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; 
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 DO 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF c > maxcost THEN 
       RETURN maxcost; 
      END IF; 
      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; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
    END WHILE; 
END IF; 
RETURN c; 
END$$ 
DELIMITER ;