levtrie

Overview ¶

Package levtrie provides a Trie implementation that supports fast searches for words within a given edit distance of a query string. Edit distance bounds are maintained during the search by simulating an NFA that accepts all words within distance d of the query string in parallel with the Trie traversal.

An example NFA is pictured below for d = 2 and the word "edit":

   ┌──┐   e  ┌──┐   d  ┌──┐   i  ┌──┐   t  ╔══╗
   |  |─────▷|  |─────▷|  |─────▷|  |─────▷║  ║
   └──┘     ◹└──┘     ◹└──┘     ◹└──┘     ◹╚══╝
    △      ╱  △      ╱  △      ╱  △      ╱  △
    │  ε,*╱   │  ε,*╱   │  ε,*╱   │  ε,*╱   │
    │    ╱    │    ╱    │    ╱    │    ╱    │
   *│   ╱    *│   ╱    *│   ╱    *│   ╱    *│
    │  ╱      │  ╱      │  ╱      │  ╱      │
   ┌──┐   e  ┌──┐   d  ┌──┐   i  ┌──┐   t  ╔══╗
   |  |─────▷|  |─────▷|  |─────▷|  |─────▷║  ║
   └──┘     ◹└──┘     ◹└──┘     ◹└──┘     ◹╚══╝
    △      ╱  △      ╱  △      ╱  △      ╱  △
    │  ε,*╱   │  ε,*╱   │  ε,*╱   │  ε,*╱   │
    │    ╱    │    ╱    │    ╱    │    ╱    │
   *│   ╱    *│   ╱    *│   ╱    *│   ╱    *│
    │  ╱      │  ╱      │  ╱      │  ╱      │
   ┌──┐   e  ┌──┐   d  ┌──┐   i  ┌──┐   t  ╔══╗
──▷|  |─────▷|  |─────▷|  |─────▷|  |─────▷║  ║
   └──┘      └──┘      └──┘      └──┘      ╚══╝

The state on the bottom left is the initial state and the double-bordered states on the far right are accepting states. *-transitions can be taken on any character and ε-transitions can be taken without consuming a character. Each transition in the NFA above corresponds to an edit operation: transitions to the right represent no edit, transitions up represent insertions, diagonal ε-transitions represent deletions and diagonal *-transitions represent substitutions.

The NFA above is a specific example from a parameterized family of Levenshtein NFAs. Creating other Levenshtein NFAs for different words or edit distances is straightfoward: add or remove columns as needed to fit the length of the word, add rows as needed to increase the edit distance, and adjust the labeled horizontal transitions to match the word.

Simulating the NFA involves keeping track of an active set of states. The active set of states is defined by the lowest active state on each diagonal and only diagonals within a sliding window of 2d + 1 possible diagonals ever contain active states during the simulation. These properties make it possible to simulate each transition of the NFA in time O(d).