Space efficient LCS using Hirschberg's algorithm

[ggyuchive]

Search before asking

• I had searched in the issues and found no similar issues.

Motivation

In kvrocks LCS command, it uses Dynamic Programming. When two string S, T and get LCS(S, T),

• Time Complexity: O(|S||T|)
• Space Complexity: O(|S||T|)

When |S| and |T| is about 10000, it requires over 400MB.

Solution

We can reduce space complexity to O(|S|+|T|) using Hirschberg's algorithm, also it can recover LCS string.

Relevant paper: A Linear Space Algorithm for Computing Maximal Common Subsequences (Author: D.S. Hirschberg)

Are you willing to submit a PR?

• I'm willing to submit a PR!

[PragmaTwice]

I think for small strings i.e. S * T <= k, DP should be generally better with a small coefficent in time function (and more cache-friendly memory accesses).

Maybe we can use DP when the strings are short, and switch to Hirschberg for longer strings. And it would be great if we could include a benchmark for the optimization.

[ggyuchive]

Hi @PragmaTwice , thanks for comment! I agree about small length of string pair will be better to do current DP.
It will be great to add benchmark test and add boundary of |S||T|.

• If |S||T| <= k, do current DP
• If |S||T| > k, do DP with Hirschberg's algorithm

[PragmaTwice]

Looks good to me. Feel free to try and open a PR.

[Priyamanjare54]

Hello @ggyuchive, I’d like to work on this issue and submit a PR.

I plan to follow the suggested hybrid approach: using the existing DP implementation for small inputs and switching to Hirschberg’s algorithm for larger inputs, along with adding benchmarks.

Please let me know if it’s okay for me to take this up.

[ggyuchive]

Hi @Priyamanjare54 , I am working on this now.
Actually now I'm not only utilize Hirschberg algorithm, but also plan to implement and test LCS using bitset that can reduce time complexity to O(|S||T| / 64).

Time & Space complexity is below.

• LCS with DP : Time O(|S||T|), Space O(|S|+|T|)
• LCS with DP & Hirschberg : Time O(|S||T|), Space O(|S|+|T|)
• LCS with DP & Hirschberg & bitset : Time O(|S||T| / 64), Space O(2 * (|S|+|T|) / 64)