Подтвердить что ты не робот

Найти самые длинные совпадающие ngrams в MySQL

Для столбца, содержащего ngrams в параметре VARCHAR с utf8mb4_unicode_ci:

+---------------------------+
| ngram                     |
+---------------------------+
| Qaru            |
| stack                     |
| overflow                  |
| Qaru 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, потому что никакая другая возвращенная строка не является ngram, содержащей stack overflow (в таблице есть Qaru protection, но не в возвращенных строках)
  • Я продолжаю protection
  • Я отфильтровываю overflow, потому что stack overflow существует в возвращенных строках

Это должно быть сделано в MySQL из-за сопоставлений (сравнения вне MySQL не дают таких же результатов, как в MySQL). (Если я не знаю о какой-либо функции MySQL, позволяющей выставить сопоставленную версию строки.)

Я могу придумать следующее решение: (sql скрипта)

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, ' %')
)

Это неэффективно, однако, поскольку суб-запрос будет выполняться для каждой согласованной nграммы.

Итак, я ищу

  • способ сделать этот запрос эффективным
  • или способ сделать это надежно вне MySQL (с учетом сопоставлений)
4b9b3361

ОТВЕТЫ

Ответ 1

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

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;

Смотрите здесь скрипку здесь. Но так как я ожидаю, что в вашей таблице может быть много записей, в то время как ваш список слов очень ограничен, почему бы не удалить самые короткие ngrams из этого списка перед выполнением фактического запроса? Моя идея - уменьшить список

('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 здесь.

Edit:

Как правильно сказано samuil, если вам просто нужно найти кратчайшую ngram, а не все связанные с ней строки, тогда вам не нужен внешний запрос, и вы можете просто выполнить внутренний запрос. При правильном индексе два запроса SELECT DISTINCT будут очень эффективными, и даже если JOIN не может быть оптимизирован (n2.ngram LIKE CONCAT('%', n1.ngram, '%') не может использовать индекс), он будет выполняться только на нескольких уже отфильтрованных записях и должен быть достаточно быстро.

Ответ 2

Вы пытаетесь отфильтровать ngrams в самом запросе. Вероятно, более эффективно это сделать в два этапа. Начните с таблицы со всеми возможными ngrams:

CREATE TABLE original (ngram varchar(100) NOT NULL)
GO

CREATE TABLE refined (ngram varchar(100) NOT NULL PRIMARY KEY)
GO

INSERT INTO original (ngram)
SELECT DISTINCT ngram
FROM ngrams
WHERE ngram IN ('stack', 'stack overflow', 'protection')
GO

INSERT INTO refined (ngram)
SELECT ngram
FROM original

Затем удалите те, которые вы не хотите. Для каждой ngram создайте все возможные подстроки. Для каждой подстроки удалите эту запись (если она есть) из списка. Требуется несколько вложенных циклов, но если ваши ngrams содержат чрезвычайно большое количество слов, это не займет много времени.

CREATE PROCEDURE refine()
BEGIN
    DECLARE done INT DEFAULT FALSE;
    DECLARE words varchar(100);
    DECLARE posFrom, posTo int;
    DECLARE cur CURSOR FOR SELECT ngram FROM original;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

    OPEN cur;

    read_loop: LOOP
        FETCH cur INTO words;
        IF done THEN
            LEAVE read_loop;
        END IF;

        SET posFrom = 1;
        REPEAT
            SET posTo = LOCATE(' ', words, posFrom);
            WHILE posTo > 0 DO
                DELETE FROM refined WHERE ngram = SUBSTRING(words, posFrom, posTo - posFrom);
                SET posTo = LOCATE(' ', words, posTo + 1);
            END WHILE;
            IF posFrom > 1 THEN
                DELETE FROM refined WHERE ngram = SUBSTRING(words, posFrom);
            END IF;
            SET posFrom = LOCATE(' ', words, posFrom) + 1;
        UNTIL posFrom = 1 END REPEAT;
    END LOOP;

    CLOSE cur;
END

Что осталось, это таблица с самыми длинными ngrams:

CALL refine;

SELECT ngram FROM refined;

SQL Fiddle: http://sqlfiddle.com/#!2/029dc/1/1

EDIT: Я добавил индекс в таблицу refined; теперь он должен работать в O (n) времени.

Ответ 3

После этого, не глядя на другие решения, я вижу, что он похож на ваше существующее лучшее решение, но немного проще читать и, возможно, немного более эффективно;

SELECT n1.ngram
FROM ngrams n1
LEFT JOIN ngrams n2
  ON n2.ngram IN ('stack', 'stack overflow', 'protection', 'overflow')
 AND n1.ngram <> n2.ngram
 AND INSTR(n2.ngram, n1.ngram) > 0
WHERE n1.ngram IN ('stack', 'stack overflow', 'protection', 'overflow')
 AND n2.ngram IS NULL;

SQLfiddle для тестирования с.

Поскольку в строке AND n1.ngram <> n2.ngram нет вычислений, запрос должен иметь возможность использовать индексы немного более эффективно.

Ответ 4

Я думаю, вы можете использовать самостоятельное объединение на LIKE %original string% и выбирать только те строки, у которых длина ngram равна самой длинной связанной длине ngram.

SELECT n1.* FROM ngrams n1
  INNER JOIN ngrams n2 ON
    n2.ngram LIKE CONCAT('%', `n1`.`ngram`, '%')
    AND n2.ngram IN ('stack overflow', 'stack')
  WHERE n1.ngram IN ('stack overflow', 'stack')
  GROUP BY n1.ngram
  HAVING MAX(CHAR_LENGTH(n2.ngram)) = CHAR_LENGTH(n1.ngram);

Недостатком этого решения является то, что вам нужно дважды предоставить список строк.

Оказывается, вам не нужно предоставлять список дважды:

SELECT n1.*
  FROM ngrams n1
  INNER JOIN ngrams n2 ON
    n2.ngram LIKE CONCAT('%', `n1`.`ngram`, '%')
    AND n2.ngram IN ('stack overflow', 'stack')
  GROUP BY n1.ngram
  HAVING MAX(CHAR_LENGTH(n2.ngram)) = CHAR_LENGTH(n1.ngram);

Ответ 5

Эта небольшая модификация вашего запроса:

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
                            n2.ngram <> n1.ngram AND
                            n2.ngram LIKE CONCAT('% ', n1.ngram, ' %')
                   );

