Stemming

Stemming operates by applying a series of hard-coded rules to iteratively remove prefixes and suffixes. Unlike lemmatization, it does not require a vocabulary lookup or part-of-speech tagging.

• Example: The suffix -ing is stripped, turning 'running' to 'runn'.
• Mechanism: It uses conditional statements (e.g., if word ends in 'ies' and length > 4, replace with 'i').
• Result: The output is a pseudo-root or stem, which is not guaranteed to be a valid dictionary word.

The most widely taught and implemented stemming algorithm, published by Martin Porter in 1980. It consists of five sequential phases of word reduction applied in order.

• Phase 1: Handles plurals and past participles (e.g., 'sses' → 'ss', 'ied' → 'i').
• Phases 2-4: Refine endings for 'tional', 'enci', 'izer', etc.
• Phase 5: Removes final 'e' and double letters in specific contexts.
• Trade-off: It is relatively gentle compared to the Lancaster stemmer, trading some recall for higher precision.

These are the two primary failure modes of heuristic stemmers, directly impacting search precision and recall.

• Over-Stemming: Two semantically distinct words are reduced to the same stem incorrectly. 'University' and 'Universal' both become 'univers', causing false positives.
• Under-Stemming: Morphologically related words fail to be reduced to the same stem. 'Data' and 'Datum' remain distinct, causing false negatives.
• Impact: Over-stemming destroys precision, while under-stemming destroys recall.

A string processing language and framework designed by Martin Porter for creating stemming algorithms. It is the modern evolution of the original Porter stemmer.

• Explicit Algorithm: The English Snowball stemmer is a distinct, more accurate algorithm than the classic Porter, often called Porter2.
• Multi-lingual: The framework standardizes stemmer implementations across dozens of languages, including Russian, Spanish, and Finnish.
• Logic: It uses a formalized grammar to define regions (R1, R2) within a word, ensuring suffixes are only removed if they fall within a specific linguistic zone.

A hybrid approach that combines a machine-readable dictionary with inflectional morphology rules to avoid the over-stemming common in purely rule-based systems.

• Validation: It first checks a dictionary to verify that the resulting stem is a valid word in the lexicon.
• Focus: It primarily handles inflectional variations (plurals, tense changes) rather than derivational ones (turning nouns into verbs).
• Advantage: It is much more conservative and precise than Porter, making it suitable for high-precision search applications where false positives are costly.

An extremely aggressive conflation algorithm that uses a single table of iterative rules to chop words down to their minimal length.

• Mechanism: It applies the last matching rule in a list repeatedly until no rule applies, often resulting in very short, unrecognizable stems.
• Overload: 'Maximum' and 'Maxim' both stem to 'maxim', but so might 'Maximize'.
• Use Case: It is useful in high-recall, low-precision environments where storage space is minimal and the cost of false positives is negligible.

The process of reducing a word to its canonical dictionary form (lemma) by considering its morphological analysis and part of speech. Unlike stemming, lemmatization always returns a valid word.

• Input: 'running', 'ran', 'runs'
• Output: 'run'
• Mechanism: Uses a vocabulary and morphological analysis (e.g., 'better' → 'good')
• Trade-off: More computationally expensive than stemming but yields higher precision for semantic tasks.

The process of filtering out high-frequency, low-information words from a query or document index to focus matching on more meaningful terms.

• Common stop words: 'the', 'is', 'at', 'which', 'on'
• Impact: Reduces index size and query latency by ignoring terms that appear in nearly all documents.
• Caution: Modern dense retrieval models often retain stop words as they provide crucial syntactic context for understanding intent.

A query expansion technique that adds words with identical or highly similar meanings to the original query terms to increase recall.

• Example: A query for 'car' is expanded to also match 'automobile' and 'vehicle'.
• Source: Typically driven by a thesaurus, WordNet, or learned word embeddings.
• Risk: Over-expansion can introduce noise and reduce precision if synonyms are contextually inappropriate.

The process of automatically detecting and correcting typographical errors in a search query before it is executed against an index. This is a critical pre-retrieval step.

• Mechanism: Often uses edit distance (Levenshtein) combined with a probabilistic language model.
• Example: 'recieve' → 'receive'
• Architecture: Modern systems use sequence-to-sequence neural models to correct errors contextually rather than relying solely on dictionary lookups.

A technique for finding strings that approximately match a pattern, measured by edit distance. It provides typo tolerance directly at the retrieval stage.

• Levenshtein Distance: Measures the minimum number of single-character edits (insertions, deletions, substitutions) required to change one word into another.
• Use Case: Matching 'Johnson' when the user types 'Jonson'.
• Implementation: Often built into inverted indexes via finite-state transducers to avoid exhaustive scanning.

The process of standardizing a raw query into a consistent canonical form before processing. This removes superficial differences that hinder matching.

• Steps include: Lowercasing, removing diacritics (e.g., 'café' → 'cafe'), and applying Unicode normalization (NFKC).
• Goal: Ensure that semantically identical queries with different encodings or casing produce the same results.
• Relationship: Stemming is often applied as a final step within the normalization pipeline.