Typo Correction in VDO: Enhancing Search with Lightweight Spell Checking

Building Spell Correction for Search in VDO

A recent search improvement in VDO involved adding a lightweight spell-correction layer. The core issue was clear: small typos in search terms—especially when querying metadata descriptions—often returned no useful results, even when relevant content existed in the library.

The solution was built to stay fully local and offline. VDO is a local-first desktop application, so the correction system needed to remain fast, work without network access, and integrate cleanly with the existing Electron + SQLite architecture.

This post explores:

  • the problem addressed
  • alternatives considered
  • the chosen design
  • implementation rationale
  • added optimizations
  • scalability observations
  • potential future improvements

The Problem

VDO supports search across multiple data types:

  • video titles
  • file names
  • tags
  • metadata descriptions
  • playlists and collections

The issue appeared most often during metadata searches. A minor spelling mistake in a movie title, topic, or descriptive term could cause the system to return zero results, even when matching content was present.

Example:

  • Expected term: constantine
  • Typed term: contsenine

Standard metadata lookup would fail despite the intended record existing.

The goal was practical rather than perfect: give users a strong chance of finding the right metadata result even after a small spelling error.

Design Constraints

Several practical constraints shaped the approach:

1. Local-first requirement

The solution could not rely on any network service or external API. Everything needed to function fully offline.

2. Interactive performance

Search runs frequently with quick-response expectations. Correction logic could not introduce noticeable delay on every keystroke.

3. Domain-specific vocabulary

The searchable terms come from titles, descriptions, tags, and playlist labels. A generic dictionary or massive language model was unnecessary; the system only needed to work well with VDO’s own data.

4. Maintainability

The implementation had to fit naturally into the existing service structure and remain easy to understand and evolve.

Alternatives Considered

Several common approaches to typo tolerance were evaluated before selecting the final design.

1. Brute-force edit-distance comparison

Build a full vocabulary of terms and compare each query token against every vocabulary entry using edit distance.

Why it was not chosen: Performance would degrade linearly with vocabulary size. With frequent searches, this cost became unacceptable.

2. Trie-based approximate matching

Build a trie (prefix tree) and perform fuzzy matching on it.

Why it was not chosen: While good for prefix lookups, approximate matching in a trie added more complexity than the use case required.

3. Phonetic algorithms (e.g., Soundex)

Use pronunciation-based matching.

Why it was not chosen: VDO’s vocabulary includes proper nouns, media titles, technical terms, and custom tags. Phonetic methods do not handle this mixed content as effectively as pure textual similarity.

4. N-gram candidate generation + edit-distance reranking (Chosen approach)

Extract and normalize terms from searchable content, build a trigram index, generate candidate terms via trigram overlap for misspelled queries, then rerank the shortlist using normalized edit distance.

This approach provided the best balance of simplicity, performance, correction quality, and scalability for a local desktop application.

Core Architecture

The solution separates concerns into two layers:

  1. Vocabulary preparation and persistence
  2. In-memory correction engine at query time

This separation improves both performance and code clarity.

Building the Search Vocabulary

Rather than using a generic dictionary, the vocabulary is derived directly from VDO’s content:

  • video titles
  • metadata descriptions
  • tag labels
  • playlist labels

This domain-specific vocabulary makes corrections far more relevant to actual user searches.

Normalization Process

Terms are processed by:

  • lowercasing
  • trimming and cleaning punctuation
  • splitting into tokens
  • removing stop words and numeric-only tokens
  • enforcing reasonable length limits
  • deduplicating

The resulting vocabulary is stored in a dedicated SQLite table. This avoids rebuilding the full list on every app launch and keeps initialization fast.

The Typo-Correction Engine

At runtime, an in-memory engine is initialized from the persisted vocabulary. It maintains:

  • a set of normalized terms for fast exact lookups
  • a trigram index (trigram → list of term IDs)

Why trigrams?
Similar words share many overlapping 3-character slices, even with minor typos. This enables efficient candidate filtering without scanning the entire vocabulary.

Query-Time Flow

  1. Run the normal metadata search first.
  2. If results are found, return them immediately.
  3. If no results are returned, activate typo correction:
    • correct each token independently
    • reconstruct the query with corrected terms
    • rerun the metadata search

Typo correction serves strictly as a fallback, preserving full performance for correct queries.

Candidate Selection Process

A two-stage pipeline keeps the process efficient:

Stage 1: Trigram-based filtering

  • Generate trigrams from the misspelled token
  • Retrieve candidate terms that share trigrams
  • Retain only those with sufficient overlap

Stage 2: Edit-distance reranking

  • Score remaining candidates using normalized edit distance (or Levenshtein similarity)
  • Select the best match only if it exceeds a minimum confidence threshold

If no candidate meets the threshold, no correction is applied. This prevents overconfident or incorrect substitutions.

Why This Design Was Selected

The trigram + edit-distance approach delivers strong practical benefits for VDO:

  • Lightweight: No external dependencies or cloud services.
  • Domain-aware: Corrections are tuned to actual content in the library.
  • Fast: Expensive work only occurs on failed searches.
  • Maintainable: Clean separation between vocabulary building, persistence, and runtime usage.
  • Scalable: Trigram indexing avoids full vocabulary scans.

Key Optimizations

Several refinements were added during implementation:

  • Fallback-only activation: Normal search runs first; correction activates only when needed.
  • Aggressive vocabulary filtering: Stop words, short/long tokens, and duplicates are removed early to reduce size and noise.
  • Unique trigrams: Repeated trigrams within a single term are stored only once.
  • Overlap and score thresholds: Weak matches are filtered before expensive scoring.
  • Lazy initialization: The in-memory engine loads once and stays resident until the vocabulary changes.
  • Separated rebuild/read paths: Vocabulary rebuilds write to SQLite; runtime only reads the saved data.

Scalability and Tradeoffs

Query-time performance remains strong because:

  • Exact lookups are O(1)
  • Trigram filtering keeps candidate lists small
  • Edit-distance scoring runs only on shortlists

Build-time cost involves scanning searchable content, which is acceptable when triggered only on meaningful data changes.

The approach intentionally prioritizes practicality over perfection. It handles common typos effectively while staying lightweight and offline. It does not attempt semantic search, grammar correction, or full phrase-level understanding.

Future Improvements

Potential enhancements include:

  • Batched database reads during vocabulary preparation
  • Debounced rebuild scheduling for burst updates
  • Source tracking or reference counting for safe partial rebuilds
  • Caching of common correction results
  • Phrase-aware correction for multi-word queries

Final Thoughts

The typo-correction feature in VDO solves a concrete user problem: small typing mistakes should not hide relevant content. By using a trigram-indexed vocabulary with edit-distance reranking, the system achieves reliable corrections while respecting the constraints of a local-first desktop application.

The result is a noticeable improvement in search quality without added complexity or performance overhead in the common case. For VDO, this represents an effective and balanced solution.