Должно быть довольно оптимально быстро с индексом на ngrams(ngram). Обратите внимание, что это упрощает условие like. Я не вижу причин, по которым вам следует беспокоиться о границах слов. Разве "стеки" не были бы более длинной версией "стека"? (Хотя элементы, на которые ссылаются n-граммы, могут быть словами, я связываю их с буквами, если не указано иное.)

С индексом это должно быть эквивалентно по производительности другим решениям с помощью join.

Если бы мне пришлось делать это за дваллиона раз, а таблица ngram была не слишком большой, я бы предварительно обработал ее, чтобы получить все пары "обобщений" - ngram_pairs. Это изменит значение выше на

SELECT  ngram
FROM    ngrams n1
WHERE   n1.ngram IN ('stack', 'stack overflow', 'protection') AND
        NOT EXISTS (SELECT  1
                    FROM    ngram_pairs np
                    WHERE   np.ngram1 = n1.ngram and
                            np.ngram2 in ('stack', 'stack overflow', 'protection') 
                   )

Это должно работать намного лучше, чем like с индексом на ngram_pairs(ngram1, ngram2). Ниже приведен код для генерации ngram_pairs:

create table ngram_pairs as
    select n1.ngram as ngram1, n2.ngram as ngram2
    from ngrams n1 join
         ngrams n2
         on length(n1.ngram) < length(n2.ngram) and
            n2.ngram like concat('%', n1.ngram, '%');

create index ngram_pairs_ngram1_ngram2 on ngram_pairs(ngram1, ngram2);

Ответ 6

Попробуйте этот запрос с использованием пользовательской переменной

select 
  ngram
from 
  (select 
    ngram, 
    @t:=if(@prev=rank, @t+1, 1) as num,
    @prev:=rank
  from 
    (select 
      ngram,
      @rank:=if(@prev like concat(ngram,'%'), @rank, @rank+1) as rank,
      CHAR_LENGTH(ngram) as size,
      @prev:=ngram
    from 
      tbl 
    join 
      (select 
         @prev:='', 
         @rank:=1) t 
    where 
       ngram in ('stack overflow', 'stack', 'protection')
    order by 
       rank, size desc
   )t
  join 
    (select 
       @t:=0, 
       @prev:=0) t1
    ) t 
  where 
    num =1

Fiddle

|          NGRAM |
|----------------|
| Qaru |
|     protection |

Ответ 7

Следующий запрос проверяет данные только один раз и дает правильные результаты (fiddle):

