Самая длинная общая подстрока MySQL

Возможно, MySQL — не самое подходящее место для реализации функций для работы со строками, и обычно нам нужны вопросы, чтобы продемонстрировать некоторые усилия над желаемым кодом. Я проявляю некоторую гибкость в этом вопросе, так как вы, по крайней мере, нашли ссылку на то, что вы пытаетесь сделать, и спросили, есть ли у MySQL собственные возможности.

Это не так.

Вы также спросили, можно ли переписать код примера для MySQL.

Это невозможно. Похоже, что он полагается на возможности, не реализованные в MySQL Server.

Однако... этот вопрос меня заинтриговал, и мне нравится делать необычные вещи в MySQL (иногда просто приятно иметь возможность что-то делать в базе данных, даже если это не обязательно самое эффективное место, а иногда, возможно, и < em>неправильное место, но все же удобное)... так что вместо душа сегодня утром я принял ванну, и за это время придумал вот что:

DELIMITER $$

DROP FUNCTION IF EXISTS `longest_common_substring` $$
CREATE FUNCTION `longest_common_substring`(short_str TEXT, long_str TEXT) RETURNS text CHARSET utf8
    NO SQL
    DETERMINISTIC
BEGIN
-- http://stackoverflow.com/questions/35545281/mysql-longest-common-substring
DECLARE short_len INT DEFAULT CHAR_LENGTH(short_str);
DECLARE long_len INT DEFAULT CHAR_LENGTH(long_str);
DECLARE swap_str TEXT;

DECLARE max_matched_len INT DEFAULT 0;
DECLARE max_at_left_marker INT DEFAULT NULL;
DECLARE max_at_match_len INT DEFAULT NULL;
DECLARE left_marker INT DEFAULT 0;
DECLARE match_len INT DEFAULT NULL;

IF short_str IS NULL OR long_str IS NULL THEN
  RETURN NULL;
ELSEIF short_str = long_str THEN
  RETURN short_str;
END IF;

IF short_len > long_len THEN
  SET swap_str = long_str;
  SET long_str = short_str;
  SET short_str = swap_str;
  SET short_len = long_len;
  SET long_len = CHAR_LENGTH(long_str);
END IF;

left_loop:
LOOP
  SET left_marker = left_marker + 1;
  IF left_marker + max_matched_len > short_len THEN
    LEAVE left_loop;
  END IF;
  SET match_len = max_matched_len;
  right_loop:
  LOOP
    SET match_len = match_len + 1;
    IF 1 - left_marker + match_len > short_len THEN
      LEAVE right_loop;
    END IF;
    IF long_str LIKE CONCAT ('%',SUBSTRING(short_str FROM left_marker FOR match_len),'%') THEN
      SET max_matched_len = match_len, max_at_left_marker = left_marker;
    ELSE
      LEAVE right_loop;
    END IF;
  END LOOP;
END LOOP;

IF (max_matched_len) THEN
  RETURN SUBSTRING(short_str FROM max_at_left_marker FOR max_matched_len);
ELSE
  RETURN NULL;
END IF;

END $$

DELIMITER ;

Кажется, он работает правильно.

mysql> SELECT longest_common_substring('Lions are growing like yellow roses on the wind','and we turn gracefully in the medieval garden of their roaring blossoms');
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| longest_common_substring('Lions are growing like yellow roses on the wind','and we turn gracefully in the medieval garden of their roaring blossoms') |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| n the                                                                                                                                                 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT longest_common_substring('die, bart, die','sideshow bob dislikes bart simpson');
+---------------------------------------------------------------------------------+
| longest_common_substring('die, bart, die','sideshow bob dislikes bart simpson') |
+---------------------------------------------------------------------------------+
|  bart                                                                           |
+---------------------------------------------------------------------------------+
1 row in set (0.01 sec)

Есть некоторые предостережения -

Если существует более одного совпадения «самой длинной» подстроки, то есть если есть два (или более) совпадения «самой длинной» подстроки одинаковой длины, первое совпадение будет возвращено.

Этот код не считает пробелы или знаки препинания менее значимыми, чем другие символы, поэтому во втором примере выше ответ фактически состоит из 5 символов, ' bart' с пробелом в начале. Возможно, подстрока с 5 символами без пробелов была бы лучшим совпадением, если бы она существовала, и этот код не нашел бы ее, поскольку используется первое совпадение, а последующие совпадения не учитываются, если они не длиннее. Его можно было бы изменить, чтобы сделать его более сложным, но это, по сути, доказательство концепции.

mysql> SELECT longest_common_substring('bart and lisa','bart or lisa');
+----------------------------------------------------------+
| longest_common_substring('bart and lisa','bart or lisa') |
+----------------------------------------------------------+
| bart                                                     |
+----------------------------------------------------------+
1 row in set (0.00 sec)

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

mysql> SELECT longest_common_substring('bart and maggie','bart or maggie');
+--------------------------------------------------------------+
| longest_common_substring('bart and maggie','bart or maggie') |
+--------------------------------------------------------------+
|  maggie                                                      |
+--------------------------------------------------------------+
1 row in set (0.00 sec)

Как это работает:

Мы принимаем два аргумента, ожидая сначала более короткую строку. Если более длинная строка идет первой, это нормально, потому что мы меняем их местами в памяти, но это стоит нам немного времени на обработку.

Затем мы перетаскиваем временную подстроку — специально созданный фрагмент короткой строки — через длинную строку, проверяя, является ли длинная строка LIKE % + наша временная подстрока + %. Если нет, переходим к следующему символу. Если это так, мы расширяем временную подстроку на 1 символ до тех пор, пока у нас больше не будет совпадения, но пока у нас было совпадение, мы сохранили его позицию и длину и использовали эту информацию в качестве последующей оптимизации, чтобы избежать ненужных сравнений, которые не может дать лучшего совпадения.

Я могу добавить это в https://github.com/sqlbot/dtsl-mysql, мою коллекцию даты, времени и функций работы со строками, как только я буду готов его выпустить.