Character filters in Elasticsearch - Time & Space Complexity

Time Complexity: Character filters

O(n)

Understanding Time Complexity

When using character filters in Elasticsearch, it's important to know how the processing time changes as the input text grows.

We want to understand how the time to apply character filters scales with the size of the text.

Scenario Under Consideration

Analyze the time complexity of the following character filter configuration and usage.

PUT /my_index
{
  "settings": {
    "analysis": {
      "char_filter": {
        "my_mapping": {
          "type": "mapping",
          "mappings": ["ph=>f", "qu=>q"]
        }
      },
      "analyzer": {
        "my_analyzer": {
          "tokenizer": "standard",
          "char_filter": ["my_mapping"]
        }
      }
    }
  }
}
    

This code sets up a character filter that replaces certain letter pairs before tokenizing the text.

Identify Repeating Operations

Look at what happens when the filter runs on input text.

• Primary operation: Scanning the entire input text to find and replace matching character sequences.
• How many times: Once per character in the input, checking if a mapping applies.

How Execution Grows With Input

As the input text gets longer, the filter must check more characters for replacements.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows directly with the length of the input text.

Final Time Complexity

Time Complexity: O(n)

This means the time to apply character filters grows linearly with the input size.

Common Mistake

[X] Wrong: "Character filters run in constant time no matter how long the text is."

[OK] Correct: The filter must check each character or character pair to apply replacements, so longer text means more work.

Interview Connect

Understanding how text processing scales helps you explain performance in search systems and text analysis tasks.

Self-Check

What if the character filter used multiple mappings with overlapping sequences? How would that affect the time complexity?

Practice

1. What is the main purpose of a character_filter in Elasticsearch analyzers?

easy

A. To split text into tokens after analysis

B. To modify text before tokenizing by replacing or removing characters

C. To store documents in the index

D. To sort search results by relevance

Solution

1. Step 1: Understand character_filter role

   Character filters act on raw text before tokenization to clean or replace characters.

2. Step 2: Differentiate from other components

   Tokenizers split text into tokens, and other parts handle indexing or sorting, not character filters.

3. Final Answer:

   To modify text before tokenizing by replacing or removing characters -> Option B

4. Quick Check:

   Character filters = modify text pre-tokenizing [OK]

Hint: Character filters act before tokenizing text [OK]

Common Mistakes:

• Confusing character filters with tokenizers
• Thinking character filters sort or store data
• Assuming character filters work after tokenizing

2. Which of the following is the correct syntax to define a mapping character filter in Elasticsearch?

easy

A. "char_filter": {"my_mapping": {"type": "mapping", "mappings": ["ph=>f", "qu=>kw"]}}

B. "char_filter": {"my_mapping": {"type": "pattern_replace", "pattern": "ph", "replacement": "f"}}

C. "char_filter": {"my_mapping": {"type": "mapping", "pattern": "ph", "replacement": "f"}}

D. "char_filter": {"my_mapping": {"type": "replace", "mappings": ["ph=>f"]}}

Solution

1. Step 1: Identify correct type and keys for mapping filter

   The mapping filter uses "type": "mapping" and a "mappings" array with string replacements.

2. Step 2: Check syntax correctness

   "char_filter": {"my_mapping": {"type": "mapping", "mappings": ["ph=>f", "qu=>kw"]}} correctly uses "type": "mapping" and "mappings" with array of strings like "ph=>f".

3. Final Answer:

   "char_filter": {"my_mapping": {"type": "mapping", "mappings": ["ph=>f", "qu=>kw"]}} -> Option A

4. Quick Check:

   Mapping filter syntax = type mapping + mappings array [OK]

Hint: Mapping filters use type 'mapping' and 'mappings' array [OK]

Common Mistakes:

• Using pattern_replace keys for mapping filter
• Wrong type name like 'replace' instead of 'mapping'
• Using 'pattern' and 'replacement' keys in mapping filter

3. Given this character filter configuration:

{
  "char_filter": {
    "my_filter": {
      "type": "pattern_replace",
      "pattern": "\\d",
      "replacement": "#"
    }
  }
}

What will be the output text after applying my_filter to the input "abc123def"?

medium

