MySQL最長公共子字符串

Question

有沒有人有最長公共子字符串（LCS）的MySQL函數？我發現一個函數here，但在SQL中。作爲一名自學成才的程序員，我不太瞭解MySQL，但是從事與藝術相關的項目。

Answer 1

MySQL可以說並不是實現字符串操作函數的最合適的地方，通常我們需要問題來展示所需代碼的一些工作。我對這個有點靈活，因爲你至少可以找到你想要做什麼的參考，並詢問MySQL是否具有本地功能。

它沒有。

您還問過示例代碼是否可以重寫爲MySQL。

它不能。它似乎依賴於未在MySQL服務器中實現的功能。

但是......這個問題讓我很感興趣，而且我喜歡在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，這是我收集的日期，時間和字符串操作函數，一旦我準備好發佈它。