Skip to main content

Empirical determination of approximate values for levenshtein distances between random strings.

Project description


Python application License

This repository contains empirically determined approximate expected Levenshtein distances between random strings over alphabets of different sizes, as well as simple python code to generate them.


To use the code, you will need numpy and numba.


Simply clone this repo:

git clone [TARGET DIR]

and then install via pip

pip install [TARGET DIR]

or install directly from PyPI (this won't include unreleased changes as specified in the changelog):

pip install expected-levenshtein


Test the cloned package:

python -m unittest

Geting started

Use precomputed models

This package comes with precomputed models for certain alphabet sizes k and string lengths n. Currently the following models are available:

  • k = 20, 25 ≤ n ≤ 6000

Note: A model for a specific value of n only fits values for m (the length of the second string) such that m ≤ n.

The following example shows how a models can be loaded and used to compute the expected levenshtein distances for k = 20, n = 5000:

import as efit
import numpy as np

# load all models for k = 20
row_indices, coefficients, mean_squared_deviations = efit.load_precomputed(20)

# get the specific model for n = 5000. Here we consider an index row offset.
coeff_5k = coefficients[5000 - row_indices[0]]

# predict expected distance for n=5000, m=876
single_distance = efit.poly(876, coeff_5k)

# predict expected distances for n=5000, m ≤ 5000
range_distances = efit.poly(np.arange(5000), coeff_5k)

Computing average levenshtein distances

To compute the approximate expected Levenshtein distances of random strings of lengths 1 ≤ lengths ≤ n, use random_average_levenshtein in

This example shows how to compute the distances of random strings up to length 100 over a 4-letter alphabet, averaged over 1000 replicates.

from sample import random_average_levenshtein
import numpy as np

random_average_levenshtein(100, 1000, np.arange(4))

Generating models for expected distances

For long sequences, the distance matrix returned by random_average_levenshtein can get quite large. If you prefer not to load and query a large matrix object every time you need an expected distance, fit.model_average_levenshtein generates a polynomial model for each row in the distance matrix. That way, the information that needs to be stored to compute approximate expected levenshtein distances is reduced to the coefficients of the polynomials. Once computed, these can be used to predict expected distances with fit.poly.

This example shows how to generate and use such models for random strings from length 25 to length 50.

from sample import random_average_levenshtein
from fit import poly, model_average_levenshtein
import numpy as np

# sample distances
average_distances = random_average_levenshtein(50, 1000, np.arange(4))

# make models
row_indices, coefficients, mean_squared_deviations = model_average_levenshtein(
    average_distances, model_rows=np.arange(25, 51))

# predict expected distance for n=50, m=44
coeff_n_50 = coefficients[-1]
predicted_expected_distance = poly(44, coeff_n_50)


MIT license (LICENSE or

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

expected-levenshtein-0.1.2.tar.gz (402.2 kB view hashes)

Uploaded source

Built Distribution

expected_levenshtein-0.1.2-py3-none-any.whl (398.2 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page