NGramSearch
Compressed n-gram posting lists. The smallest index (about 7 bytes per character), about 1 s to build 1M items, and single-digit-microsecond queries. Results come back in input order with no cache.
New in 1.1 · NGramSearch · .NET 10 · Apache 2.0
Fast, low-memory substring search for .NET
FastSearch is a free, open-source C# library for case-insensitive “contains” search over in-memory collections. Index a million items in about a second with 47 MiB, then search them in microseconds.
47 MiB
Index for 1M items
~5 µs
Typical query, 1M items
~1 s
To index 1M items
15K+
NuGet downloads
Recorded v1.1 results on 999,998 nonblank passwords, .NET 10. Sequential query calls; LINQ uses parallel workers. One dependency: Pineapple (MILL5’s core utilities).
FastSearch in 30 seconds
- What it is: a C# library for case-insensitive substring search over in-memory lists of objects: autocomplete, type-ahead, filtering and lookup.
- Recommended algorithm:
NGramSearch. On 1M items it uses 47 MiB (30× less than a suffix trie), builds in about 1.2 s and averages about 5 µs per query. - NGramSearch results: each matching input position once, in input order. Concurrent searches are safe.
- Platform: .NET 10 on Windows, macOS and Linux. Free under Apache 2.0.
- Install:
dotnet add package FastSearch
Six engines. One interface.
All algorithms implement ISearch<T>, so you can swap them without changing application code.
SuffixArraySearch
A generalized suffix array with a 1/2/3-character prefix table. Fastest at handing back very broad results, which it memoizes in a bounded cache.
CharSequenceSearch
Stores a precomputed answer at every trie node, so narrow queries are the fastest of all (about 0.1 µs). Memory grows as O(N·L²): 1.5 GiB for 1M items.
HashSearch
Precomputes a hash of every substring. Query speed is similar to the trie, and it uses the most memory of any algorithm.
LinqSearch
A parallel LINQ scan over lowercased copies made at construction. It has no substring index, but retains a text snapshot that must be rebuilt when indexed data changes.
StringSearch
A single-threaded Contains scan with no index. It’s the reference that every other algorithm is tested against.
Which algorithm should I use?
| If you need… | Use |
|---|---|
| The best all-round choice: small memory, fast build, fast queries | NGramSearch |
| The fastest enumeration of very broad results (1–2 character queries over millions of items) | SuffixArraySearch |
| The lowest latency on narrow queries, and memory is no concern (small lists) | CharSequenceSearch |
| A parallel scan over a text snapshot, without a substring index | LinqSearch |
| A simple scan that reads source data on every query | StringSearch |
| Precomputed substring answers using hash lookup, when memory is no concern | HashSearch |
Benchmarks: 1 million items
Recorded v1.1 results: every algorithm uses the same 999,998 nonblank passwords on the same Apple-silicon Mac with .NET 10 and workstation GC, each in its own process with DOTNET_TieredCompilation=0. Query calls are sequential; LinqSearch uses parallel workers.
| Algorithm | Build | Index memory | Heap after queries | Random query (avg) | a (370k hits) | love (3,297) | catherine (5) |
|---|---|---|---|---|---|---|---|
| NGramSearch (new) | 1.2 s | 47.4 MiB | 47.4 MiB | 5.28 µs | 1.6 ms | 13.7 µs | 0.59 µs |
| SuffixArraySearch (new) | 0.64 s | 83.2 MiB | 120.9 MiB | 103 µs | 0.70 ms | 6.23 µs | 0.15 µs |
| CharSequenceSearch (trie) | 12.1 s | 1.54 GiB | 1.54 GiB | 1.51 µs | 1.5 ms | 13.1 µs | 0.08 µs |
| HashSearch | 20.3 s | 1.79 GiB | 1.78 GiB | 2.22 µs | 1.5 ms | 14.9 µs | 0.13 µs |
| LinqSearch | 92 ms | 78.9 MiB | 78.9 MiB | 4.0 ms | 12.3 ms | 3.2 ms | 1.8 ms |
| StringSearch (Contains) | — | 0 | 0 | 36.7 ms | 37.6 ms | 35.5 ms | 20.2 ms |
The random query is the average of 1,000 cold searches of 1–8 characters and times the Search call only. The named queries average 2,000 warm calls (20 for scans), including enumeration of every result. Heap after queries is measured after both workloads and excludes input strings. These charts reuse the recorded results; performance depends on hardware, data, queries, and cache state. Full tables for 10k, 100k and 1M items are in the README.
Searching in three lines of C#
Install the NuGet package, index your collection once, and call Search().
Algorithm specifications: NGramSearch, SuffixArraySearch, CharSequenceSearch, HashSearch, LinqSearch, StringSearch.
// 1. Install: dotnet add package FastSearch
using FastSearch;
// 2. Index your collection (one-time cost)
var names = new List<string> { "Alice", "Bob", "Catherine", "Phoenix" };
var search = new NGramSearch<string>(names);
// 3. Search: case-insensitive, input order, no duplicates
var results = search.Search("cat");
// results: ["Catherine"]
// Given your existing people collection, index several fields:
var peopleSearch = new NGramSearch<Person>(
people,
p => new[] { p.FirstName, p.LastName, p.Email }
);
using FastSearch;
// 2. Index your collection (one-time cost)
var names = new List<string> { "Alice", "Bob", "Catherine", "Phoenix" };
var search = new NGramSearch<string>(names);
// 3. Search: case-insensitive, input order, no duplicates
var results = search.Search("cat");
// results: ["Catherine"]
// Given your existing people collection, index several fields:
var peopleSearch = new NGramSearch<Person>(
people,
p => new[] { p.FirstName, p.LastName, p.Email }
);
Try the desktop sample
Load a password dataset, choose one of six search algorithms, and run a search benchmark in the .NET MAUI desktop app for Mac Catalyst and Windows.
See the README for setup and run commands.
How NGramSearch stays small and fast
It stores which items contain each short substring, compressed, instead of every possible answer.
Index short substrings
Every 1-, 2- and 3-character substring, plus every 4-character substring shared by 16 or more items, maps to the sorted list of items that contain it.
Compress the lists
Each list stores the gaps between item ids as variable-length integers (about 1–2 bytes per entry), or a bitmap for very common substrings. The index never grows after it is built.
Intersect and verify
Short queries read one list directly. Longer queries intersect the rarest lists, then check the few candidates left against a compact copy of the text.
Part of the MILL5 open-source family
FastSearch is one of many open-source .NET libraries built by MILL5 — a Boston-based Microsoft Gold Partner.
Pineapple
MILL5's core .NET utilities library — preconditions, extensions, parallelism helpers. Inspired by Google Guava. 108K+ NuGet downloads.
GitHub →M5.BloomFilter
A .NET implementation of probabilistic Bloom Filters for membership testing at scale. Includes JSON and Protobuf serialization support.
GitHub →yocto
An extremely small, low-on-ceremony, high-on-value Inversion of Control container for .NET. 42K+ NuGet downloads.
GitHub →Polygon.Net
A C# wrapper for the Polygon.io financial data API. Stocks, options, forex, and crypto market data for .NET developers.
GitHub →Cut & Move
A free macOS menu bar utility that adds real Cmd+X cut-and-move to Finder. Pure Swift, zero dependencies.
GitHub →MacEdgeLight
A stunning ambient screen-edge light for macOS. Replaces physical ring lights for streaming, video calls, and presentations. Native Swift.
GitHub →Frequently asked questions
What is FastSearch?
FastSearch is a free, open-source C# library for case-insensitive substring (contains) search over in-memory collections of objects. It provides six algorithms behind one ISearch<T> interface. The recommended one, NGramSearch, indexes 1 million items in about 1 second using 47 MiB of memory and answers typical queries in about 5 µs.
What is the fastest way to search for a substring across a large list in C#?
Build an index once instead of calling string.Contains on every item. On 1 million strings, a Contains scan takes about 37 ms per query and parallel LINQ about 4 ms. A FastSearch index answers the same queries in microseconds: about 5 µs on average with NGramSearch, and about 1.5 µs with the CharSequenceSearch suffix trie, which needs 1.5 GiB of memory to do it.
Which FastSearch algorithm should I use?
Use NGramSearch for almost everything: it has the smallest index (47 MiB for 1M items), builds in about a second, and keeps typical queries in single-digit microseconds. Use SuffixArraySearch if you mostly run 1–2 character queries over millions of items, CharSequenceSearch for the lowest latency on narrow queries over small lists, and LinqSearch for a parallel scan over a text snapshot, or StringSearch to read the source on every query.
How much memory does FastSearch use?
NGramSearch uses about 7 bytes per indexed character on lists of 100,000 items or more, and that doesn't grow as you search. For 1 million passwords (7.5 million characters) that is 47 MiB, compared with 83 MiB for SuffixArraySearch (121 MiB after the measured query workload), 1.54 GiB for CharSequenceSearch and 1.79 GiB for HashSearch.
How does NGramSearch work?
NGramSearch maps every 1-, 2- and 3-character substring (and every common 4-character substring) to a delta- and varint-compressed list of the items that contain it. Queries of up to 3 characters are answered directly from one list, already in input order. Longer queries intersect the rarest lists and verify the few remaining candidates against a compact lowercased copy of the text.
How do I install FastSearch?
Run dotnet add package FastSearch, or Install-Package FastSearch in the Visual Studio Package Manager Console, or search for FastSearch in the NuGet UI.
Which .NET versions does FastSearch support?
FastSearch 1.1 targets .NET 10, the current long-term support release. It no longer targets .NET Standard 2.1, because every .NET runtime that used it (.NET Core 3.x through .NET 9) is out of support or reaches end of support in November 2026. If you need an older runtime, use FastSearch 1.0.16.
Is FastSearch thread-safe?
Concurrent searches can share the completed indexes. Keep source objects and custom index functions safe for concurrent use: StringSearch reads them on every query, and CharSequenceSearch exact-match mode rechecks source fields. SuffixArraySearch synchronizes its result cache.
Can I search custom objects and several fields at once?
Yes. Override ToString() on your class, or pass a Func<T, string[]> that returns the strings to index for each item, such as name, email and company. With NGramSearch, matching fields return each input position once. LinqSearch can return duplicates for multiple matching fields; ordering and duplicate behavior depend on the algorithm.
Is FastSearch free and open source?
Yes. FastSearch is licensed under Apache 2.0. The source is at github.com/MILL5/FastSearch and the package is on NuGet.
Who built FastSearch?
FastSearch was built by Richard Crane, a Microsoft Most Valuable Professional (MVP) and founder of MILL5, a Boston-based Microsoft Gold Partner specializing in cloud, AI, IoT, data analytics and modern application development.
Built by Rich Crane — Microsoft MVP, MILL5.
Part of the Inventing Fire with AI initiative. The same workshop behind Video Downloader, MacEdgeLight, and Cut & Move.