fuzzy-autocomplete

A small autocomplete + fuzzy-search engine in Java, built from classic data structures rather than a library. Type a prefix and get the most likely completions; misspell a word and still get the right suggestions.

It exists to show the data structures doing real work:

• a trie for prefix completion,
• a bounded min-heap for top-k ranking, and
• a pruned Levenshtein trie traversal for typo tolerance.

Example

> th
  the                  1000000
  that                 100000
  this                 83333
  they                 19607
  their                17241
  there                15873

> ~adress             (fuzzy: 'adress' is a typo)
  address              (1 edit)  weight=4016
  dress                (1 edit)  weight=348

Quickstart

Requires JDK 17+. The Maven wrapper is included, so you don't need Maven installed.

git clone https://github.com/Chri2K02/fuzzy-autocomplete.git
cd fuzzy-autocomplete
./mvnw test          # build + run the test suite

Run the interactive CLI against the bundled 10k-word dictionary:

./mvnw -q exec:java
# then type a prefix, or '~word' for a fuzzy lookup

Or run one-shot queries:

# compile once, then call the CLI directly
./mvnw -q compile
java -cp target/classes com.kearns.autocomplete.cli.Main data/words.txt suggest th 5
java -cp target/classes com.kearns.autocomplete.cli.Main data/words.txt fuzzy exampel 2 5

How it works

Prefix completion. Terms are stored in a trie keyed by character. A query walks to the node for the prefix, then gathers every word in the subtree below it. Because a prefix like s can match thousands of words, the candidates are streamed through a size-k min-heap (TopKRanker) that keeps only the best k by weight — O(n log k) instead of sorting everything at O(n log n).

Fuzzy matching. Typo tolerance uses edit (Levenshtein) distance, but instead of comparing the query against every dictionary word, it walks the same trie while filling in the edit-distance dynamic-programming matrix one row per node. Every node reuses its parent's row, so a shared prefix is scored once for all the words beneath it. If the smallest value in a node's row already exceeds the edit budget, no word below can come back under budget, so the whole branch is pruned. That pruning is what keeps fuzzy lookups fast over a large dictionary.

Fuzzy results are ranked closest-first (fewest edits), then by weight — so a one-edit correction beats a two-edit one even if the latter is a more common word.

Benchmarks

Measured on JDK 21 over the bundled ~10k-word dictionary, with the simple harness in cli/Benchmark.java (JIT warm-up, then a timed batch of random queries). Numbers vary by machine; the point is the relative cost.

Operation	ns/op	throughput
suggest(prefix, k=10) — random 1–3 char prefixes	~19,000	~53k ops/sec
fuzzy(word, maxEdits=1, k=10)	~33,000	~30k ops/sec
fuzzy(word, maxEdits=2, k=10)	~157,000	~6k ops/sec

Index build: ~29 ms for ~10k terms; ~5 MB heap. Short prefixes are the expensive case for suggest because they match large subtrees; a two-edit fuzzy search is the expensive case overall because it explores more of the trie.

# reproduce
./mvnw -q compile
java -cp target/classes com.kearns.autocomplete.cli.Benchmark

Testing

./mvnw test runs the JUnit 5 suite (28 tests). The key one is a property-style cross-check: for many random dictionaries and queries, FuzzyMatcher's pruned traversal is verified to return exactly the same matches as a naive brute-force Levenshtein scan over every word. If the fast path ever disagrees with the obvious-but-slow path, the build fails.

Project layout

fuzzy-autocomplete/
  pom.xml
  data/words.txt                 # bundled corpus: "term,weight" per line
  src/main/java/com/kearns/autocomplete/
    Autocomplete.java            # public API / facade
    Trie.java                    # prefix tree
    TopKRanker.java              # bounded min-heap ranking
    FuzzyMatcher.java            # pruned Levenshtein trie traversal
    Suggestion.java              # (term, weight)
    FuzzyResult.java             # (term, weight, distance)
    cli/Main.java                # interactive + one-shot CLI
    cli/Benchmark.java           # timing harness
  src/test/java/com/kearns/autocomplete/
    ...                          # unit tests + brute-force cross-check

Data

data/words.txt is derived from a public frequency-ordered English word list; each line is term,weight, where the weight approximates usage frequency so that ranking prefers common words. The engine accepts any file in this format.

License

MIT — see LICENSE.