How to "align" 2 strings?

First let me explain what I mean by "alignment".

Let's say we have to strings : e.g. AGBCDEF ABCDIEFK

Their "alignment" would be :

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

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

Another (quite simplified) example (since I believe my question has probably something to do with NLP) :

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

How would you go about that? Any ideas (or even reference) regarding the algorithm?

I'm probably going to write this in Objective-C (or PHP), but any code would be welcome.

Answers


I think what you are looking for is longest common subsequence.


I think what you're looking for is something like minimum edit distance from natural language processing. Look at a demo of the Levenshtein distance algorithm here


Need Your Help

NoClassFoundError runtime at tomcat

java tomcat gwt vaadin m2eclipse

Java.lang.NoClassDefFoundError: com/google/gwt/event/dom/client/HasClickHandlers at java.lang.ClassLoader.defineClass1(Native Method) at ...

NetworkOnMainThreadException Even After Implementing AsyncTask

java android android-asynctask fatal-error forceclose

I'm not sure exactly what's going on here but I've implemented AsyncTask and I'm still getting a NetworkOnMainThreadException and I have no idea why.