# PruningRadixTrie: a prefix search that stops walking branches it cannot win

> PruningRadixTrie is an MIT licensed C# radix trie that stores the maximum rank of a node's children, so a top-k prefix lookup can prune low ranked branches and terminate early. The project claims three orders of magnitude over an ordinary radix trie, and the interesting part is the rank bookkeeping rather than the trie itself.

**wolfgarbe/PruningRadixTrie** — PruningRadixTrie - 1000x faster Radix trie for prefix search & auto-complete

- Repository: https://github.com/wolfgarbe/PruningRadixTrie
- Website: https://seekstorm.com/blog/pruning-radix-trie/
- Stars: 603 · Forks: 33
- Language: C#
- License: MIT
- Published: 2026-10-22 · Updated: 2026-10-22 · Language: en
- Canonical page: https://hysenlabs.com/projects/wolfgarbe-pruningradixtrie

## The trie is standard, the pruning is not

A radix trie, also called a Patricia trie, is a space-optimized trie, a prefix tree. PruningRadixTrie is derived from one of those, and the project describes it as a novel radix trie algorithm that allows pruning of the radix trie and early termination of the lookup.

The distinction matters. A conventional trie walks the tree following the characters of the prefix, and when it reaches the end of the prefix it has to collect every matching subtree, because a conventional trie has no way to know which of those matches the caller cares about. The work is proportional to the size of the matching set, which for a short prefix in a large dictionary is enormous.

The insight behind this implementation is that a caller usually does not want the complete set. In many cases we are not interested in a complete set of all children for a given prefix, but only in the top-k most relevant terms. The project argues that especially for short prefixes this results in a massive reduction of lookup time for the top-10 results, and that a complete result set of millions of suggestions would not be helpful at all for auto-completion.

That reframing is what makes the structure interesting. It is not a faster trie; it is a trie that assumes you want a ranked shortlist, and that treats the ability to stop early as the primary goal rather than an optimisation.

The implementation is C#, in a solution with a benchmark project, and the licence is MIT. The project is contributed by SeekStorm, a search as a service and search API company, which explains both the emphasis on serving many users in parallel and the presence of a benchmark suite.

## One integer per node makes the pruning possible

The mechanism is described in one sentence in the README, and it is the whole trick. The lookup acceleration is achieved by storing in each node the maximum rank of all its children. By comparing this maximum child rank with the lowest rank of the results retrieved so far, the trie can heavily prune itself and do early termination of the lookup for non-promising branches with low child ranks.

The logic is straightforward once stated. The results already collected have a lowest rank, which is the weakest result the caller will still accept for a top-k query. A subtree whose best possible child ranks below that threshold cannot contain a result the caller wants, so the walk into it is pointless and the branch is abandoned. A subtree whose maximum child rank is at or above the threshold might contain something worth having, so the walk continues.

What this costs is bookkeeping on insertion. Every node has to maintain the maximum rank of its children, which means that when a term is added, the ranks along its path have to be updated. The API reflects that, since terms are inserted with their frequency count and frequency counts for the same term are summed up.

The design also explains the ranking requirement. The structure is only able to prune because the terms carry a rank at all, which is why the dictionary used in the project's own testing is a frequency-ranked one. A collection of unranked strings does not give the structure anything to prune with, and the project says you can use any frequency dictionary for any language and domain of your choice.

## Short prefixes and CJK input are where the payoff is

The project's own framing of the problem is about serving many users rather than one. While 37 ms for an autocomplete might seem fast enough for a single user, it becomes insufficient when we have to serve thousands of users in parallel, and then autocomplete lookups in large dictionaries are only feasible when powered by something much faster than an ordinary radix trie.

The prefix length is the second variable, and it is where the biggest gains are. A prefix of length 1 is not very useful for the Latin alphabet, but it does make sense for CJK languages, where a single character is a meaningful start. For the Latin alphabet the interesting range is the two and three character prefixes, where a conventional trie has the most branches to explore and the most results to discard.

The third point is that the prefix need not be characters at all. The project notes many more application fields for a fast prefix search algorithm beyond character-wise word completion: instead of characters, the prefix can be composed of arbitrary items, for example whole words in a query completion, or towns in a long routing sequence. The structure is over sequences of tokens, and a token can be a character, a word or a place name.

That is the generalisation worth taking away. A radix trie over arbitrary token sequences with rank-aware pruning is a component you could drop into a query completion box, an address form, a routing input, or a search-as-you-type field over any vocabulary you can assign frequencies to. The related blog posts on the same site cover spelling correction and a comparison with SymSpell and the BK-tree, which tells you the same author treats this as one member of a family of approximate matching structures.

## Four operations, one file format

The API is small enough to read in one sitting. An instance is created directly:

```csharp
PruningRadixtrie pruningRadixTrie = new PruningRadixtrie();
```

Terms are inserted with their frequency count, and frequency counts for the same term are summed up, so the dictionary can be built by streaming a frequency list:

```csharp
pruningRadixTrie.AddTerm("microsoft", 1000);
```

The query is the interesting call, because it takes the prefix, the number of results wanted, and an out parameter for the total frequency of everything under that prefix:

```csharp
string prefix="micro";
int topK=10;
var results = pruningRadixTrie.GetTopkTermsForPrefix(prefix, topK, out long termFrequencyCountPrefix);
foreach ((string term,long termFrequencyCount) in results) Console.WriteLine(term+" "+termFrequencyCount);
```

The out parameter is a small design decision that pays off in practice. The total frequency count of the whole prefix tells the caller how much weight of language sits under that prefix, which is what a ranking or a did-you-mean layer needs in order to decide whether the suggestion list is worth showing at all, and it is available without a second traversal.

