Understanding Advanced Search Techniques: Lexical, Phonetic, Semantic, and Synonymic Query Expansion

Introduction: The “Prashant in Search” Problem

The challenge of finding relevant search results for seemingly unrelated queries is a common problem in information retrieval. A recent example, the “Prashant vs. Krosan” meme on Swiggy’s app, perfectly illustrates this. When a user searched for “Prashant,” they were served results for “Krosan.” This scenario highlights the limitations of traditional search methods and necessitates a deeper look into advanced techniques like lexical, phonetic, semantic, and synonymic query expansion.

1. Lexical Search: The Foundation

Lexical search is the most basic form of search, relying on literal text matching.

How it Works

• Text Similarity: Documents are matched based on the exact words present in the query.
• Inverted Index: A core data structure where words are mapped to the document IDs in which they appear.
• Query Processing: For a given search query, words are looked up in the inverted index. Set operations (union, intersection) are performed on document IDs to generate a candidate list.
• Ranking: Algorithms like TF-IDF (Term Frequency-Inverse Document Frequency) or BM25 are applied to rank the candidate documents and surface the most relevant results.

Limitations of Lexical Search

While effective for exact matches, lexical search struggles with variations and contextual understanding:

• Non-existent Words: If a word in the query (e.g., “home”) is not present in the corpus, even if a synonym (e.g., “house”) is abundant, no results will be returned.
• Spelling Variations: Different spellings of the same word (e.g., “Krishna” vs. “Krisna” vs. “Krishnaa”) are treated as distinct words.
• Misspellings/Typos: Without fuzzy search capabilities, typos are not handled. Even with fuzzy search, which allows for a certain edit distance, it can lead to irrelevant matches. For instance, an edit distance of 4 for “Prashant” could match “Merchant,” “Elephant,” “Pleasant,” “Present,” “Variant,” or “Servant,” which are likely irrelevant.
• Synonyms: It fails to recognize that “car,” “vehicle,” “sedan,” or “SUV” can refer to the same concept.
• Nicknames and Aliases: “Raj,” “Raja,” “Rajesh,” or “Bitu” for the same person are not linked.
• Abbreviations: “AI” and “Artificial Intelligence” are seen as distinct terms.

2. Phonetic Search: Sound-Alike Matching

Phonetic search addresses the problem of words that sound similar but are spelled differently.

How it Works

• Pronunciation Encoding: Algorithms encode words based on their pronunciation, converting them into a standardized “root word” or key.
• Algorithms:
  • Soundex: One of the oldest phonetic algorithms.
  • Metaphone (and Double Metaphone): More advanced algorithms that aim to be more accurate than Soundex, especially for English words.
  • NIIS: A lesser-known algorithm that also converts words to phonetic roots.
• Matching: Multiple words that sound similar will be reduced to the same phonetic root word, enabling matches even with spelling discrepancies.
  • Example: “House” might be reduced to “HS” by Metaphone. “Arnold Schwarzenegger” can be searched even with misspellings because variations like “Schwarzenegger” and “Shwazeneger” might reduce to the same phonetic key.

Strengths

• No Training Data: Phonetic algorithms are rule-based and do not require any training data.
• Fast and Scalable: Computation of phonetic roots is quick, making it suitable for large datasets.
• Typo Tolerance: Excellent for handling typos or variations in spelling that preserve pronunciation.

Concerns

• Homophones: Words that sound identical but have different meanings (e.g., “night” and “knight”) will be reduced to the same phonetic root, leading to irrelevant matches. For Metaphone, both might reduce to “NTN” or “NA” for NIIS.
• Limited Scope: It only works for sound-alike words.

Prashant vs. Krosan with Phonetic Search

Applying phonetic algorithms to “Prashant” and “Krosan” reveals they do not sound similar enough:

• Metaphone: “Prashant” -> PRXNT, “Krosan” -> KRSNT. These are not the same.
• NIIS: “Prashant” -> PRASAD, “Krosan” -> CRASAD. These are also not the same. Therefore, phonetic search would not resolve the “Prashant vs. Krosan” problem.

3. Semantic Search: Understanding Meaning

Semantic search goes beyond literal text and pronunciation to understand the meaning and context of words.

How it Works

• Vector Embeddings: Words are converted into numerical vector representations (embeddings) in an N-dimensional space using models like BERT or Word2Vec.
• Training Corpus: These models are trained on large text corpora (e.g., news articles, Wikipedia) to learn the contextual relationships between words.
• Meaning-Based Matching: When a query is made, it’s also converted into a vector. The search then involves finding other vectors in the N-dimensional space that are “close” to the query vector, typically using k-Nearest Neighbors (KNN) algorithms.
• Contextual Relationships: If a model is trained on data where “house” and “home” are used in similar contexts, searching for “house” can return documents containing “home,” even if “house” isn’t explicitly in the document corpus.

Strengths

• Deep Understanding: Matches based on the meaning of words, providing highly relevant results even for novel queries.
• Contextual Relevance: Can infer relationships not explicitly present in the document corpus but learned from the training data.

Concerns

• Resource Intensive: Generating and storing vector embeddings, and performing KNN lookups, can be computationally expensive, especially at scale.
• Training Dependency: Requires a well-trained model and a relevant training corpus.

Prashant vs. Krosan with Semantic Search

In the real world, “Prashant” (a name) and “Krosan” (a food item) have no inherent semantic relationship. A general-purpose semantic model trained on news articles or Wikipedia would not establish a link between them. Thus, semantic search would also fail to solve the “Prashant vs. Krosan” problem.

4. Synonymic Query Expansion: The Solution

Given the limitations of lexical, phonetic, and semantic search for specific, domain-dependent relationships like “Prashant” and “Krosan,” synonymic query expansion emerges as the most effective solution.

How it Works

• Domain-Specific Synonyms: A predefined list or database of synonyms is maintained, often curated manually or through domain-specific knowledge. For instance, Swiggy might have explicitly defined “Prashant” as a synonym for “Krosan” once the meme gained traction.
• Query Expansion: When a user’s query contains a word with a defined synonym, the original query is expanded to include its synonyms using an OR operator.
  • Example: If a user searches for “Prashant,” and “Krosan” is a defined synonym, the internal query becomes Prashant OR Krosan.
• Execution: This expanded query is then fired against the underlying search engine (e.g., Elasticsearch), which retrieves documents containing either “Prashant” or “Krosan.”

Why it Works for “Prashant vs. Krosan”

• Explicit Mapping: It directly addresses the problem by explicitly linking two otherwise unrelated terms based on a specific, often temporary or cultural, context.
• High Relevance: Ensures that when a user searches for “Prashant,” they receive results for “Krosan” because the system has been explicitly told they are related in this context.
• Complementary: It complements other search techniques by handling edge cases and domain-specific nuances that general algorithms cannot infer.

Conclusion

Building a robust search system often requires a combination of techniques. While lexical search forms the base, phonetic search handles pronunciation variations, and semantic search understands meaning. However, for highly specific, context-dependent, or meme-driven relationships like “Prashant” and “Krosan,” synonymic query expansion is the most direct and effective approach. By understanding the strengths and limitations of each method, engineers can design search systems that deliver highly relevant results across a wide spectrum of user queries.