Building a search engine from scratch is the best way to understand the underlying data structures and algorithms that power it.
Full-text search uses text indexes to quickly find terms, with established solutions like Elasticsearch, Algolia, and newer ones like Meilisearch.
Raw text is processed through tokenization, lowercasing, stop-word removal, and stemming to create a clean set of searchable terms.
An inverted index, implemented with a hash map, provides constant-time (O(1)) lookups by mapping search tokens directly to the documents that contain them.
Prefix trees, or tries, optimize memory usage by storing common prefixes of words only once, avoiding redundant data storage.
The Levenshtein distance algorithm uses dynamic programming to calculate the "edit distance" between two strings, enabling effective typo tolerance in search queries.
Lyra is a new, open-source full-text search engine written in TypeScript that achieves microsecond search times by leveraging efficient data structures.
The Q&A covers the educational value of custom hash functions, handling acronyms versus stop words, and Lyra's current in-memory architecture.
Jobs that call for the skills explored in this talk.