Levenshtein Distance - Definition

Definition

Mathematically, the Levenshtein distance between two strings is given by where

\qquad\operatorname{lev}_{a,b}(i,j) = \begin{cases} 0 &, i=j=0 \\ i &, j = 0 \text{ and } i > 0 \\ j &, i = 0 \text{ and } j > 0 \\ \min \begin{cases} \operatorname{lev}_{a,b}(i-1,j) + 1 \\ \operatorname{lev}_{a,b}(i,j-1) + 1 \\ \operatorname{lev}_{a,b}(i-1,j-1) + \end{cases} &, \text{ else} \end{cases}

Note that the first element in the minimum corresponds to deletion(from to ), the second to insertion and the third to match or mismatch, depending on whether the respective symbols are the same.

Read more about this topic:  Levenshtein Distance

Famous quotes containing the word definition:

    “I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)

    “Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.”
    —Willard Van Orman Quine (b. 1908)