# Obtaining EditDistance[] from a List of Strings

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.

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

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"
*)

-
+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} *)

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

DeveloperPartitionMap[EditDistance @@ # &, stringlist, 2, 1]

-
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

-
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