mysql - 在MySQL中找到最长的匹配ngram

给定一个包含VARCHAR排序规则的utf8mb4_unicode_ci中包含ngram的列:

+---------------------------+
| ngram                     |
+---------------------------+
| stack overflow            |
| stack                     |
| overflow                  |
| stack overflow protection |
| overflow protection       |
| protection                |
+---------------------------+

和一个查询:

SELECT * FROM ngrams WHERE ngram IN ('stack', 'stack overflow', 'protection', 'overflow')

给定此查询返回的行，如何才能保留返回的行中最长ngrams 的行？

在此示例中，我得到3行:stack，stack overflow和protection。

然后，我需要像这样过滤行:

我过滤掉stack，因为stack overflow存在于返回的行

中

我保留stack overflow，因为没有其他返回的行是包含stack overflow的ngram(表中有stack overflow protection，但不在返回的行中)

我也保留protection

我过滤掉overflow，因为stack overflow存在于返回的行

中


由于归类，它必须在MySQL中完成(MySQL外部的比较不会产生与MySQL中相同的结果)。 (除非我不知道某些MySQL函数允许公开字符串的整理版本。)

我可以想到以下解决方案:(sql fiddle)

SELECT  ngram
FROM    ngrams n1
WHERE   n1.ngram IN ('stack', 'stack overflow', 'protection')
AND     NOT EXISTS (
    SELECT  1
    FROM    ngrams n2
    WHERE   n2.ngram IN ('stack', 'stack overflow', 'protection')
    AND     LENGTH(n2.ngram) > LENGTH(n1.ngram)
    AND     CONCAT(' ', n2.ngram, ' ') LIKE CONCAT('% ', n1.ngram, ' %')
)

但是，它效率低下，因为将为每个匹配的ngram执行子查询。

所以我在寻找

是使此查询有效的一种方式

或一种在MySQL外部可靠地执行此操作的方法(考虑归类)

最佳答案

如果我正确理解您的逻辑，则此查询应为您提供正确的结果:

SELECT n1.ngram
FROM
  ngrams n1 LEFT JOIN ngrams n2
  ON
    n2.ngram IN ('stack', 'stack overflow', 'protection')
    AND n2.ngram LIKE CONCAT('%', n1.ngram, '%')
    AND CHAR_LENGTH(n1.ngram) < CHAR_LENGTH(n2.ngram)
WHERE
  n1.ngram IN ('stack', 'stack overflow', 'protection')
  AND n2.ngram IS NULL;

请参阅 fiddle here。但是由于我希望您的表可能有很多记录，而您的单词列表确实受到很大限制，为什么不执行实际查询之前从该列表中删除最短的ngram？我的想法是减少 list

('stack', 'stack overflow', 'protection')

至

('stack overflow', 'protection')

这个查询应该可以解决问题:

SELECT *
FROM
  ngrams
WHERE
  ngram IN (
    SELECT s1.ngram
    FROM (
      SELECT DISTINCT ngram
      FROM ngrams
      WHERE ngram IN ('stack','stack overflow','protection')
    ) s1 LEFT JOIN (
      SELECT DISTINCT ngram
      FROM ngrams
      WHERE ngram IN ('stack','stack overflow','protection')
    ) s2
      ON s2.ngram LIKE CONCAT('%', s1.ngram, '%')
         AND CHAR_LENGTH(s1.ngram) < CHAR_LENGTH(s2.ngram)
    WHERE
      s2.ngram IS NULL
  );

是的，我要查询表ngrams两次，然后再次将结果重新连接到ngrams，因为我们必须确保最长的值实际上存在于表中，但是如果您在ngram列上具有正确的索引，则两个派生查询使用DISTINCT应该非常有效:

ALTER TABLE ngrams ADD INDEX idx_ngram (ngram);

fiddle 是here。

编辑:

正如samuil正确指出的那样，如果您只需要查找最短的ngram而不是与其关联的整个行，那么您就不需要外部查询，而只需执行内部查询即可。使用正确的索引，两个SELECT DISTINCT查询将非常有效，即使无法优化JOIN(n2.ngram LIKE CONCAT('%', n1.ngram, '%')无法利用索引)，它也将仅在一些已经过滤的记录上执行，并且应该非常快。