Research

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\)).

Fast fuzzy search on 100 million DNA dataset

This expository note explains how to query a 100 million DNA dataset in a couple seconds.