threedaymonk/text — pull request #18 by pablorusso (2014-02-13 19:22:15+00:00)
Title: Levenshtein max distance

Diagonal index was not correctly calculated when the levenshtein matrix was not square, but this error only affected some specific scenarios, so I have fix it. (See Note 1)

Also, I have reduced the second loop when max_distance is specified, reducing algorithm order from O(n*m) to O(max_distance*m). (See Note 2)

Finally I have added tests to capture each use case: additions (start, end, middle), deletions (start, end, middle), char change and a mix of them. If you can think of any other use case to test, just tell me and I will add it.

##### Note 1: Stop calculations when diagonal value is greater or equal than max_distance

Accoding to [A Guided Tour to Approximate String Matching, Gonzalo Navarro, Dept. of Computer Science, University of Chile](http://swp.dcc.uchile.cl/TR/1999/TR_DCC-1999-005.pdf) at page 17:

>This matrix has some properties which can be easily proved by induction (see, e.g. [Ukk85a])
> and which make it possible to design better algorithms. Some of the most used are that
> the values of neighboring cells di er in at most one, and that upper-left to lower-right diagonals
> are nondecreasing."

Also, this can be demostrated using the triangle inequality rule (The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string), explaning in [wikipedia](http://en.wikipedia.org/wiki/Levenshtein_distance), as following:

```
We can divide S (S = S[0]+S[1]+...+S[n]), so:

L0 = LEV(S[0], T)
L1 = LEV(S[0]+S[1], T)
...
Ln = LEV(S[0]+S[1]+...+S[n], T)

So, based in the previously rule, for any N:

LEV(S[N],T) < LEV(S[N], S[N+1]) + LEV(T, S[N+1])

But LEV(S[N], S[N+1]) is always 1, so

LEV(S[N], T) < 1 + LEV(T, S[N+1])

and as we are using integer math, we can say that

LEV(S[N], T) <= LEV(T, S[N+1])
```

This last formula proves that Levenshtein diagonal will never go lower.

Finally, if you check [Levenshtein site](http://www.levenshtein.net/), it says (without formal demostration):

> The diagonal jump can cost either one, if the two characters in the row and column do not match
> or 0, if they do.

So diagonal increase or stays the same, but never goes lower and the implemented optimization should work.

##### Note 2: Reduce second loop when max_distance is specified

According to "Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. pp. 263–264. ISBN 0-521-58519-8.":

> The problem is to find the best global alignment subject to the added condition that the alignment
> contains at most k mismatches and spaces, for a given value k. The goal is to reduce the time
> bound for the solution from 0(nm) (based on standard dynamic programming) to 0(km).
> The basic approach is to compute the edit distance of S1 and S2 using dynamic programming
> but fill in only an 0(km)-size portion of the full table.

The key observation is the following:

> If we define the main diagonal of the dynamic programming table as the cells (i, i) for i < n < m,
> then any path in the dynamic programming table that defines a k-difference global alignment
> must not contain any cell(i, i + l) or (i, i — l) where l is greater than k. To understand this,
> note that any path specifying a global alignment begins on the main diagonal (in cell (0, 0))
> and ends on, or to the right of, the main diagonal (in cell (n, m)). Therefore, the path must
> introduce one space in the alignment for every horizontal move that the path makes off the
> main diagonal. Thus, only those paths that are never more than k horizontal cells from the
> main diagonal are candidates for specifying a k-difference global alignment.

> Therefore, to find any k-difference global alignment, it suffices to fill in the dynamic programming
> table in a strip consisting of 2k + 1 cells in each row, centered on the main diagonal. When
> assigning values to cells in that strip, the algorithm follows the established recurrence relations
> for edit distance except for cells on the upper and lower border of the strip. Any cell on the upper
> border of the strip ignores the term in the recurrence relation for the cell above it
> (since it is out of the strip); similarly, any cell on the lower border ignores the term in the recurrence
> relation for the cell to its left.

Also, in the following [stackoverflow question](http://stackoverflow.com/questions/3866249/modifying-levenshtein-distance-algorithm-to-not-calculate-all-distances) there is an implementation in JAVA.

During my tests, without the change, calling gettext:find in a big project with 10 languages, takes more than 40 mins (I interrupted it). After the changes, it finished in less than 20 mins. It is a huge performance boost.

Let me know what you think!