Obtaining EditDistance[] from a List of Strings

Question

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.

Answer 1

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

Answer 2

For fun, here's another approach using ListCorrelate:

ListCorrelate[{1, 1}, stringlist, {1, -1}, {}, ##2 &, EditDistance]
(* {1, 4, 1, 0, 4} *)

Answer 3

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]

Answer 4

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