AhoCorasick 2.0.258

dotnet add package AhoCorasick --version 2.0.258
NuGet\Install-Package AhoCorasick -Version 2.0.258
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="AhoCorasick" Version="2.0.258" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add AhoCorasick --version 2.0.258
#r "nuget: AhoCorasick, 2.0.258"
#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 AhoCorasick as a Cake Addin
#addin nuget:?package=AhoCorasick&version=2.0.258

// Install AhoCorasick as a Cake Tool
#tool nuget:?package=AhoCorasick&version=2.0.258

AhoCorasick

Version Build status Coverage Status netstandard2.0 net40

This is an implementation of the Aho-Corasick string matching algorithm for .NET (netstandard2.0 and net40) and SQL Server (SQL CLR). Mostly ported from xudejian/aho-corasick in CoffeeScript.

Usage

var ac = new AhoCorasick("a", "ab", "bab", "bc", "bca", "c", "caa");
var results = ac.Search("abccab").ToList();

Assert.AreEqual(0, results[0].Index); // index into the searched text
Assert.AreEqual("a", results[0].Word); // matched word
// ...

or

var results = "abccab".Contains("a", "ab", "bab", "bc", "bca", "c", "caa").ToList();

Custom char comparison

You can optionally supply an IEqualityComparer<char> to perform custom char comparisons when searching for substrings. Several implementations with comparers that mirror StringComparer are included.

var results = "AbCcab".Contains(CharComparer.OrdinalIgnoreCase, "a", "ab", "c").ToList();

SQL CLR Functions

There are also several SQL CLR user defined functions that can be used to perform fast substring matching in Microsoft SQL Server. To use this:

  1. Make sure you have enabled CLR integration
  2. Execute AhoCorasick.SqlClr_Create.sql

For one-off queries, you can use the functions that rebuild the trie on each query, e.g.

select top(100) * from Posts P
where dbo.ContainsWords((select Word from Words for xml raw, root('root')), P.Body, 'o') = 1

The words to match are always supplied as XML where the values are taken from the first attribute of all elements directly beneath the root node. Be careful to select the word column as the only or first column otherwise you'll end up matching the wrong words. The XML in the example above looks like this:

<root>
  <row Word="Aachen" />
  <row Word="Aaliyah" />
  <row Word="aardvark" />
  ...
</root>

Here's more about FOR XML.

The last parameter in the function indicates the culture to use since there is no way to use SQL Server collations in SQL CLR code. Values can be:

Value Character comparison
c Current Culture
n Invariant Culture
o or Empty Ordinal
Culture name, e.g. "de-de" Specific .NET Culture

The culture identifier can be suffixed by :i indicating case-insensitive matching.

Static objects

The function in the example above has the problem that the trie is rebuilt for each query even though the input always stays the same. To overcome this problem, there are a number of functions to manage the creation and destruction of static objects whose handles can be saved in SQL variables. Example:

declare @ac nvarchar(32);
set @ac = dbo.CreateAhoCorasick((select Word from Words for xml raw, root('root')), 'en-us:i');
select * from Posts P
where dbo.ContainsWordsByObject(P.Body, @ac) = 1;

This is a lot faster than the first example because the trie is created only once and then reused for each row in the query. The handle (@ac) is a hash value generated from the words to match and the culture. The corresponding object is saved in a static dictionary. You can list the currently active objects using dbo.ListAhoCorasick(), remove all objects using dbo.ClearAhoCorasick() or remove only one object using dbo.DeleteAhoCorasick(@ac).

Getting all matches

The examples above only checked if the words occurred in the queried texts. If you want to get the matched words and the indexes where they occur in the queried texts you can use the supplied table-valued functions. For example:

declare @ac nvarchar(32);
set @ac = dbo.CreateAhoCorasick((select Word from Words for xml raw, root('root')), 'o');
select top(100) * from Posts P
cross apply dbo.ContainsWordsTableByObject(P.Body, @ac) W

This will return a table such as this:

ID Body Index Word
1 What factors related... 5 factor
1 What factors related... 6 actor
1 What factors related... 5 factors
...

Word boundaries

There are also functions that return only matches occuring at word boundaries: dbo.ContainsWordsBoundedByObject() and dbo.ContainsWordsBoundedTableByObject(). Word boundaries here are the same as \b in regexes, i.e. matches will occur as if words were specified as \bword\b.

Forcing parallelism

Although these kinds of queries lend themselves very well to parallel execution, SQL Server tends to overestimate the cost of parallel queries and builds non-parallel plans most of the time where user defined functions are involved. You can force a parallel plan by using a trace flag (more about this here):

declare @ac nvarchar(32);
set @ac = dbo.CreateAhoCorasick((select Word from Words for xml raw, root('root')), 'en-us:i');
select * from Posts P
where dbo.ContainsWordsBoundedByObject(P.Body, @ac) = 1
OPTION (RECOMPILE, QUERYTRACEON 8649)

Parallel operators are identified by a yellow badge with two arrows in the query plan.

Performance

Here's a benchmark searching for ~5000 words (average length 7) in ~250,000 texts (average length ~900):

SQL AhoCorasick
560s 7s

The SQL query used was this:

select * from Posts P
where exists (select * from Words W where CHARINDEX(W.Word, P.Text) > 0)

No. The CONTAINS predicate can only search for a single literal or variable at a time. You can't use it in a join or subquery to search for a column value of a table in the query, i.e. this won't work:

select * from Posts P
where exists (select * from Words W where CONTAINS(P.Text, W.Word))

If you know of a way to make this work using FTS (perhaps using a cursor?) let me know.

Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  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. 
.NET Core netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard2.0 is compatible.  netstandard2.1 was computed. 
.NET Framework net40 is compatible.  net403 was computed.  net45 was computed.  net451 was computed.  net452 was computed.  net46 was computed.  net461 was computed.  net462 was computed.  net463 was computed.  net47 was computed.  net471 was computed.  net472 was computed.  net48 was computed.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen40 was computed.  tizen60 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.
  • .NETFramework 4.0

    • No dependencies.
  • .NETStandard 2.0

    • No dependencies.

NuGet packages (2)

Showing the top 2 NuGet packages that depend on AhoCorasick:

Package Downloads
GcAbstractions

Abstractions for GC library

AutoLink

Replace URIs in text with HTML links

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
2.0.258 7,985 2/12/2024
2.0.190 33,277 12/20/2022
2.0.189 307 12/20/2022
2.0.46 390,583 10/18/2019
2.0.29 18,704 6/26/2019
2.0.11 187,543 9/4/2017
1.1.5577.36525 5,996 4/9/2015
1.1.5569.20484 1,267 4/1/2015
1.1.5569.20298 1,271 4/1/2015
1.0.5563.31756 1,329 3/26/2015