MyersBitParallelAlgorithm 0.1.1

MyersBitParallelAlgorithm

A small, dependency-free .NET 8, .NET 9, and .NET 10 library for repeatedly calculating the exact Levenshtein distance from one prepared search term to many candidate strings.

Source code on GitHub

The matcher uses the single-word form of Gene Myers's bit-vector algorithm, so the search term is limited to 64 UTF-16 code units. Candidate strings are not length-limited.

Install

dotnet add package MyersBitParallelAlgorithm --version 0.1.1

Use

using MyersBitParallelAlgorithm;

string term = TextNormalizer.ToLowerInvariantAndTrim("  Jose  ");
var matcher = MyersMatcher.ForUtf16(term);

foreach (string patientName in patientNames)
{
    string candidate = TextNormalizer.ToLowerInvariantAndTrim(patientName);
    int distance = matcher.Distance(candidate);
    // Rank or filter in the application.
}

Use MyersMatcher.ForAscii when both the search term and every candidate are guaranteed to contain only ASCII characters. It rejects non-ASCII input rather than silently changing comparison semantics. Use ForUtf16 for general .NET text.

Matchers are immutable and safe to reuse concurrently. Preparing a matcher allocates its character-mask lookup once; calls to Distance do not allocate.

Comparison semantics

• Distance is the number of unit-cost insertions, deletions, and substitutions.
• Matching is ordinal and case-sensitive.
• UTF-16 code units are compared. A supplementary Unicode character, such as most emoji, therefore occupies two positions.
• An empty search term is supported.
• A search term longer than 64 code units is rejected.

Normalization is deliberately optional. TextNormalizer.RemoveDiacritics removes Unicode combining marks and is lossy. ToLowerInvariantAndTrim performs invariant lowercasing and trims only leading and trailing whitespace. Apply the same normalization to both the search term and candidates. Name-handling rules are domain decisions; this library does not remove punctuation, collapse internal whitespace, transliterate scripts, or apply culture-specific casing.

Scope

This package computes full-string distance from one prepared term. It does not provide substring search, thresholds, similarity ratios, result ranking, custom character mapping, or patterns longer than 64 code units.

Benchmarks

The benchmark console app uses Bogus to generate deterministic fake patient names, normalizes one shared ASCII dataset, and uses BenchmarkDotNet to compare the following NuGet packages:

• MyersBitParallelAlgorithm (this project)
• FastBatchLevenshtein 1.0.0
• FuzzySharp 2.0.2 (currently commented out)
• MyersBitParallel 0.2.4

Each benchmark materializes every matching candidate ID into a preallocated result buffer and runs two independent threshold scenarios: edit distance at most three, and normalized similarity of at least 60%. FastBatchLevenshtein uses its native batch-search operation; the other libraries scan the same candidate array and apply the equivalent threshold. Each invocation searches 16 names back-to-back, sampled deterministically from the candidates: 12 two-part names and 4 three-part names. Setup verifies that all implementations return the same query-and-candidate match set before measurement. Fake-data generation, normalization, engine construction, and prepared-pattern creation are outside the timed methods.

Each active implementation also has a parallel benchmark that searches all 16 prepared queries concurrently. Each query uses an isolated preallocated result buffer or slice, and setup verifies every complete match set against the sequential baseline.

For the edit-distance threshold, this library's benchmark first rejects names whose length difference is greater than three. ExactDistanceBenchmarks separately compares exact, unbounded distance calculations without threshold shortcuts.

Run it in Release configuration:

dotnet run --project benchmarks/MyersBitParallelAlgorithm.Benchmarks -c Release

Use BenchmarkDotNet command-line arguments to filter or adjust a run, for example --filter *FuzzySharp*. Benchmark results are written under BenchmarkDotNet.Artifacts/.

The benchmark project references the AGPL-3.0-licensed MyersBitParallel package. It is isolated from the runtime library and is not included in the MyersBitParallelAlgorithm NuGet package. Distribution of the compiled benchmark application must comply with that dependency's license.

Algorithm and license

The implementation is based on the algorithm described in:

Gene Myers, "A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming," Journal of the ACM 46(3), 1999. https://doi.org/10.1145/316542.316550

The project is available under the MIT License. CureMD should approve the copyright and employment-IP wording before public publication.