I'm looking for a (space) efficient implementation of an LCS algorithm for use in a C++ program. Inputs are two random access sequences of integers.
I'm currently using the dynamic programming approach from the wikipedia page about LCS. However, that has O(mn) behaviour in memory and time and dies on me with out of memory errors for larger inputs.
I have read about Hirschberg's algorithm, which improves memory usage considerably, Hunt-Szymanski and Masek and Paterson. Since it isn't trivial to implement these I'd prefer to try them on my data with an existing implementation. Does anyone know of such a library? I'd imagine since text diff tools are pretty common, there ought to be some open source libraries around?
Asked
Active
Viewed 5,711 times
12
BuschnicK
- 5,304
- 8
- 37
- 49
-
Are you interested in the actual longest common subsequence or just its length? – IVlad Sep 07 '10 at 14:08
-
Disappointed that a few quick web searches didn't turn up anything especially useful (loads of ad hoc implementations for `char` in C, but nothing with either Hirschberg's linear-space speedup or templated on element type for C++). If you do find (or create :D) anything, please update! – j_random_hacker Sep 08 '10 at 06:04
-
Also: Not directly on-topic, but Myers had a couple of O(nd) algorithms, where d is the number of edits needed. Very nice for inputs that you expect to be similar! (I think one of these is still used in most `diff`s.) – j_random_hacker Sep 08 '10 at 06:05
-
3The best I have found so far is http://wordaligned.org/articles/longest-common-subsequence Although you have to be careful: the C++ version increments iterators past the end when performing the recursive calls. Needs fixing. Also, it does not implement the common prefix/suffix optimization. – BuschnicK Sep 08 '10 at 15:55
3 Answers
3
When searching for things like that, try scholar.google.com. It is much better for finding scholarly works. It turned up http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf this document, a "survey of longest common subsequences algorithms".
cadolphs
- 9,014
- 1
- 24
- 41
-
1Grudging +1 because the OP really wants library implementations of said algorithms, not descriptions. But probably a useful paper anyway. – j_random_hacker Sep 09 '10 at 10:42
-
Also it would be helpful to know the date of publication & other details. – j_random_hacker Sep 09 '10 at 10:45
0
Hirschberg's Algorithm embeds a javascript implementation : almost C.
Waldir Leoncio
- 10,853
- 19
- 77
- 107
user2832537
- 11
