liveBook · Manning

Prefix search

As explained in Advanced Algorithms and Data Structures

Prefix search is an operation that retrieves all stored strings beginning with a specified prefix.

Prefix search retrieves every stored string beginning with a specified prefix. It is a natural operation for a string container and supports applications such as spell-checking and other prefix-oriented lookup tasks. section 6.1.3

A string container can expose prefix search alongside ordinary container operations:

  • insert, remove, and contains manage stored strings. section 6.1.3
  • keysStartingWith(prefix) returns all stored strings beginning with prefix. section 6.1.3
  • A trie locates the prefix endpoint, then traverses the subtree rooted there to enumerate matching keys. section 6.3.6
  • A radix trie must also handle a prefix ending inside a compressed edge; a partial match can identify a descendant subtree even without a node at the prefix endpoint. section 6.3.6

Compressed-edge matching

Suppose the requested prefix is not explicitly stored in a radix trie. If the remaining prefix fully matches the beginning of an edge, searchNodeWithPrefix returns that edge's destination and enumeration continues through its descendants; an incomplete match returns null. section 6.3.6

Table 6.1 API and contract for StringContainer (view table figure)

Abstract Data Structure: StringContainer

API

 
class StringContainer {
  insert(key)
  remove(key)
  contains(key)
  longestPrefix(key)
  keysStartingWith(prefix)
}

Contract with client

Besides all the operations of a regular, plain container, this structure allows us to search for the longest prefix of a string that is stored in it and return all the stored strings that start with a certain prefix.

Use the API contract to compare exact lookup, longest-prefix lookup, and retrieval of every key starting with a prefix. section 6.1.3

For a trie, prefix search runs in O(n + m) in the comparison table, where n is the number of returned or traversed keys and m is the average key length. Tries favor frequent prefix searches but consume memory for nodes and child references; profile alternatives when memory locality or storage costs dominate. section 6.2.7

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains trie traversal, radix-trie partial-edge matching, API operations, complexity, and memory trade-offs.
Examples
Uses a StringContainer API and a radix-trie case where the requested prefix ends inside a compressed edge.
What it assumes
Assumes familiarity with stored strings and container operations, then develops trie and radix-trie search behavior.
What you can do after
Implement prefix retrieval by locating a prefix and enumerating its descendant keys, including compressed-edge cases.
How it connects
Connects prefix search with tries, radix tries, string containers, longest-prefix search, and balanced binary search trees.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.