4

好的，这就是我想要做的：

获取两个以上的字符串并“对齐”它们（没有 DNA/RNA 序列等，只是常规字符串，每个字符串都不像 1000 个项目）

我已经完成了一些成对对齐（对齐两个字符串）的工作，但是当我尝试对齐多个字符串时，“间隙”给我带来了一些问题。

示例（我目前正在测试的一个）：

ABCDEF
ABGHCEEF
AJKLBCDYEOF

AB--CDEF
ABGHCEEF
=======================
AB--C-EF

A-B--C--E-F
AJKLBCDYEOF
=======================
A----C--E-F

还有另一个（更具说明性的）示例：

http://nest.drkameleon.com
http://www.google.com
http://www.yahoo.com

http://nest.drkameleon.com
http://-www.--google--.com

=======================
http://----.------le--.com

http://----.------le--.com
http://-www.-----yahoo.com

=======================
http://----.----------.com

我目前在做什么：

  • 对字符串进行排序（较长的字符串在列表中排在第一位）
  • 对齐第一对：AB 并得到结果（比方说R1）
  • 然后对齐第二对：R1和C（结果R2）
  • 然后对齐第三对：R2和D
  • 等等...

那么你的想法是什么？我怎么能去呢？有没有更好的办法？（当然，必须有……）

我宁愿在 Perl/Python 或类似的东西中这样做，但是任何类型的代码/参考都会受到欢迎！:-)

4

2 回答 2

1

我认为您可以将此问题转换为更一般的字符串差异问题而不是字符串对齐问题。考虑如何使用 GNUdiff来查找两个文件之间的差异，并使用与执行 N-way 相同的算法diff。

我不确定这种方法的时间/内存复杂性是否符合您的需求，但您至少可以这样考虑问题。

于 2012-04-09T13:18:19.577 回答
1

有一种基于 Levenshtein 算法的算法来计算最长的公共序列，带有可选的空格。不确定这是否有帮助。

于 2012-04-09T15:46:38.963 回答