Redis STRALGO LCS命令与实现

Redis STRALGO LCS命令与实现

STRALGO LCS STRINGS ohmytext mynewtext"mytext"我们也可以计算两个键相对应的字符串值的lcs，通过使用keys参数，例子如下：MSET key1 ohmytext key2 mynewtextOKSTRALGO LCS KEYS key1 key2"mytext"我们也可以使用len参数只计算lcs的长度而不返回具体的lcs字符串：STRALGO LCS STRINGS ohmytext mynewtext LEN6另外，我们也可以通过idx参数得到每一个lcs字符的位置。STRALGO LCS KEYS key1 key2 IDX1) "matches"2) 1) 1) 1) (integer) 42) (integer) 72) 1) (integer) 52) (integer) 82) 1) 1) (integer) 22) (integer) 32) 1) (integer) 02) (integer) 13) "len"4) (integer) 6如上所示，字符串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 41) "matches"2) 1) 1) 1) (integer) 42) (integer) 72) 1) (integer) 52) (integer) 83) "len"4) (integer) 6这样字符串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])的较大值。综上所述，通过转换为子问题来求解，状态转移方程如下：

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

我们从上向下，从左向右填充填充动态规划表，需要注意的是边界情况。在两个前缀子串有一个为空的时候，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的过程。

其中红色代表记录当前字符到结果数组，箭头代表i和j的移动方向。Redis的lcs命令实现，就是通过以上算法实现的，具体代码和详细注释如下：

参考资料：15.4节https://redis.io/commands/stralgo

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。