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 回答