LazyLevenshteinWithThreshold 1.0.0
dotnet add package LazyLevenshteinWithThreshold --version 1.0.0
NuGet\Install-Package LazyLevenshteinWithThreshold -Version 1.0.0
<PackageReference Include="LazyLevenshteinWithThreshold" Version="1.0.0" />
paket add LazyLevenshteinWithThreshold --version 1.0.0
#r "nuget: LazyLevenshteinWithThreshold, 1.0.0"
// Install LazyLevenshteinWithThreshold as a Cake Addin
#addin nuget:?package=LazyLevenshteinWithThreshold&version=1.0.0
// Install LazyLevenshteinWithThreshold as a Cake Tool
#tool nuget:?package=LazyLevenshteinWithThreshold&version=1.0.0
LazyLevenshteinWithThreshold
A C# implementation of the Levenshtein string distance, using lazy evaluation of its diagonals
Usage
LazyLevenshteinWithThreshold.CalculateDistance(string1, string2)
or
new LazyLevenshteinWithThreshold().CalculateStringDistance(string1, string2)
Complexity:
O(|a|*(Dist(a, b)))
If same strings:
O(|a|)
If completely different strings:
O(|a|*|b|)
(just as the regular dynamic programming solution)
Thresholding
The algorithm supports thresholding, hence the worst case time complexity is O(|a|*threshold) (If threshold is reached, distance calculation stops and int.MaxValue is returned)
Note on Time complexity
Even if this algorithm has a better time complexity, it is vastly slower than regular Levenshtein Dynamic programming algorithms on small strings due to the fact that it needs to initialize objects
Implementation and addition of thresholding by Karl Tillström
https://www.codeinthenorth.com
Developed in Master Thesis "Java exception matching in real time using fuzzy logic" (2010) https://odr.chalmers.se/handle/20.500.12380/122239
Original Algorithm (without thresholding) by:
L.Allison, Department of Computer Science, Monash University, Australia 3168. December 1991, Revised May 1992 http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/92.IPL.html
Product | Versions 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 | 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. |
-
.NETStandard 2.0
- No dependencies.
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 | 477 | 5/10/2020 |