This is a .NET Core 3.1 / .NET 6.0 ported version of gmamaladze/trienet. Please refer to the README.md file in this original repository for its background, appliances, motivation, and perhaps find some updates there :-)

This library provides efficient prefix / infix (aka. substring) search with various data structures. To install the NuGet package, use the following command

#  Package Management Console
Install-Package CXuesong.Ported.TrieNet
#  .NET CLI
dotnet add package CXuesong.Ported.TrieNet

The library provides the following interface to expose the most basic & common functionality of various tries. Note that the actual "Retrieve" behavior (prefix / infix search) is implementation-dependent.

namespace Gma.DataStructures.StringSearch;

public interface IReadOnlyTrie<out TValue>
{
    IEnumerable<TValue> Retrieve(ReadOnlySpan<char> query);
    IEnumerable<TValue> Retrieve(ReadOnlyMemory<char> query);
    IEnumerable<TValue> Retrieve(string query);
}

public interface ITrie<TValue> : IReadOnlyTrie<TValue>
{
    void Add(ReadOnlyMemory<char> key, TValue value);
    void Add(string key, TValue value);
}

Compared with the original edition, this ported package introduced Memory / Span-based API that can be helpful if you do not want to creating a lot of strings when querying for a specific word / prefix.

Copied from the README.md in the original repo:

using Gma.DataStructures.StringSearch;

var trie = new UkkonenTrie<int>(3);
//var trie = new SuffixTrie<int>(3);

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

var result = trie.Retrieve("hel");

Similar to the performance test given by the README.md in the original repo, please execute the PerformanceComparisonTests in the unit test project for the results below.

In addition to the performance gain thanks to the algorithms, the adoption of ReadOnlyMemory and ReadOnlySpan instead of string concatenations also slightly reduces the trie build-up time and look-up time.

[1] Average operation time over each trie item.

Here is the look-up time and build-up time for each kind of trie in the ported library.

Here is the look-up time and build-time for ported (this repo) v.s. original library.

This demo application is from the original repository. The only change in this repo is the demo performs case-insensitive search.

The app demonstrates indexing of large text files and look-up inside them. I have experimented with huge texts containing millions of words. Indexing took usually only several seconds and the look-up delay was still unnoticable for the user.