Module documentation for 0.1.0
The library provides efficient implementations of various strings metrics.
It works with strict
Text values and returns either
(because the metrics cannot be negative), or
Ratio Natural values because
returned values are rational non-negative numbers by definition.
The current version of the package implements:
- Levenshtein distance
- Normalized Levenshtein distance
- Damerau-Levenshtein distance
- Normalized Damerau-Levenshtein distance
- Hamming distance
Comparison with the
package whose scope overlaps with the scope of this package. The differences
edit-distanceallows to specify costs for every operation when calculating Levenshtein distance (insertion, deletion, substitution, and transposition). This is rarely needed though in real-world applications, IMO.
edit-distanceonly provides single Levenshtein distance,
text-metricsaims to provide implementations of most string metrics algorithms.
text-metricsworks on strict
edit-distancestates, “[the algorithms] have been fairly heavily optimized”, which is apparently true, yet the
text-metricsis faster for short strings (under 64 characters) and even faster for longer strings (scales better). How much faster? For short strings more than ×2.5, and about ×4 for longer strings.
All “meat” of the algorithms is written is C in a rather straightforward way. Levenshtein variants are based on the “iterative algorithm with two matrix rows” from Wikipedia with additional improvement that we do not copy current row of distances into previous row, but just swap the pointers (which is OK, since the arrays have equal length and current row will be overwritten in the next iteration anyway).
Normalized versions are defined as thin (inlined) Haskell wrappers.
Copyright © 2016 Mark Karpov
Distributed under BSD 3 clause license.
Text Metrics 0.1.0
- Initial release.