TrieNet2 2.0.0

.NET 6.0
There is a newer version of this package available.
See the version list below for details.
dotnet add package TrieNet2 --version 2.0.0
NuGet\Install-Package TrieNet2 -Version 2.0.0
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="TrieNet2" Version="2.0.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add TrieNet2 --version 2.0.0
#r "nuget: TrieNet2, 2.0.0"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
// Install TrieNet2 as a Cake Addin
#addin nuget:?package=TrieNet2&version=2.0.0

// Install TrieNet2 as a Cake Tool
#tool nuget:?package=TrieNet2&version=2.0.0

NuGet version

TrieNet - The library provides .NET Data Structures for Prefix String Search and Substring (Infix) Search to Implement Auto-completion and Intelli-sense. This is a modern .NET update for the old TrieNet package.


  nuget install TrieNet2
using TrieNet.Ukkonen;

var trie = new CharUkkonenTrie<int>(3);
//var trie = new GenerixSuffixTrie<char, int>(3);

trie.Add("hello", 1);
trie.Add("world", 2);
trie.Add("hell", 3);

var result = trie.Retrieve("hel");
// result = { 1, 3 };

var result2 = trie.RetrieveSubstrings("ll");
// result2 = { new WordPosition(2, 1), new WordPosition(2, 3) };


This small library contains a bunch of trie data structures all having the same interface:

public interface ITrie {
  IEnumerable Retrieve(string query);
  void Add(string key, TValue value);
Class Description
Trie The simple trie, allows only prefix search, like .Where(s => s.StartsWith(searchString))
SuffixTrie Also allows infix search, like .Where(s => s.Contains(searchString))
PatriciaTrie Compressed trie, more compact, a bit more efficient during look-up, but a quite slower during build-up.
SuffixPatriciaTrie The same as PatriciaTrie, also enabling infix search.
ParallelTrie Very primitively implemented parallel data structure which allows adding data and retrieving results from different threads simultaneusly.
CharUkkonenTrie The same as SuffixPatriciaTrie, but more compact, more efficient during look-up, and quite a lot faster during build-up. This is the best choice.

There is also a generic interface which lets you search for more than just strings:

public interface IGenericTrie<TKey, TValue> where TKey : IEquatable<TKey> {
    IEnumerable<TValue> Retrieve(ReadOnlySpan<TKey> query);
    void Add(ReadOnlyMemory<TKey> key, TValue value);

At the moment only UkkonenTrie implements this interface.


All diagrams are given in logarithmic scale on the x-axis and y-axis.

Demo app

The app demonstrates indexing of large text files and look-up inside them. Indexing usually takes only a few seconds and the look-up delay will be unnoticeable for the user.

Product Versions
.NET net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows net7.0 net7.0-android net7.0-ios net7.0-maccatalyst net7.0-macos net7.0-tvos net7.0-windows
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.
  • net6.0

    • No dependencies.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
2.0.2 519 9/29/2022
2.0.0 252 9/28/2022