LCS

LCS

LCS key1 key2 [LEN] [IDX] [MINMATCHLEN min-match-len] [WITHMATCHLEN]

Доступно с версии:

7.0.0

Сложность по времени:

O(N*M), где N и M — длины s1 и s2 соответственно

Категории ACL:

@read, @string, @slow,

Команда LCS реализует алгоритм поиска наибольшей общей подпоследовательности. Обратите внимание, что это отличается от алгоритма поиска наибольшей общей подстроки, так как совпадающие символы в строке не обязаны быть смежными.

Например, наибольшая общая подпоследовательность для строк "foo" и "fao" — это "fo", так как при сканировании двух строк слева направо наибольший общий набор символов состоит из первой "f" и затем "o".

LCS очень полезен для оценки степени сходства двух строк. Строки могут представлять различные данные. Например, если две строки — это последовательности ДНК, LCS предоставит меру сходства между двумя последовательностями ДНК. Если строки представляют текст, отредактированный пользователем, LCS может показать, насколько новый текст отличается от старого и так далее.

Обратите внимание, что этот алгоритм работает за O(N*M) время, где N — длина первой строки, а M — длина второй строки. Поэтому либо запустите другой экземпляр Redis для выполнения этого алгоритма, либо убедитесь, что вы работаете со строками очень малого размера.

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

Иногда нам нужен только размер совпадения:

> LCS key1 key2 LEN
(integer) 6

Однако часто бывает полезно знать положение совпадения в каждой строке:

> LCS 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

Совпадения генерируются от последнего к первому, так как именно так работает алгоритм, и более эффективно генерировать их в таком же порядке. Вышеприведенный массив означает, что первое совпадение (второй элемент массива) находится между позициями 2-3 первой строки и 0-1 второй строки. Затем есть еще одно совпадение между 4-7 и 5-8.

Чтобы ограничить список совпадений теми, у которых минимальная длина задана:

> LCS 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

Наконец, чтобы также получить длину совпадения:

> LCS 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

Возвращаемое значение

• Без модификаторов возвращается строка, представляющая наибольшую общую подстроку.
• Когда LEN задано, команда возвращает длину наибольшей общей подстроки.
• Когда IDX задано, команда возвращает массив с длиной LCS и всеми диапазонами в обеих строках, начальным и конечным смещением для каждой строки, где есть совпадения. Когда WITHMATCHLEN задано, каждый массив, представляющий совпадение, также будет содержать длину совпадения (см. примеры).