Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Consider the following question. I have a long selection of files (some 5,000), arranged linearly, and I want to view to what degree the files have changed between each other. For a small example, here are some (nonsensical) strings:

string1 = "i am a cheese ball";
string2 = "i am a cheese bull";
string3 = "i am a cheese frog";
string4 = "i am a cheesy frog";
string5 = "i am a cheesy frog";
string6 = "i am a cheesy curd";
stringlist = {string1, string2, string3, string4, string5, string6};

Here is how to manually get my answer, which is {1,4,1,0,4}:

list = {EditDistance[string1, string2], 
  EditDistance[string2, string3], EditDistance[string3, string4], 
  EditDistance[string4, string5], EditDistance[string5, string6]}

There must be an automated solution, however, that moves through the list and gets the EditDistance[] between each set of things (i.e. 1 to 2, then 2 to 3, then 3 to 4, then 5 to 6, etc.). Outside of a convoluted set of Do[] loops, however, I can't find the proper command. I suspect the issue is that I'm having trouble expressing mathematically what I want to do here.

share|improve this question
2  
Something like : EditDistance[Sequence @@ #] & /@ Transpose[{Most[stringlist], Rest[stringlist]}] –  b.gatessucks Jul 9 '12 at 15:08

4 Answers 4

up vote 5 down vote accepted

If you just want each sets of two following items this will do:

 EditDistance @@@ Partition[stringlist, 2, 1]

Partition[list,2,1] will split your list up into sublists each with two elements and one overlapping, then it's just a matter of getting EditDistance applied to each set, which could be done using EditDistance[#[[1]],#[[2]]]&/@list, but the above is much more elegant using the shorthand for Apply[] "@@@" Which replaces heads at level 1 with the function being applied.

For kicks, if you wanted to compare any two two element subset of the given strings, then of cause presentation become a bit more of an issue but this would give you a nice list:

 {#1 -> EditDistance@## -> #2} & @@@ Subsets[stringlist, {2}] // Grid

(*=>
"i am a cheese ball" -> 1 -> "i am a cheese bull"
"i am a cheese ball" -> 4 -> "i am a cheese frog"
"i am a cheese ball" -> 5 -> "i am a cheesy frog"
"i am a cheese ball" -> 5 -> "i am a cheesy frog"
"i am a cheese ball" -> 5 -> "i am a cheesy curd"
"i am a cheese bull" -> 4 -> "i am a cheese frog"
"i am a cheese bull" -> 5 -> "i am a cheesy frog"
"i am a cheese bull" -> 5 -> "i am a cheesy frog"
"i am a cheese bull" -> 4 -> "i am a cheesy curd"
"i am a cheese frog" -> 1 -> "i am a cheesy frog"
"i am a cheese frog" -> 1 -> "i am a cheesy frog"
"i am a cheese frog" -> 5 -> "i am a cheesy curd"
"i am a cheesy frog" -> 0 -> "i am a cheesy frog"
"i am a cheesy frog" -> 4 -> "i am a cheesy curd"
"i am a cheesy frog" -> 4 -> "i am a cheesy curd"
*)
share|improve this answer
    
+1 - the results are already flowing out. And thanks for that extra addition, I could see that being very helpful. –  programming_historian Jul 9 '12 at 16:04

For fun, here's another approach using ListCorrelate:

ListCorrelate[{1, 1}, stringlist, {1, -1}, {}, ##2 &, EditDistance]
(* {1, 4, 1, 0, 4} *)
share|improve this answer
    
Thanks for the extra approach, it's always great to add another command to my toolkit. –  programming_historian Jul 9 '12 at 16:04

Here are some other ways.

Usually fastest:

MapThread[EditDistance, {Most@#, Rest@#}] & @ stringlist

Inner[EditDistance, Most@#, Rest@#, List] & @ stringlist

PartitionMap may be more memory efficient:

Developer`PartitionMap[EditDistance @@ # &, stringlist, 2, 1]
share|improve this answer
    
I like the MapThread solution. –  TomD Jul 9 '12 at 18:44
MatrixForm @ Outer[EditDistance, stringlist, stringlist]

Note since EditDistance is a metric, the resulting "similarity" matrix is symmetric.

Ps, I don't believe for a second that there's a unique concept of edit distance. I'm surprised EditDistance accepts no options. In general definitions of metric abound, see Deza & Deza's Dictionary of Distances, 2006

share|improve this answer
    
I was similarly surprised (even Levenschtein distance, which the documentation quotes, is a bit different at least in the courses I've taken). This'll do for a quick and dirty solution though, but yes, too bad there are no options... –  programming_historian Jul 9 '12 at 23:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.