php - MySQLでレーベンシュタインは遅いですか？

Question

昨日、レーベンシュタイン法を使うように言われたところがありました。遅いクエリですか？多分私は何か他のものを使うことができますか？

Answer 1

この関数を使用してBENCHMARK、パフォーマンスをテストできます。

SELECT BENCHMARK(10000, LEVENSHTEIN('abc', 'abd'));

ユースケースに似たさまざまな文字列でテストしてみてください。

Answer 2

データセットによって異なります。

同じ長さの文字列を比較するだけで、かなり高速化できることがわかりました。

文字列の長さがどれだけ似ている必要があるかは、データによって異なります。

ここに主題に関する記事があります：http：//kerbtier.ch/2008/12/30/levenshtein-to-slow-how-to-speed-it-up

Answer 3

うまく機能させたい場合は、スキーマを正規化します。

問題は、他のデータがどれほど類似しているかを判断するために、DBMSがそのデータをロードし、データと比較する必要があることです。したがって、「類似した」値を見つけるには、テーブル内のすべての行（現在の行を除く）を読み取る必要があります。インデックスを使用して、データムに近いデータを見つけることはできません。

一方、次のようなスキーマを使用した場合：

CREATE TABLE member (
   member_id      INT(11),
   member_data    CLOB,
   PRIMARY KEY (member_id));

CREATE TABLE about_member (
   member_id      INT(11),
   metric         VARCHAR(10),
   value          MEDIUMINT(9),
   PRIMARY KEY (member_id, metric),
   KEY by_value (metric, value, member_id));

about_member（1-1-2-2-1）文字列は、個別の行として実装する必要があることに注意してください。

 member_id     metric      value
 1234          lost        2
 1234          won         3
 1234          drawn       1
 1234          handicap    9

次に、たとえば次のクエリを使用して、インデックスを効果的に使用できます。

 SELECT compare.member_id, SUM(ABS(compare.value-datum.value)) AS difference
 FROM about_member compare, about_member datum
 WHERE datum.member_id=$MEMBER_TO_COMPARE
 AND compare.member_id<>datum.member_id
 AND compare.metric=datum.metric
 AND compare.metric BETWEEN (datum.metric-1) AND (datum.metric+1) /* tweak here */
 GROUP BY compare.member_id;