Token filters (lowercase, stemmer, synonym) in Elasticsearch - Time & Space Complexity

Time Complexity: Token filters (lowercase, stemmer, synonym)

O(n)

Understanding Time Complexity

When Elasticsearch processes text, it changes words step-by-step using token filters like lowercase, stemmer, and synonym. Understanding how long this takes helps us know how fast searches and indexing happen.

We want to see how the time to process text grows as the text gets longer or more complex.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch analyzer using token filters.

{
  "settings": {
    "analysis": {
      "analyzer": {
        "custom_analyzer": {
          "tokenizer": "standard",
          "filter": ["lowercase", "stemmer", "synonym"]
        }
      },
      "filter": {
        "synonym": {
          "type": "synonym",
          "synonyms": ["quick,fast"]
        },
        "stemmer": {
          "type": "stemmer",
          "name": "english"
        }
      }
    }
  }
}
    

This analyzer breaks text into words, then applies lowercase, stems words to their root, and replaces synonyms.

Identify Repeating Operations

Look at what happens to each word (token) in the text.

• Primary operation: Each token passes through three filters one after another.
• How many times: Once per token in the input text.

How Execution Grows With Input

As the number of words grows, the total work grows too, because each word is processed by all filters.

Input Size (n)	Approx. Operations
10	30 (10 tokens x 3 filters)
100	300 (100 tokens x 3 filters)
1000	3000 (1000 tokens x 3 filters)

Pattern observation: The total work grows directly with the number of tokens; doubling tokens doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to process text grows in a straight line with the number of words.

Common Mistake

[X] Wrong: "Adding more filters multiplies the time complexity to something like O(n²)."

[OK] Correct: Each filter processes tokens one after another, so time grows linearly with tokens, not squared. More filters add a fixed number of steps per token, not nested loops.

Interview Connect

Knowing how token filters affect processing time helps you explain search speed and indexing performance clearly. This skill shows you understand how text analysis scales with data size.

Self-Check

What if we added a filter that compares each token to every other token? How would the time complexity change?

Practice

1.

What does the lowercase token filter do in Elasticsearch?

easy

A. Converts all tokens to lowercase letters

B. Removes stop words from the tokens

C. Finds the root form of tokens

D. Adds synonyms to tokens

Solution

1. Step 1: Understand the lowercase filter purpose

   The lowercase filter changes all tokens to lowercase to make searches case-insensitive.

2. Step 2: Compare with other filters

   Stemmer finds root words, synonym adds similar words, stop word filter removes common words. Only lowercase converts to lowercase.

3. Final Answer:

   Converts all tokens to lowercase letters -> Option A

4. Quick Check:

   Lowercase filter = converts tokens to lowercase [OK]

Hint: Lowercase filter always makes words small letters [OK]

Common Mistakes:

• Confusing lowercase with stemmer
• Thinking lowercase adds synonyms
• Mixing lowercase with stop word removal

2.

Which of the following is the correct syntax to define a synonym token filter in Elasticsearch?

{
  "filter": {
    "my_synonym": {
      "type": "synonym",
      "synonyms": ["quick,fast"]
    }
  }
}

easy

A. { "type": "stemmer", "synonyms": ["quick,fast"] }

B. { "type": "stop", "synonyms": ["quick,fast"] }

C. { "type": "synonym", "synonyms": ["quick,fast"] }

D. { "type": "lowercase", "synonyms": ["quick,fast"] }

Solution

1. Step 1: Identify the token filter type for synonyms

   The synonym filter must have "type": "synonym" to work correctly.

2. Step 2: Check the synonyms property

   The synonyms list is correctly provided as an array of strings with comma-separated words.

3. Final Answer:

   { "type": "synonym", "synonyms": ["quick,fast"] } -> Option C

4. Quick Check:

   Synonym filter syntax = type synonym with synonyms list [OK]

Hint: Synonym filter always uses type 'synonym' with synonyms array [OK]

Common Mistakes:

• Using wrong type like stemmer or lowercase
• Not providing synonyms as an array
• Misspelling 'synonym' in type

3.

Given this analyzer configuration in Elasticsearch:

{
  "analyzer": {
    "my_analyzer": {
      "tokenizer": "standard",
      "filter": ["lowercase", "porter_stem"]
    }
  }
}

What will be the output tokens for the input text "Running Runs"?

medium

A. ["run", "runs"]

B. ["running", "runs"]

C. ["Running", "Runs"]

D. ["run", "run"]

Solution

1. Step 1: Apply lowercase filter

   Input "Running Runs" becomes "running runs" after lowercase filter.

2. Step 2: Apply porter_stem filter

   Porter stemmer reduces "running" and "runs" to root "run" for both tokens.

3. Final Answer:

   ["run", "run"] -> Option D

4. Quick Check:

   Lowercase + stemmer = root forms in lowercase [OK]

Hint: Lowercase then stemmer gives root lowercase tokens [OK]

Common Mistakes:

• Ignoring stemming effect
• Not applying lowercase first
• Expecting original case tokens

4.

Identify the error in this token filter definition:

{
  "filter": {
    "my_stemmer": {
      "type": "stemmer",
      "language": "englishy"
    }
  }
}

medium

A. "type" should be "stemmer_override"

B. "language" value is misspelled; should be "english"

C. "filter" key must be inside "analyzer"

D. Missing "synonyms" array

Solution

1. Step 1: Check the "language" parameter spelling

   The language "englishy" is incorrect; the correct value is "english".

2. Step 2: Verify the stemmer type and parameters

   Type "stemmer" is correct; no synonyms needed here; filter can be defined outside analyzer.

3. Final Answer:

   "language" value is misspelled; should be "english" -> Option B

4. Quick Check:

   Stemmer language spelling must be exact [OK]

Hint: Check spelling of language names in stemmer filters [OK]

Common Mistakes:

• Using invalid language names
• Confusing stemmer with synonym filter
• Expecting synonyms in stemmer filter

5.

You want to create an analyzer that makes searches case-insensitive, finds root forms of words, and also matches synonyms like "fast" for "quick". Which token filters should you include in your analyzer?

hard

A. ["lowercase", "stemmer", "synonym"]

B. ["stop", "lowercase", "synonym"]

C. ["lowercase", "synonym"]

D. ["stemmer", "stop"]

Solution

1. Step 1: Identify filters for case-insensitivity and root forms

   Lowercase filter makes tokens lowercase; stemmer finds root forms.

2. Step 2: Add synonym filter for matching similar words

   Synonym filter adds synonyms like "fast" for "quick" to improve matching.

3. Final Answer:

   ["lowercase", "stemmer", "synonym"] -> Option A

4. Quick Check:

   Lowercase + stemmer + synonym = case-insensitive, root, and synonym matching [OK]

Hint: Combine lowercase, stemmer, and synonym filters for full matching [OK]

Common Mistakes:

• Omitting stemmer or synonym filters
• Using stop filter instead of stemmer
• Not including lowercase for case-insensitivity