Talk:Levenshtein distance: Difference between revisions

==J Implementation==

 

 

<lang j>levD=: i.@-@>:@#@] ,~ >:@i.@-@#@[ ,.~ ~:/

 

''First, we setup up an matrix of costs, with 0 or 1 for unexplored cells (1 being where the character pair corresponding to that cell position has two different characters). Note that the "cost to reach the empty string" cells go on the bottom and the right, instead of the top and the left, because this works better with J's "reduce" operator.''

The J operator / inserts its verb between each item in an array, so <code>'kitten' lev 'sitting'</code> is equivalent to:

 

 

Or, breaking it down and avoiding problems with long lines:

 

<lang j>d=. 7 6 5 4 3 2 1 0

{.d NB. the first number in the final instance of d is our result

</lang>

 

So, let's take a specific example:

 

Examining this sentence, bottom up, the first thing we do is join together these two lists, as columns:

That leaves us with a sentence like:

 

 

Or, breaking it down, again:

 

<lang j>dd7=.1 0

 

So, for example, finding the value for dd4 is 2 3 given that we know that dd5 is 1 2

{. 1 3 1 2 NB. find if current character matches

1

1

2

1&{1 3 1 2 NB. retain current delete cost to be used as next substitute cost

In other words, each instance of this operation is computing the new insert and substitute costs based on the previous values. (That said, note that "insert" and "delete" are arbitrary designations -- an "insert" on the string 'kitten' will be a delete on the string 'sitting', and vice versa.)

 

 

6 5 4 3 2 2 2 2

6 5 4 3 2 1 1 1

 

Here, the rows correspond to suffixes of the string 'kitten' and the columns correspond to suffixes of the string 'sitting', and the numbers represent the edit cost of matching the two corresponding suffixes.