SELECT my_ngrams.ngram
  FROM (SELECT CASE WHEN @v LIKE CONCAT('%',n1.ngram,'%') THEN 1 ELSE 0 END AS ngram_match
             , @v:=concat(@v,',',n1.ngram) AS ngram_concat
             , n1.ngram
          FROM    ngrams n1, (SELECT @v := '') r
         WHERE   n1.ngram IN ('stack', 'stack overflow', 'overflow', 'protection', 'overflow protection')
      ORDER BY length(n1.ngram) DESC) my_ngrams
 WHERE my_ngrams.ngram_match <> 1
;

Однако он полагается на поведение пользовательских переменных в MySQL (http://dev.mysql.com/doc/refman/5.5/en/user-variables.html) и должен использоваться с некоторой осторожностью в качестве результат.

"Порядок по" важен для решения, поскольку это влияет на то, как оцениваемая пользователем переменная оценивается по строкам, что влияет на соответствие строк по этому случаю и затем фильтруется.

Он также объединяет все результаты для поиска для совпадений ngram перед фильтрацией, поэтому вам следует знать, что вы можете конкатенировать строку, которая больше, чем максимально допустимая MySQL (<а2 > ).

Это должно быть очень эффективным даже для больших таблиц, если столбец правильно проиндексирован.

Ответ 8

Вот альтернатива, использующая LEFT JOIN.

Таблица является самосоединенной при условии, что никакая ngram не существует, которая содержится в другой ngram, и что она не равна ngram в собственной таблице. Подзапросы были устранены, сохраняя при этом производительность.

ИЗМЕНИТЬ

Добавлены условия фильтра.

SELECT n1.ngram
FROM ngrams n1
LEFT JOIN 
(
  SELECT ngram
  FROM ngrams
  WHERE ngram IN ('stack', 'stack overflow', 'protection')) n2
ON n2.ngram like Concat('%', n1.ngram, '%') and n1.ngram <> n2.ngram
WHERE n2.ngram IS NULL
AND n1.ngram IN ('stack', 'stack overflow', 'protection');

Если вы проверяете, содержит ли только начало ngram в другой ngram, вы можете заменить условие JOIN на    ON n2.ngram like Concat(n1.ngram, '%') and n1.ngram <> n2.ngram.

Я добавил больше значений в SQL Fiddle:

  • 'xyz' (который не содержится ни в какой другой ngram)
  • "исключение" (которое является еще одним родителем "переполнения стека" )
  • "обработка исключения" (который является родительским элементом "переполнение стека"   Исключение ')

Демо-версия SQL Fiddle

Ссылка

Синтаксис JOIN в Справочном руководстве по MySQL

Ответ 9

Попробуйте следующее: Fiddle

SELECT * 
FROM   tab 
WHERE  ngram NOT IN (SELECT DISTINCT b.ngram 
                     FROM   tab a, 
                            tab b 
                     WHERE  a.ngram != b.ngram 
                            AND a.ngram LIKE Concat('%', b.ngram, '%'));

Если вы хотите включить только те из списка, которые существуют в таблице, попробуйте этот запрос: -

SELECT b.ngram ab 
FROM   (SELECT * 
        FROM   tab 
        WHERE  ngram IN ( 'stack', 'stack overflow', 'protection' )) a, 
       (SELECT * 
        FROM   tab 
        WHERE  ngram IN ( 'stack', 'stack overflow', 'protection' )) b 
WHERE  a.ngram LIKE Concat('%', b.ngram, '%') 
GROUP  BY b.ngram 
HAVING Count(*) = 1

Demo2

Ответ 10

SELECT * FROM   ngrams a WHERE  a.n NOT IN (SELECT DISTINCT a.n 
                 FROM   ngrams b
                 WHERE b.n != a.n 
                    AND b.n LIKE CONCAT('%', a.n, '%'));

Ответ 11

SELECT  a.ngram FROM ngram a  CROSS JOIN (SELECT ngram AS ngram1 FROM ngram) b 
ON b.ngram1 LIKE CONCAT('%', a.ngram, '%') 
WHERE length(a.ngram) <= length(b.ngram1) 
GROUP BY a.ngram HAVING COUNT(a.ngram) = 1 ORDER BY LENGTH(b.ngram1) DESC

Ответ 12

Попробуйте

 ORDER BY LENGTH(ngram) DESC and use LIMIT 1

EDIT:

попробуйте следующее:

  SELECT n1.ngram
  FROM ngrams n1 
  INNER JOIN ngrams n2
  ON LENGTH(n2.ngram) < LENGTH(n1.ngram)
  WHERE   n2.ngram IN ('stack', 'stack overflow', 'protection')
  GROUP BY n1.ngram