Spelling Correction

The mathematical foundation for measuring lexical similarity between a misspelled query and candidate corrections.

• Levenshtein Distance: Calculates the minimum number of single-character edits (insertions, deletions, substitutions) required to transform one string into another.
• Damerau-Levenshtein Distance: Extends the basic metric by adding transposition (swapping adjacent characters) as a single operation, effectively catching errors like 'teh' for 'the'.
• Optimal String Alignment: A restricted variant that ensures no substring is edited more than once, balancing computational efficiency with accuracy.

A technique that encodes words by their pronunciation rather than their spelling, enabling the matching of queries that are spelled incorrectly but sound correct.

• Soundex: A classic algorithm that maps names to a letter-and-three-digit code based on consonant sounds, collapsing variations like 'Smith' and 'Smyth'.
• Metaphone & Double Metaphone: More sophisticated algorithms that account for English spelling inconsistencies and non-English origins, producing variable-length keys.
• Phonetic Hashing: Used to create an inverted index where a misspelled query like 'fone' can retrieve documents containing 'phone' by matching their shared phonetic hash.

A probabilistic framework that treats the user's query as a corrupted signal transmitted through a noisy channel, where the original intended word is the source.

• Bayesian Inference: The model selects the correction c that maximizes the probability P(c|q), which is proportional to the error model P(q|c) and the language model P(c).
• Error Model: Estimates the likelihood of specific typos, such as adjacent-key substitutions on a QWERTY keyboard or phonetic confusions.
• Language Model: Provides the prior probability of a word occurring in the language, ensuring that 'battery' is preferred over the technically closer but nonsensical 'batteri'.

Moving beyond isolated word correction to analyze the surrounding terms for disambiguation, resolving real-word errors that are lexically valid but semantically wrong.

• Real-Word Errors: Detecting when 'form' is typed instead of 'from'. Both are valid dictionary words, requiring syntactic context to flag the error.
• N-gram Language Models: Evaluate the probability of a candidate correction within a sequence of neighboring words to ensure grammatical coherence.
• Transformer-Based Models: Modern systems use BERT or similar architectures to perform masked language modeling, predicting the most likely word for a given position based on bidirectional context, achieving high accuracy on complex errors.

A highly efficient, dictionary-based algorithm optimized for sub-millisecond correction latency, widely used in production search engines.

• Symmetric Delete Principle: Instead of generating all possible misspellings of a dictionary word, the algorithm pre-computes all deletion variants (e.g., 'hello' -> 'helo', 'hllo', 'helo').
• Indexing Phase: The dictionary is indexed by its delete variants. A misspelled query undergoes the same deletion process, and its variants are looked up in the index.
• Performance Advantage: This approach drastically reduces the search space compared to brute-force edit distance calculations, making it ideal for autocomplete and real-time query processing.

End-to-end deep learning models that treat spelling correction as a sequence-to-sequence translation task, converting a misspelled string directly into its corrected form.

• Seq2Seq Architectures: Models based on recurrent neural networks or transformers are trained on large parallel corpora of misspelled-corrected sentence pairs.
• Character-Level Modeling: Unlike word-level approaches, these models operate on raw character sequences, allowing them to handle novel, out-of-vocabulary errors and morphological variations.
• Integration with LLMs: Large language models can perform zero-shot correction via prompting, leveraging their vast pre-trained knowledge to resolve ambiguous errors without task-specific fine-tuning.

The foundational string metric for spelling correction, calculating the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another. For example, the distance between 'kitten' and 'sitting' is 3. This metric powers the candidate generation phase of most spellcheckers, allowing the system to rank potential corrections by their edit proximity to the misspelled query.

A technique that finds strings matching a pattern approximately rather than exactly, providing typo tolerance directly within the search index. Unlike isolated pre-processing, fuzzy matching allows the engine to retrieve documents containing 'color' even when the user types 'colour'. It often uses Damerau-Levenshtein distance (which adds transposition of adjacent characters) to handle fast-fingered typing errors without requiring a separate dictionary lookup.

A query expansion method that adds words with similar pronunciation to account for 'sounds-like' spelling errors. Algorithms like Soundex and Metaphone index words by their phonetic hash, allowing a search for 'fone' to match 'phone'. This is critical for correcting errors where the user has phonetically sounded out a word but has no idea of the correct orthography, such as searching for a proper name.

The broader process of standardizing a raw query into a consistent canonical form before any expansion or retrieval occurs. This pipeline includes:

• Lowercasing all characters
• Removing diacritics (e.g., 'café' → 'cafe')
• Applying Unicode normalization (NFKC) to standardize ligatures and full-width characters Spelling correction is often a distinct, subsequent step in this normalization pipeline.

A technique that uses the user's session history, location, or profile to disambiguate spelling corrections. For example, if a user in a medical portal types 'diabetis', the context strongly suggests correcting it to 'diabetes' rather than a generic dictionary match. This prevents over-correction by grounding the spellchecker in the specific domain and intent of the search session.

The use of large language models to not just correct spelling, but to rewrite the entire query. An LLM can take a malformed input like 'speling correctoin algorthm' and generate the clean, expanded query 'spelling correction algorithm Levenshtein distance'. This moves beyond simple edit distance to a semantic understanding of what the user likely intended to research.