Redis STRALGO LCS命令與實(shí)現(xiàn)

作者： Wen Hui

轉(zhuǎn)載：中間件小哥

在 Redis 6.0-rc4版本的reiease中茧痒，我們看到 Redis支持一個(gè)新命令及其子命令： STRALO LCS, LCS是longest common subsequence（最長公共子序列）的縮寫，其定義是：一個(gè)數(shù)列{\displaystyle S}载荔，如果分別是兩個(gè)或多個(gè)已知數(shù)列的子序列内贮，且是所有符合此條件序列中最長的规脸，則{\displaystyle S}稱為已知序列的最長公共子序列沽一。例如x = [A,,B,C,B,D,A,B], y = [B,D,C,A,B,A],則序列[B,C,A]為x和y的最長公共子序列鼎兽。LCS在現(xiàn)實(shí)生活中有很多應(yīng)用答姥，例如檢測文本相似度铣除，版本控制等，在生物醫(yī)學(xué)中踢涌，lcs也被用在檢測DNA樣本的相似度。Redis的作者salvatore也在他的twitter中提到使用使用·lcs測試covid-19冠狀病毒的基因序列序宦。（https://twitter.com/antirez/status/1245448546205216777）睁壁。

STRALGO LCS命令格式如下：

STRALGO LCS [KEYS ...] [STRINGS ...] [LEN] [IDX] [MINMATCHLEN <len>] [WITHMATCHLEN]

借用官網(wǎng)的例子，如果我們計(jì)算ohmytext和mynnewtext兩個(gè)字符串的lcs,可以使用如下命令：

STRALGO LCS STRINGS ohmytext mynewtext
"mytext"

</pre>

我們也可以計(jì)算兩個(gè)鍵相對應(yīng)的字符串值的lcs互捌，通過使用keys參數(shù)潘明，例子如下：

MSET key1 ohmytext key2 mynewtext
OK
STRALGO LCS KEYS key1 key2
"mytext"

</pre>

我們也可以使用len參數(shù)只計(jì)算lcs的長度而不返回具體的lcs字符串：

STRALGO LCS STRINGS ohmytext mynewtext LEN
6

</pre>

另外，我們也可以通過idx參數(shù)得到每一個(gè)lcs字符的位置秕噪。

STRALGO LCS KEYS key1 key2 IDX

"matches"
1. 1. 1. (integer) 4
    2. (integer) 7
  2. 1. (integer) 5
    2. (integer) 8
2. 1. 1. (integer) 2
    2. (integer) 3
  2. 1. (integer) 0
    2. (integer) 1
"len"
(integer) 6

</pre>

如上所示钳降，字符串key1的值（ohmytest）和key2的值（mynewtest）的lcs結(jié)果為字符串1的4-7索引和字符串2的5-8的索引（對應(yīng)著test）和字符串1的2-3的索引和字符串2的0-1的索引（對應(yīng)著my）。因?yàn)橛?jì)算的時(shí)候是從后往前計(jì)算的腌巾，所以輸出的結(jié)果也是相反的遂填。

我們也可以通過提供minmatchlen參數(shù)指定最小的匹配長度，如下所示：

STRALGO LCS KEYS key1 key2 IDX MINMATCHLEN 4

"matches"
1. 1. 1. (integer) 4
    2. (integer) 7
  2. 1. (integer) 5
    2. (integer) 8
"len"
(integer) 6

</pre>

這樣字符串1的2-3的索引和字符串2的0-1的索引（對應(yīng)著my）的匹配就被過濾掉了澈蝙。

求解LCS及其長度本身是個(gè)·np-hard問題吓坚，但可以通過使用空間換時(shí)間的思想使用動(dòng)態(tài)規(guī)劃在多項(xiàng)式時(shí)間來求解。

具體思路如下灯荧，假如我們要求數(shù)組x [x1,x2,x3,x4 … xm]和數(shù)組y [y1,y2,y3,y4 … yn]的lcs長度礁击，如果xm 和yn的值相等，那么原問題便轉(zhuǎn)化為x的子數(shù)組x [x1,x2,x3,x4 … xm-1] 和y [y1,y2,y3,y4 … yn-1]的lcs長度加一逗载。相反地哆窿，如果xm 和yn的值不相等，則lcs的長度為lcs(x[x1,x2,x3,x4 … xm-1], y[y1,y2,y3,y4 … yn]) 和lcs(x[x1,x2,x3,x4 … xm], y[y1,y2,y3,y4 … yn-1])的較大值厉斟。綜上所述挚躯，通過轉(zhuǎn)換為子問題來求解，狀態(tài)轉(zhuǎn)移方程如下：

image

我們在具體實(shí)現(xiàn)時(shí)擦秽，可以通過建立動(dòng)態(tài)規(guī)劃表秧均，來存儲之前計(jì)算過的兩個(gè)前綴字串的lcs長度。例如如果我們要計(jì)算mynewtest和ohmytest的lcs長度号涯，則動(dòng)態(tài)規(guī)劃表如下：

image

我們從上向下目胡，從左向右填充填充動(dòng)態(tài)規(guī)劃表，需要注意的是邊界情況链快。在兩個(gè)前綴子串有一個(gè)為空的時(shí)候誉己，lcs的長度也為0.當(dāng)xi和yj相同時(shí)，則當(dāng)前l(fā)cs長度為左上角的方格的值加1域蜗，當(dāng)xi和yj不相同時(shí)巨双，則當(dāng)前l(fā)cs長度為左邊或右邊方格中的值的最大值噪猾。這樣，當(dāng)處理到最右下角的方格時(shí)筑累，計(jì)算出的值就為兩個(gè)字符串的lcs長度袱蜡。

接下來我們要考慮的是如果知道lcs長度的動(dòng)態(tài)規(guī)劃表，怎樣來得到lcs呢慢宗？我們可以從后往前查找坪蚁，如果當(dāng)前位置i，j滿足xi 等于yj時(shí)镜沽，記錄當(dāng)前值到result數(shù)組里敏晤，并將i和j各減一。如果當(dāng)前位置xi和yj不相等缅茉，則查找動(dòng)態(tài)規(guī)劃表嘴脾，如果lcs（i-1，j）大于lcs（i蔬墩，j-1）時(shí)译打，i減一，反之j減一拇颅。重復(fù)以上過程直到i或j有一個(gè)為零為止扶平。下表記錄了計(jì)算lcs的過程。

image

其中紅色代表記錄當(dāng)前字符到結(jié)果數(shù)組蔬蕊，箭頭代表i和j的移動(dòng)方向结澄。

Redis的lcs命令實(shí)現(xiàn)，就是通過以上算法實(shí)現(xiàn)的岸夯，具體代碼和詳細(xì)注釋如下：

image

參考資料：

https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97

算法導(dǎo)論第三版 15.4節(jié)

https://redis.io/commands/stralgo