Levenshtypo 1.1.0

Levenshtypo - a .NET fuzzy matching string dictionary

Levenshtypo is a library which allows you to search large data sets by fuzzy matching the key strings.

The dataset is loaded upfront as a sequence of key-value pairs. Once loaded it allows searching for the values which are up to a certain Levenshtein Distance away from a query string.

Levenshtein Distance is the number of character insertions, deletions or substitutions required to transform one string into another.

Planned Work (Coming Soon)

• Automaton to return edit distance
• State Serialization logic
• Preserialized state machines offered on GitHub

Installation

Install via Nuget.

Getting Started

// Start with a dataset
IEnumerable<KeyValuePair<string, object>> dataset = ...;

// Index the dataset in a levenshtrie. The levenshtrie should be stored for re-use.
Levenshtrie<object> levenshtrie = Levenshtrie<object>.Create(dataset);

// Search the dataset for keys with edit distance 2 from "hello"
object[] results = levenshtrie.Search("hello", 2);

Samples

These samples and more can be found in the samples directory.

<details> <summary>Suggest similar words</summary>

public class TypoSuggestion
{
    private readonly Levenshtrie<string> _trie;

    public TypoSuggestion(IEnumerable<string> words)
    {
        _trie = Levenshtrie<string>.Create(
            words.Select(w => new KeyValuePair<string, string>(w, w)),
            ignoreCase: true);
    }

    public string[] GetSimilarWords(string word)
    {
        return _trie.Search(word, maxEditDistance: 2);
    }
}

</details>

<details> <summary>Find whether a string matches blacklist</summary>

public class BlacklistDetection
{
    private readonly Levenshtrie<string> _trie;

    public BlacklistDetection(IEnumerable<string> blacklist)
    {
        _trie = Levenshtrie<string>.Create(
            blacklist.Select(w => new KeyValuePair<string, string>(w, w)),
            ignoreCase: true);
    }

    public bool IsBlacklisted(string word)
    {
        return _trie.Search(word, maxEditDistance: 1).Contains(word);
    }
}

</details>

</details>

<details> <summary>Quickly check whether a list of strings matches an input</summary>

// Benchmarks below show that a naive implementation,
// even if it is well written, is 10x slower than using
// an automaton.
// Benchmark run against English language dataset.
//
// | Method          | Mean       | Error     | StdDev    | Allocated |
// |-----------------|-----------:|----------:|----------:|----------:|
// | Using_naive     | 103.190 ms | 1.4706 ms | 1.3756 ms |     214 B |
// | Using_automaton |   8.161 ms | 0.0469 ms | 0.0439 ms |      12 B |

public static string[] Search(string searchWord, string[] against)
{
    var automaton = LevenshtomatonFactory.Instance.Construct(searchWord, maxEditDistance: 2);

    var results = new List<string>();

    foreach (var word in against)
    {
        // Naive version would be:
        // bool matches = LevenshteinDistance.Levenshtein(searchWord, word) <= 2;

        // Automaton version is:
        bool matches = automaton.Matches(word);
        if (matches)
        {
            results.Add(word);
        }
    }

    return results.ToArray();
}

</details>

Limitations

• No lookup by UTF8 byte arrays.
• No support for surrogate character pairs.
• Only ordinal character comparison, whether case sensitive or insensitive.
• Maximum Levenshtein Distance of 3.

Performance

The English Language dataset used in the benchmarks contains approximately 465,000 words.

<details> <summary>Search all English Language with a fuzzy key</summary>

• Naive: Compute Levenshtein Distance against all words.
• Levenshtypo: This library.
• Dictionary: .NET Dictionary which only works for distance of 0.

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3880/23H2/2023Update/SunValley3)
AMD Ryzen 9 5950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK 8.0.400-preview.0.24324.5
  [Host]     : .NET 8.0.6 (8.0.624.26715), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.6 (8.0.624.26715), X64 RyuJIT AVX2

</details>

<details> <summary>Load all English Language dataset</summary>

• Levenshtypo: This library.
• Dictionary: .NET Dictionary for comparison.

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3880/23H2/2023Update/SunValley3)
AMD Ryzen 9 5950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK 8.0.400-preview.0.24324.5
  [Host]     : .NET 8.0.6 (8.0.624.26715), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.6 (8.0.624.26715), X64 RyuJIT AVX2

</details>

References

The algorithm in this library is based on the 2002 paper Fast String Correction with Levenshtein-Automata by Klaus Schulz and Stoyan Mihov.

I used the following blog posts to further help understand the algorithm.

• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata
• https://fulmicoton.com/posts/levenshtein/

I used the following repository to obtain the list of English words, used in tests.

• https://github.com/dwyl/english-words