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

Есть ли у кого-нибудь функция MySQL для самой длинной общей подстроки (LCS)? Я нашел функцию here, но в SQL. Будучи программистом-самоучкой, я мало знаю MySQL, но работаю над проектом art-with-language.MySQL самая длинная общая подстрока

источник

2016-02-22 Rossa Urs

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

Это не так.

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

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

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

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, мою коллекцию функций даты, времени и строкой, как только я готов ее выпустить.

источник

2016-02-22 14:46:22

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

ответ

Смежные вопросы