## Calculate the difference between 2 string of words.

Discussion of Common Lisp
liza
Posts: 1
Joined: Fri Feb 26, 2010 8:49 pm

### 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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

### Re: Calculate the difference between 2 string of words.

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.

speech impediment
Posts: 36
Joined: Mon May 04, 2009 5:19 pm

### Re: Calculate the difference between 2 string of words.

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

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

### Re: Calculate the difference between 2 string of words.

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

speech impediment
Posts: 36
Joined: Mon May 04, 2009 5:19 pm

### Re: Calculate the difference between 2 string of words.

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.

smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

### Re: Calculate the difference between 2 string of words.

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.
Last edited by smithzv on Thu Mar 04, 2010 8:36 pm, edited 1 time in total.