Persistence is two methods, one to read and one to write:

```csharp
pruningRadixTrie.ReadTermsFromFile("terms.txt");
```

```csharp
pruningRadixTrie.WriteTermsToFile("terms.txt");
```

The file is the same terms file the dictionary comes from, which keeps the format simple, and it means the expensive part of a deployment, building and ranking a multi-million term dictionary, happens once and is then loaded from disk rather than rebuilt on every start.

## The Rust version is official, the other ports are not

The README separates official implementations from ports, and the distinction is stated carefully enough to be worth repeating. Under official implementations there are two: the C# repository, which is this one, and the Rust implementation at `wolfgarbe/pruning_radix_trie_rs`.

Under ports, there are third party ports or reimplementations in other languages, and the project attaches an explicit warning to that list: they have not been tested by the author whether they are an exact port, error free, provide identical results, or are as fast as the original algorithm. Go, Java and Python ports are listed, and two Rust implementations are also listed, one of which is the official one and one of which is a separate community repository.

That warning is the correct thing for a reader to carry away. A port of a pruning implementation is easy to get subtly wrong, because the whole point of the algorithm is the rank invariant, and an implementation that updates the maximum child rank differently, or that terminates on a different comparison, will return the same top results most of the time and different ones at the boundaries. Silent divergence in a result set is the kind of bug that is hard to notice and expensive to diagnose later.

So the practical guidance is short. Use the C# implementation if you are in .NET, use the Rust implementation if you are in Rust, and treat the other ports as code to read rather than code to depend on until you have compared their output against the reference on your own dictionary.

## The speed claim, the dictionary, and the questions to ask first

The project states that the pruning radix trie is up to 1000x faster than an ordinary radix trie, and describes the structure as three orders of magnitude faster than the radix trie it derives from. It ships a benchmark image, and the repository contains a `PruningRadixTrie.Benchmark` project alongside the library and a Visual Studio solution.

Those are the project's own figures, published by a project whose author is a search API company with a commercial interest in fast prefix search. That is not a reason to dismiss them, and the accompanying reasoning about serving thousands of users in parallel is the kind of argument a search service has to make honestly. It is a reason to check the benchmark against your own workload, because the shape of the workload is what determines the gain. A query that returns the top ten of a million candidates prunes enormously; a query that must return everything under a prefix does not prune at all and gets the ordinary trie cost plus the bookkeeping.

The dictionary matters just as much. `Terms.txt` contains 6 million unigrams and bigrams derived from English Wikipedia, with term frequency counts used for ranking, and the project notes that you can use any frequency dictionary for any language and domain of your choice. A domain-specific dictionary with meaningful frequencies is where the pruning does the most work, and a dictionary of unranked or uniformly ranked terms is where it does the least.

On upkeep, the repository is not archived and the last push was on 2026-10-07, while the tagged releases are v1.0.0 and v1.0.1, both from 2024-06-27. The structure is stable and the version is 1.0, which for a data structure library of this kind is a reasonable place to sit, though the gap between the release tags and the current branch is worth keeping in mind if you are pinning a version.

## Conclusion

PruningRadixTrie suits a service that answers prefix or auto-complete queries over a large frequency ranked dictionary and needs the top-k results rather than the whole set, particularly when many users query in parallel. It does not suit a use case that needs every term under a prefix, since the pruning is exactly what makes the lookup fast, and it does not suit a project that needs the additional behaviour the other data structures in the same family provide. Before adopting, read the blog post on the algorithm to understand the rank invariant, check the port you intend to use, since the project states that the third party ports are untested by the author for exactness and speed, and plan for the dictionary to be loaded and ranked before serving the first query.

## FAQ

### What makes PruningRadixTrie different from an ordinary radix trie?

Each node stores the maximum rank of all its children, so a top-k prefix lookup can compare that maximum against the lowest rank of the results collected so far and abandon branches that cannot contain a wanted result. That is pruning with early termination, which an ordinary radix trie does not do.

### How do I add terms and query for suggestions with PruningRadixTrie?

Add each term with its frequency count using `AddTerm`, where counts for the same term are summed, then call `GetTopkTermsForPrefix(prefix, topK, out long termFrequencyCountPrefix)`, which returns the top-k terms and the total frequency under the prefix.

### Can I persist a PruningRadixTrie to disk?

Yes, with `WriteTermsToFile("terms.txt")` and `ReadTermsFromFile("terms.txt")`. The file format is the same terms file the dictionary is built from, so a large ranked dictionary can be built once and then loaded from disk rather than rebuilt at start-up.

### Are the Go, Java and Python versions of PruningRadixTrie reliable?

The project states that the third party ports and reimplementations have not been tested by the author for being an exact port, error free, providing identical results, or being as fast as the original. The C# and Rust implementations are the official ones.

### What dictionary does PruningRadixTrie use for testing?

A `Terms.txt` file with 6 million unigrams and bigrams derived from English Wikipedia, with term frequency counts used for ranking. The project notes that any frequency dictionary for any language or domain can be used instead.

## Sources

- [License: MIT](https://github.com/wolfgarbe/PruningRadixTrie/blob/master/LICENSE)
- [Project website](https://seekstorm.com/blog/pruning-radix-trie/)
- [README](https://github.com/wolfgarbe/PruningRadixTrie/blob/master/README.md)
- [Releases](https://github.com/wolfgarbe/PruningRadixTrie/releases)
- [wolfgarbe/PruningRadixTrie on GitHub](https://github.com/wolfgarbe/PruningRadixTrie)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/wolfgarbe-pruningradixtrie