Efficient Similar‑String Search in Search Engines Using Levenshtein and Damerau‑Levenshtein Automata

The article introduces the problem of fuzzy search and spelling correction in search engines, which rely on measuring string similarity using edit distances such as Levenshtein distance (LD) and Damerau‑Levenshtein distance (DLD). It explains that traditional dynamic‑programming approaches have O(m·n) complexity and are too slow for large‑scale, high‑QPS environments.

To accelerate similarity checks, the author proposes building deterministic finite automata (DFA) for a given target string a . The Levenshtein DFA represents each state as the vector of edit distances between prefixes of a and the processed prefix of a candidate string b . The initial state is {0,1,2,…,|a|} , and a state is accepting if its last element ≤ the maximum allowed edit distance (typically 1 or 2). The transition function is implemented in Java:

public static int RecurLevenshteinDistance(String a, int lenA, String b, int lenB) { ... }

public static int LevenshteinDistance(String a, String b) { ... }

By pre‑processing the target string into a DFA (O(|a|) time) and caching state transitions in a hash map, each similarity test runs in O(|b|) time, a dramatic improvement over the classic O(|a|·|b|) method.

The article then extends the approach to Damerau‑Levenshtein DFA, which must handle transposition operations. Because DLD states include both the current distance vector and the previous distance vector together with the character that caused the transition, naïve state construction would explode combinatorially. The author introduces a state‑reduction theorem (Theorem 6) that identifies when the “Damerau condition” can be safely ignored, allowing many states to be merged. The resulting State class stores m_prevDists , m_curDists , and m_prevChar , and its equals() method implements the reduction logic.

Both DFAs are built once (BuildLevenshteinDFA / BuildDamerauLevenshteinDFA) and then used to test candidate strings with a simple loop that follows cached transitions. Performance analysis shows that, after state reduction, the number of distinct states remains constant for a fixed edit‑distance bound, yielding overall linear time and modest memory usage.

Finally, the article summarizes the contributions: a novel construction algorithm for Damerau‑Levenshtein DFA, rigorous correctness proofs for both automata, and practical Java code that can be integrated into backend search systems such as Elasticsearch or Lucene. Open questions for future work include further state‑reduction techniques, integration with Finite State Transducer (FST) dictionaries, and handling of multi‑byte Unicode characters.