STRALGO LCS algo-specific-argument [algo-specific-argument ...]

用来实现基于字符串的复杂算法。目前的唯一实现是 LCS 算法(longest common subsequence(最长公共子序列))。

未来会加入更多的算法实现。STRALGO 的目标是给 Redis 使用者提供标准库里不提供的算法的实现。

第一个参数是选择使用的算法名字,目前支持一个算法,所以只能是 "LCS"。

*LCS algorithm

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

STRALGO LCS 命令实现了最长公共子序列算法。注意这个算法不同于最长公共字符串(longest common string)算法,因为它匹配的部分不需要是相邻的。

例如 "foo" 和"fao" 的 LCS 是 "fo",从左到右扫描两个要计算的字符串,最长公共字符集是,首字符 "f" 和最后一个字符 "o"。

LCS 的最大作用使计算两个字符串的相似度。字符串可以用来表示许多事情。例如两个字符串是DNA序列, LCS 可以计算出两个 DNS 序列的相似度。如果字符串用来表示一段文本,那么 LCS 可以用来查找新旧文本的差异等等。

LCS 算法的时间复杂度是 O(N*M) ,N 表示首字符串的长度,M 是第二个字符串的长度。所以最好使用独立的 Redis 实例来提供算法那计算,或者确保字符串不太长。

我们计算 ohmytext 和 mynnewtext 两个字符串的 lcs,可以使用如下命令:

> STRALGO LCS STRINGS ohmytext mynewtext
"mytext"

计算存储在key中的字符串值的 LCS :

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

使用 len 参数只计算 lcs 的长度而不返回具体的 lcs 字符串:

> STRALGO LCS STRINGS ohmytext mynewtext LEN
6

比较有用的功能是,我们也可以通过 idx 参数得到每一个 lcs 字符在原字符串中的位置:

> STRALGO LCS KEYS key1 key2 IDX
1) "matches"
2) 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
3) "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 4
1) "matches"
2) 1) 1) 1) (integer) 4
         2) (integer) 7
      2) 1) (integer) 5
         2) (integer) 8
3) "len"
4) (integer) 6

这样字符串1 的 2-3 的索引和字符串2 的 0-1 的索引(对应着 my)的匹配就被过滤掉了。

计算匹配的长度:

> STRALGO LCS KEYS key1 key2 IDX MINMATCHLEN 4 WITHMATCHLEN
1) "matches"
2) 1) 1) 1) (integer) 4
         2) (integer) 7
      2) 1) (integer) 5
         2) (integer) 8
      3) (integer) 4
3) "len"
4) (integer) 6

*返回值

对于 LCS 算法:

  • 返回最长公共子串,可以是不相邻字符串。
  • LEN 选项返回子串的长度。
  • IDX 返回子串各字符在元字符串中的位置。 WITHMATCHLEN 返回匹配部分长度,详见上例。