Redis STRALGO LCS命令与实现

作者: 中间件小哥 | 来源:发表于2020-08-25 12:56 被阅读0次

作者： Wen Hui

转载：中间件小哥

在 Redis 6.0-rc4版本的reiease中，我们看到 Redis支持一个新命令及其子命令： STRALO LCS, LCS是longest common subsequence（最长公共子序列）的缩写，其定义是：一个数列{\displaystyle S}，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则{\displaystyle S}称为已知序列的最长公共子序列。例如x = [A,,B,C,B,D,A,B], y = [B,D,C,A,B,A],则序列[B,C,A]为x和y的最长公共子序列。LCS在现实生活中有很多应用，例如检测文本相似度，版本控制等，在生物医学中，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]

借用官网的例子，如果我们计算ohmytext和mynnewtext两个字符串的lcs,可以使用如下命令：

STRALGO LCS STRINGS ohmytext mynewtext
"mytext"

</pre>

我们也可以计算两个键相对应的字符串值的lcs，通过使用keys参数，例子如下：

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

</pre>

我们也可以使用len参数只计算lcs的长度而不返回具体的lcs字符串：

STRALGO LCS STRINGS ohmytext mynewtext LEN
6

</pre>

另外，我们也可以通过idx参数得到每一个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结果为字符串1的4-7索引和字符串2的5-8的索引（对应着test）和字符串1的2-3的索引和字符串2的0-1的索引（对应着my）。因为计算的时候是从后往前计算的，所以输出的结果也是相反的。

我们也可以通过提供minmatchlen参数指定最小的匹配长度，如下所示：

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的索引（对应着my）的匹配就被过滤掉了。

求解LCS及其长度本身是个·np-hard问题，但可以通过使用空间换时间的思想使用动态规划在多项式时间来求解。

具体思路如下，假如我们要求数组x [x1,x2,x3,x4 … xm]和数组y [y1,y2,y3,y4 … yn]的lcs长度，如果xm 和yn的值相等，那么原问题便转化为x的子数组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])的较大值。综上所述，通过转换为子问题来求解，状态转移方程如下：

image

我们在具体实现时，可以通过建立动态规划表，来存储之前计算过的两个前缀字串的lcs长度。例如如果我们要计算mynewtest和ohmytest的lcs长度，则动态规划表如下：

image

我们从上向下，从左向右填充填充动态规划表，需要注意的是边界情况。在两个前缀子串有一个为空的时候，lcs的长度也为0.当xi和yj相同时，则当前lcs长度为左上角的方格的值加1，当xi和yj不相同时，则当前lcs长度为左边或右边方格中的值的最大值。这样，当处理到最右下角的方格时，计算出的值就为两个字符串的lcs长度。

接下来我们要考虑的是如果知道lcs长度的动态规划表，怎样来得到lcs呢？我们可以从后往前查找，如果当前位置i，j满足xi 等于yj时，记录当前值到result数组里，并将i和j各减一。如果当前位置xi和yj不相等，则查找动态规划表，如果lcs（i-1，j）大于lcs（i，j-1）时，i减一，反之j减一。重复以上过程直到i或j有一个为零为止。下表记录了计算lcs的过程。