3

首先让我解释一下我所说的“对齐”是什么意思。

假设我们必须字符串：例如 AGBCDEF ABCDIEFK

他们的“对齐”将是：

A - G - B - C - D -   - E - F -
A -   - B - C - D - I - E - F - K
-----------------------------------

A - ? - B - C - D - ? - E - F - ?

另一个（相当简化的）示例（因为我相信我的问题可能与 NLP 有关）：

I give Mary a kiss
I give Ann a book
----------------------
I give X a Y

你会怎么做呢？关于算法的任何想法（甚至参考）？

我可能会用 Objective-C（或 PHP）来写这个，但任何代码都会受到欢迎。

4

2 回答 2

4

我认为您正在寻找的是与自然语言处理的最小编辑距离。在此处查看Levenshtein 距离算法的演示

于 2012-04-08T18:44:13.070 回答
1

我认为您正在寻找的是最长的公共子序列。

于 2012-04-08T18:53:08.067 回答