Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Fast String Correction with Levenshtein-Automata

This paper uses the terms descendent and stroke, and I can't find definitions for them by googling. Could you recommend a book, or page.


share|cite|improve this question
up vote 1 down vote accepted

I don’t know whether this terminology is standard, so I can’t give you a reference, but I can explain how it’s used in the paper. I think that the easiest way to explain is by an example.

Consider the words $u=$ abcde and $v=$ aebbfg; the Levenshtein distance between them is $5$, as illustrated by this sequence of edit operations:

   abde                              delete c
   abbe                              substitute b for d
   aebbe                             insert e
   aebbf                             substitute f for e  
   aebbfg                            insert g

(Other sequences of length $5$ are possible.) The letters of $v$ are of three types.

  1. Those that were in $u$ and were never changed: these are the a and the first b. These letters are the descendants of the a and b in $u$, respectively. (In the paper these letters are the ones ‘not touched by any edit operation’ in the discussion immediately following Lemma 2.0.2.)

  2. Those that are the result of substituting a letter for a letter in $u$: these are the second b and the f. These letters are the descendants of the d and e in $u$, respectively.

  3. Those that were inserted: these are the e and the g. These are not descendants of any letter of $u$.

Note also that the c of $u$ has no descendant in $v$, because it was deleted.

Now construct a bipartite graph $G(u,v)$. Its vertices are the letters of $u$ as one of the parts and the letters of $v$ as the other part. Connect a letter $x$ in $u$ to a letter $y$ in $v$ if and only if $y$ is the descendant of $x$. $G(u,v)$ is the paper’s trace representation, and a stroke in the paper’s terminology is simply one of these edges. In my example the picture looks like this:

                a e b b f g  
                |  /  | |
                a b c d e 

(I put $u$ on the bottom and $v$ on the top in order to follow the convention used in Figure 2.1 of the paper.) $G(u,v)$ has four edges; in the paper’s terminology, this trace representation has four strokes. As noted in the discussion immediately following Lemma 2.0.2, no strokes cross, each letter of $u$ that has no attached edge was deleted, and each letter of $v$ that has no attached edge was inserted.

share|cite|improve this answer
Great explanation. Thank you. (>'-')> <('-'<) ^('-')^ v('-')v <('-'<) (>'-')> ^(^-^)> – Enjoys Math Apr 9 '12 at 3:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.