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:

    “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)

    “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)

    “Was man made stupid to see his own stupidity?
    Is God by definition indifferent, beyond us all?
    Is the eternal truth man’s fighting soul
    Wherein the Beast ravens in its own avidity?”
    —Richard Eberhart (b. 1904)