高效的最长公共子序列算法库？ [英] efficient longest common subsequence algorithm library?

问题描述

我在找一个（空间）高效实现的LCS算法在C ++程序使用。输入是整数两个随机接入序列。
我目前使用的约LCS维基百科页面的动态规划方法。然而，有O（MN）的内存和时间的行为，并死在我与内存不足的错误较大的投入。
我已阅读有关的Hirschberg算法，从而大大提高了内存使用情况，亨特 - Szymanski的和马塞克和帕特森。既然这是不平凡实现这些我preFER试戴我的数据与现有的实现。有谁知道这样的图书馆吗？我想像，因为文字的diff工具是pretty的共同点，也应该是周围的一些开放源代码库？

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?

推荐答案

在搜索喜欢的事情，尝试scholar.google.com。这是多寻找学术著作更好。它止跌回升 http://www.biotec.icb.ufmg.br/cabi /artigos/seminarios2/subsequence_algorithm.pdf 本文档中，的最长公共子序列算法，调查。

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".

这篇关于高效的最长公共子序列算法库？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！