Lightning Talk: Searching with C++ - A Fulltext Index Search Algorithm
summary
Shows a small fulltext index implemented in modern C++ using string_view and ranges, transforming a needle into n‑grams ("engrams") and mapping each gram to a multiset of index entries with offsets. Insert/remove update iterators into the original multiset; search picks the smallest posting list (36 hits) to start, converts postings to relative positions, and repeatedly intersects lists by offset to produce exact matches. Code is on the slides repo and the algorithm demonstrably returns hits for real targets like cppreference and the C++ standard.
AI-written summary · about
chapters (7)
related talks
05mFinding Strings in Large Files
57mRange Algorithms, Views and Actions: A Comprehensive Guide
01h 23mAlex Stepanov, Generic Programming in Cpp, and the STL
08mLightning Talk: Coccinelle for C++
01h 22mGlean: C++ Code Indexing at Meta
01h 23mBootstrapped by Boost
01h 01mAlgorithm Intuition (part 2 of 2)
03mKeyword Abuse