Левенштейн работает медленно в 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

Если вы хотите, чтобы он работал хорошо, нормализует вашу схему .

Проблема в том, что для определения того, насколько похожи другие данные, СУБД должна загрузить эти данные и сравнить их с данными. Таким образом, он должен прочитать каждую строку в таблице (кроме текущей), чтобы найти «похожие» значения. Он не может использовать индексы для поиска данных, которые близки к данным.

Если, с другой стороны, вы использовали такую ​​схему:

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;