# FastSearch

> FastSearch is a free, open-source C# library for fast, low-memory, case-insensitive substring ("contains") search over in-memory collections of objects. Its recommended algorithm, NGramSearch, indexes 1 million items in about 1 second using 47 MiB of memory and answers a typical query in about 5 µs. It targets .NET 10, is licensed under Apache 2.0, and is published on NuGet as `FastSearch`. Built by Microsoft MVP Richard Crane at MILL5.

## About

- **Name:** FastSearch
- **Version:** 1.1.3
- **Platform:** .NET 10 (`net10.0`) on Windows, macOS and Linux. Version 1.1 drops .NET Standard 2.1; use 1.0.16 for older runtimes.
- **Price:** Free, open source (Apache 2.0)
- **Language:** C#
- **Install:** `dotnet add package FastSearch`
- **NuGet:** https://www.nuget.org/packages/FastSearch
- **Repository:** https://github.com/MILL5/FastSearch
- **Website:** https://mill5.github.io/FastSearch/
- **Author:** Richard Crane (Microsoft MVP, Founder of MILL5)
- **MVP profile:** https://mvp.microsoft.com/en-US/MVP/profile/10ce0bc0-7536-43f6-b28c-e9601a4a0d0d
- **MILL5:** https://mill5.com
- **Podcast:** *Inventing Fire with AI* — https://inventingfirewith.ai
- **Support:** rich@mill5.com
- **Last updated:** 2026-10-12

## Quick answer: which algorithm should I use?

- **NGramSearch (recommended):** the best all-round choice, with the smallest substring index in the measured workload, a fast build and fast queries.
- **SuffixArraySearch:** the fastest enumeration of very broad results (1–2 character queries over millions of items).
- **CharSequenceSearch:** the lowest latency on narrow queries, when memory is no concern (small lists).
- **LinqSearch:** a parallel scan over a lowercased text snapshot; rebuild when indexed data changes.
- **StringSearch:** a direct scan that reads the source and indexed fields on every query.
- **HashSearch:** precomputed substring answers using hash lookup, at high memory cost.

## Algorithms

All six algorithms implement `ISearch<T>` (`ICollection<T> Search(string? search)`). Results are case-insensitive.

### NGramSearch (new in 1.1, recommended)
Every distinct 1-, 2- and 3-character substring of an item, plus every 4-character substring shared by 16 or more items, maps to a sorted list of item ids. The lists are delta + varint compressed (about 1–2 bytes per entry), or stored as bitmaps when that is smaller. Queries of up to 3 characters are answered from one list: no sort, no de-duplication, no cache, and a lazy read-only result whose Count is known up front. Longer queries intersect the rarest lists and verify the remaining candidates against a compact lowercased copy of the text. Results are in input order with no duplicates. Memory is about 7 bytes per indexed character (on 100k+ items) and doesn't grow with queries.

### SuffixArraySearch (new in 1.1)
A generalized suffix array with a 1/2/3-character prefix table, plus binary search for longer queries. Memory is O(N·L). Broad results are memoized in a cache capped at one reference per indexed character. Results are in input order.

### CharSequenceSearch
A suffix trie with a precomputed result list at every node. Fastest for narrow queries, but memory is O(N·L²).

### HashSearch
A precomputed hash of every substring. Speed is similar to the trie, and it uses the most memory.

### LinqSearch
A parallel LINQ scan over lowercased copies of the strings, with no index.

### StringSearch
A single-threaded `string.Contains` scan with no index. Used as the correctness baseline.

## Benchmarks (999,998 nonblank passwords, approximately 7.5 M characters, .NET 10)

