php - 2つの文字列を「整列」する方法は?

Question

まず、「整列」とは何かを説明します。

文字列が必要だとしましょう: 例: 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) で書くつもりですが、どんなコードでも大歓迎です。

Answer 1

あなたが探しているのは、自然言語処理からの最小編集距離のようなものだと思います。ここでレーベンシュタイン距離アルゴリズムのデモを見てください

Answer 2

あなたが探しているのは、最長共通部分列だと思います。