# 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.