| Algorithm | Build | Index memory | Heap after queries | Random query avg | `a` (370k hits) | `love` (3,297) | `catherine` (5) |
|---|---:|---:|---:|---:|---:|---:|---:|
| NGramSearch | 1.2 s | 47.4 MiB | 47.4 MiB | 5.28 µs | 1.6 ms | 13.7 µs | 0.59 µs |
| SuffixArraySearch | 0.64 s | 83.2 MiB | 120.9 MiB | 103 µs | 0.70 ms | 6.23 µs | 0.15 µs |
| CharSequenceSearch | 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 | — | 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. Query calls are sequential; LinqSearch uses parallel workers. Heap excludes input strings and is measured after both workloads. These are the recorded v1.1 results on an Apple-silicon Mac with workstation GC and DOTNET_TieredCompilation=0, not new measurements; hardware, data and query distribution affect the results.

## How to use

```csharp
// dotnet add package FastSearch
using FastSearch;

var search = new NGramSearch<Customer>(customers, c => new[] { c.Name, c.Email });
ICollection<Customer> hits = search.Search("phoe"); // case-insensitive, input order, no duplicates
```

Items are indexed by `ToString()` unless you pass a `Func<T, string[]>` that returns the strings to index for each item. The indexed algorithms capture text at construction; rebuild when source items or indexed fields change. LinqSearch also captures text even though it has no substring index. StringSearch reads its retained source on each call, so callers must keep that source and the index function safe during concurrent use. NGramSearch and SuffixArraySearch preserve input position order; do not assume that every algorithm has the same ordering or duplicate behavior for multiple indexed fields.

## Use cases

- **Autocomplete / type-ahead search** in web, desktop, or mobile applications
- **Password search / breach checking** against large password lists
- **Name lookup** across employee directories, contact lists, CRM systems
- **Product search** in e-commerce catalogs
- **Log searching** across application log entries
- **Any scenario** requiring fast substring matching over in-memory collections

## Dependencies

- [Pineapple](https://github.com/MILL5/pineapple) (1.0.41) — MILL5's core .NET utilities library

## Related MILL5 projects

- [Pineapple](https://github.com/MILL5/pineapple) — Core .NET utilities (preconditions, extensions, parallelism)
- [yocto](https://github.com/MILL5/yocto) — Tiny IoC container for .NET
- [M5.BloomFilter](https://github.com/MILL5/M5.BloomFilter) — Probabilistic Bloom Filters for .NET
- [Polygon.Net](https://github.com/MILL5/Polygon.Net) — C# wrapper for Polygon.io financial data API

## Other projects by the author

- [Cut & Move](https://github.com/ChiefInnovator/cutandmove) — Free macOS menu bar utility that adds Cmd+X cut-and-move to Finder
- [MacEdgeLight](https://github.com/ChiefInnovator/macedgelight) — Ambient screen-edge light app for macOS

## Docs

- [README](https://github.com/MILL5/FastSearch/blob/main/README.md): Project overview, features, and quick start
- [NGramSearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/NGramSearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [SuffixArraySearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/SuffixArraySearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [CharSequenceSearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/CharSequenceSearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [HashSearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/HashSearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [LinqSearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/LinqSearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [StringSearch Spec](https://github.com/MILL5/FastSearch/blob/main/docs/StringSearch-Spec.md): Algorithm behavior, implementation and trade-offs
- [NGramSearch source](https://github.com/MILL5/FastSearch/blob/main/FastSearch/Algorithms/NGramSearch.cs): Recommended algorithm implementation
- [Benchmarks](https://github.com/MILL5/FastSearch#performance--memory-v11-net-10): Full tables for 10k, 100k and 1M items
- [NuGet Package](https://www.nuget.org/packages/FastSearch): Package listing and version history

## Author

Richard Crane is a **Microsoft Most Valuable Professional (MVP)** and the founder of **MILL5**, a Boston-based Microsoft Gold Partner specializing in cloud, AI, IoT, data analytics, and modern application development.

- MILL5: https://mill5.com
- Microsoft MVP profile: https://mvp.microsoft.com/en-US/MVP/profile/10ce0bc0-7536-43f6-b28c-e9601a4a0d0d
- Inventing Fire With AI (podcast): https://inventingfirewith.ai
- Contact: rich@mill5.com

## License

Apache License 2.0 — https://opensource.org/licenses/Apache-2.0