php - MySQL 中的 Levenshtein 慢吗？

Question

昨天我有一个问题，人们建议我使用Levenshtein方法。它是一个缓慢的查询吗？也许我可以用别的东西？

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;