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:

    “Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
    —The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)

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

    “... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
    —George Eliot [Mary Ann (or Marian)