Zeroshtein 1.0.0

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

// Install Zeroshtein as a Cake Tool
#tool nuget:?package=Zeroshtein&version=1.0.0

Zeroshtein

Simple and fast implementation of the Levenshtein distance algorithm. And nothing more. It utilizes Span<T> over stackallock to avoid allocations and improve performance. And ArrayPool<T> in case of exceed MaxStackAllocSize static property value.

It has a lot of optimizations and tricks to improve performance:

  • Do not use unsafe code.
  • Reducing array indexings.
  • Allocating only array for current line calculation and reusing it for next line calculation.
  • Zero index is not part of the line and stored in a separate variable.
  • etc.

Benchmarks

And in result it extremely fast on Windows and MacOS. It even faster than Fastenshtein library (a little bit 😏).

Windows 11, x86

Method Mean Error StdDev Ratio Gen0 Allocated
Fastenshtein 7.613 us 0.0295 us 0.0276 us 1.00 0.9308 5896 B
FastenshteinZeroAlloc 6.845 us 0.0136 us 0.0120 us 0.90 - -
Zeroshtein 6.958 us 0.0093 us 0.0083 us 0.91 - -
ZeroshteinInMemory 12.122 us 0.0263 us 0.0246 us 1.59 - -
StringSimilarity 17.948 us 0.0691 us 0.0647 us 2.36 1.7395 11064 B
NinjaNye 19.700 us 0.0586 us 0.0490 us 2.59 7.1411 44880 B
FuzzyStrings 77.905 us 0.2432 us 0.2031 us 10.23 26.8555 169040 B
Quickenshtein 23.650 us 0.0324 us 0.0271 us 3.11 - -

Benchmark was performed in next environment:

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22000.1574/21H2/SunValley)
Intel Core i7-9700K CPU 3.60GHz (Coffee Lake), 1 CPU, 8 logical and 8 physical cores
.NET SDK=7.0.102
  [Host]     : .NET 7.0.2 (7.0.222.60605), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.2 (7.0.222.60605), X64 RyuJIT AVX2

MacOS 13.2, arm64

Method Mean Error StdDev Ratio Gen0 Allocated
Fastenshtein 5.690 us 0.0240 us 0.0225 us 1.00 0.9384 5896 B
FastenshteinZeroAlloc 5.237 us 0.0142 us 0.0132 us 0.92 - -
Zeroshtein 5.469 us 0.0105 us 0.0093 us 0.96 - -
ZeroshteinInMemory 6.906 us 0.0188 us 0.0176 us 1.21 - -
StringSimilarity 8.884 us 0.0173 us 0.0162 us 1.56 1.7548 11064 B
NinjaNye 11.147 us 0.0263 us 0.0219 us 1.96 7.1411 44880 B
FuzzyStrings 46.450 us 0.1166 us 0.0974 us 8.17 26.9165 169040 B
Quickenshtein 5.692 us 0.0115 us 0.0108 us 1.00 - -

Benchmark was performed in next environment:

BenchmarkDotNet=v0.13.5, OS=macOS Ventura 13.2.1 (22D68) [Darwin 22.3.0]
Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
.NET SDK=7.0.101
  [Host]     : .NET 7.0.1 (7.0.122.56804), Arm64 RyuJIT AdvSIMD
  DefaultJob : .NET 7.0.1 (7.0.122.56804), Arm64 RyuJIT AdvSIMD

Usage

var distance = Zeroshtein.Levenshtein.Distance("horce", "rose");

By default Zeroshtein uses stackallock to allocate calculation array in stack only. And if it exceeds MaxStackAllocSize static property value it uses ArrayPool<T> to allocate array in memory. Default value of MaxStackAllocSize is 1024 bytes. But can be changed to any value, it is a static property.

Zeroshtein.Levenshtein.MaxStackAllocSize = 4096;

It should be set with caution. Big value can cause StackOverflowException in case of long strings. This exception can't be caught and handled. It will cause application crash.

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 netcoreapp1.0 was computed.  netcoreapp1.1 was computed.  netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard1.1 is compatible.  netstandard1.2 was computed.  netstandard1.3 was computed.  netstandard1.4 was computed.  netstandard1.5 was computed.  netstandard1.6 was computed.  netstandard2.0 was computed.  netstandard2.1 was computed. 
.NET Framework 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 tizen30 was computed.  tizen40 was computed.  tizen60 was computed. 
Universal Windows Platform uap was computed.  uap10.0 was computed. 
Windows Phone wpa81 was computed. 
Windows Store netcore was computed.  netcore45 was computed.  netcore451 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.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
1.0.0 236 3/16/2023