A survey of longest common subsequence algorithms
- 8 November 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The aim of this paper is to give a comprehensive comparison of well-known longest common subsequence algorithms (for two input strings) and study their behaviour in various application environments. The performance of the methods depends heavily on the properties of the problem instance as well as the supporting data structures used in the implementation. We want to make also a clear distinction between methods that determine the actual lcs and those calculating only its length, since the execution time and more importantly, the space demand depends crucially on the type of the task. To our knowledge, this is the first time this kind of survey has been done. Due to the page limits, the paper gives only a coarse overview of the performance of the algorithms; more detailed studies are reported elsewhere.Keywords
This publication has 31 references indexed in Scilit:
- Performance analysis of some simple heuristics for computing longest common subsequencesAlgorithmica, 1994
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990
- An O(NP) sequence comparison algorithmInformation Processing Letters, 1990
- The longest common subsequence problem revisitedAlgorithmica, 1987
- Remark on the HSUDU new algorithm for the longest common subsequence problemInformation Processing Letters, 1987
- AnO(ND) difference algorithm and its variationsAlgorithmica, 1986
- New algorithms for the LCS problemJournal of Computer and System Sciences, 1984
- An information-theoretic lower bound for the longest common subsequence problemInformation Processing Letters, 1978
- A fast algorithm for computing longest common subsequencesCommunications of the ACM, 1977
- Bounds for the String Editing ProblemJournal of the ACM, 1976