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:

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)

    “Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
    —Nadine Gordimer (b. 1923)

    “One definition of man is “an intelligence served by organs.””
    —Ralph Waldo Emerson (1803–1882)