TrieNet2 2.0.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

alternate text is missing from this package README image

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.

Usage

  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) };

Implementation

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.

Performance

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

alternate text is missing from this package README image

alternate text is missing from this package README image

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.

alternate text is missing from this package README image

Product Compatible and additional computed target framework versions.
.NET net6.0 is compatible.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 was computed.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
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 (1)

Showing the top 1 popular GitHub repositories that depend on TrieNet2:

Repository Stars
bcssov/IronyModManager
Mod Manager for Paradox Games. Official Discord: https://discord.gg/t9JmY8KFrV
Version Downloads Last updated
2.0.2 1,933 9/29/2022
2.0.0 391 9/28/2022