A. "abc1#3def"

B. "abc123def"

C. "abc###def"

D. "abc#23def"

Solution

1. Step 1: Understand pattern_replace with pattern '\\d'

   The pattern '\\d' matches any digit character (0-9). The replacement is '#'.

2. Step 2: Apply replacement to input text

   All digits '1', '2', '3' in "abc123def" are replaced by '#', resulting in "abc###def".

3. Final Answer:

   "abc###def" -> Option C

4. Quick Check:

   Digits replaced by '#' = "abc###def" [OK]

Hint: Pattern '\d' matches all digits, replaced by '#' [OK]

Common Mistakes:

• Replacing only first digit instead of all
• Not escaping backslash in pattern
• Confusing pattern_replace with mapping filter

4. Identify the error in this character filter definition:

{
  "char_filter": {
    "bad_filter": {
      "type": "mapping",
      "mapping": ["ph=>f"]
    }
  }
}

medium

A. Character filters cannot use arrays

B. The type 'mapping' is invalid

C. The replacement string 'ph=>f' is incorrect format

D. The key should be 'mappings' not 'mapping'

Solution

1. Step 1: Check correct key for mapping filter

   The mapping filter requires the key 'mappings' (plural) for the array of replacements.

2. Step 2: Verify other parts

   Type 'mapping' is valid, and the replacement string format "ph=>f" is correct.

3. Final Answer:

   The key should be 'mappings' not 'mapping' -> Option D

4. Quick Check:

   Key name must be 'mappings' for mapping filter [OK]

Hint: Use 'mappings' key (plural) for mapping filters [OK]

Common Mistakes:

• Using 'mapping' instead of 'mappings'
• Mistaking type name
• Wrong replacement string format

5. You want to create a character filter that replaces all occurrences of 'cat' with 'dog' and removes digits from the text before tokenizing. Which configuration correctly combines these requirements?

hard

A. {
"char_filter": {
"replace_cat": {
"type": "mapping",
"mappings": ["cat=>dog"]
},
"remove_digits": {
"type": "pattern_replace",
"pattern": "[0-9]",
"replacement": ""
}
}
}

B. {
"char_filter": {
"replace_cat": {
"type": "pattern_replace",
"pattern": "cat",
"replacement": "dog"
},
"remove_digits": {
"type": "mapping",
"mapping": ["0=>", "1=>", "2=>", "3=>", "4=>", "5=>", "6=>", "7=>", "8=>", "9=>"]
}
}
}

C. {
"char_filter": {
"replace_cat": {
"type": "mapping",
"mapping": ["cat=>dog"]
},
"remove_digits": {
"type": "pattern_replace",
"pattern": "\\d",
"replacement": ""
}
}
}

D. {
"char_filter": {
"replace_cat": {
"type": "pattern_replace",
"pattern": "cat",
"replacement": "dog"
},
"remove_digits": {
"type": "pattern_replace",
"pattern": "d",
"replacement": ""
}
}
}

Solution

1. Step 1: Check replacement of 'cat' with 'dog'

   Using a mapping filter with "cat=>dog" is correct and simpler for exact string replacement.

2. Step 2: Check digit removal filter

   Removing digits with pattern_replace using pattern "[0-9]" and empty replacement is valid and concise.

3. Step 3: Verify combined configuration

   { "char_filter": { "replace_cat": { "type": "mapping", "mappings": ["cat=>dog"] }, "remove_digits": { "type": "pattern_replace", "pattern": "[0-9]", "replacement": "" } } } correctly combines a mapping filter for 'cat' and a pattern_replace filter for digits removal.

4. Final Answer:

   { "char_filter": { "replace_cat": { "type": "mapping", "mappings": ["cat=>dog"] }, "remove_digits": { "type": "pattern_replace", "pattern": "[0-9]", "replacement": "" } } } -> Option A

5. Quick Check:

   Mapping for 'cat', pattern_replace for digits removal [OK]

Hint: Use mapping for exact words, pattern_replace for patterns [OK]

Common Mistakes:

• Using pattern_replace for simple word mapping unnecessarily
• Using mapping filter to remove digits (inefficient)
• Incorrect regex patterns for digits