Calculate the difference between 2 string of words.

Hello!
I need help from you guys. I'm pretty new in Lisp. I have to find any differences between two string of words, say
string1 = "he sell me books"
string2 = "he sells me his book"

Then I have to show that between string1 and string2, the difference is
i) "sell" in string1 and "sells" in string2
ii) blank in string1 and "his" in string2
iii) "books" in string1 and "book" in string2.

Any idea? By the way, I manage to find the difference between two strings if the length of both string are equal. But I got stuck when both lengths are unequal. Please help me.

Thanks!
Liza

This is not a Lisp question, this is an algorithm question. Try to first understand the problem independently of the programming language, and then ask again if you have problems with implementation. What is even your problem domain? Except rather obviously 'homework'. Example given indicates natural language processing of some sorts, which cannot be solved without strong constraints on the input, on which the solution would strongly depend.

I think this is mainly solved with the set functions, like set-difference, member, and subsetp and perhaps intersection.

liza wrote:Hello!
I need help from you guys. I'm pretty new in Lisp. I have to find any differences between two string of words, say
string1 = "he sell me books"
string2 = "he sells me his book"

Then I have to show that between string1 and string2, the difference is
i) "sell" in string1 and "sells" in string2
ii) blank in string1 and "his" in string2
iii) "books" in string1 and "book" in string2.

Any idea? By the way, I manage to find the difference between two strings if the length of both string are equal. But I got stuck when both lengths are unequal. Please help me.

Thanks!
Liza

This is called a Levenstein distance (or 'edit distance'). see http://en.wikipedia.org/wiki/Levenshtein_distance

I guess I should modify my suggestion since the set functions I mentioned works on lists. I suppose a short cut would be to create a function that convert your character objects into lists, use the set functions, and then convert them back into strings when you are done with everything and have to print the output. However, this short cut is pretty inefficient. If someone says something about that and that you should work directly with vectors/arrays, you can always just accuse them of being a premature optimizer.

speech impediment wrote:I think this is mainly solved with the set functions, like set-difference, member, and subsetp and perhaps intersection.

Actually, sets do not have any order associated with them, so it wouldn't serve you well to think this way. I would expect that any help that the set functions give you is purely coincidental.

speech impediment wrote:. I suppose a short cut would be to create a function that convert your character objects into lists, use the set functions, and then convert them back into strings when you are done with everything and have to print the output. However, this short cut is pretty inefficient.

It isn't in an algorithmic sense. To measure the difference between two strings you have to at least look at each element in the string, so adding a linear time step is not inefficient. In a practical sense, it is.

You need to take a step back and read some literature. Look at Dmitry's post. It is not clear from your post what you mean by difference. There are different way to measure string difference. Perhaps that wiki page will help solidify some ideas.

EDIT: I see know I wasn't even talking to the OP, sorry OP.