This page contains a collection of technical surveys which I did during development of polyleven.
List of articles¶
- Can We Optimize the Wagner-Fischer Algorithm?
In this expository note, I explain several techniques to optimize the Wagner-Fischer algorithm.
This note contains a small benchmark test program as well. The result suggests that it is possible to reduce the computation time by 20-40% in general cases.
- Wagner-Fischer vs Myers’ Algorithm
This article compares the two most common algorithms for computing Levenshtein Distance.
- mbleven – A fast algorithm for bounded edit distance
mbleven is a fast algorithm to compute k-bounded Levenshtein distance. In general, it’s one of the fastest algorithm for cases where the bound parameter is small (\(k < 3\)).
This expository note explains how to query a 100 million DNA dataset in a couple seconds.