lev-dist.py

import random
import string

import matplotlib
import numpy as np
from scipy.spatial.distance import cityblock

matplotlib.use('Agg')
import matplotlib.pyplot as plt

with open('/usr/share/dict/words') as fp:
    words = fp.readlines()

words = [word.strip().lower() for word in words]

N = 30000
max_dist = 30

words1 = random.sample(words, N)
words2 = random.sample(words, N)


def levenshtein_dist(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2 + 1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]  # / max(len(s1), len(s2))


letters = string.ascii_letters + '-'
l2i = {l: i for i, l in enumerate(letters)}


def hist_dist(s1, s2):
    s1e = hist_embed(s1)
    s2e = hist_embed(s2)
    return cityblock(s1e, s2e)  # / max(len(s1), len(s2)) / 2


def hist_embed(s1):
    e = np.zeros(len(l2i))
    for i in [l2i[l] for pos, l in enumerate(list(s1))]:
        e[i] += 1.
    return e


lds, hds = [], []
for w1, w2 in zip(words1, words2):
    lds.append(levenshtein_dist(w1, w2))
    hds.append(hist_dist(w1, w2))

lds = np.array(lds)
hds = np.array(hds)
MSE = np.mean((lds - hds) ** 2)
print(MSE)
vals = []
uniqs = np.unique(lds)
for dist in uniqs:
    idx = lds == dist
    vals.append(hds[idx])

maxd = max(np.max(lds), np.max(hds))
plt.figure(figsize=(6, 6))
plt.boxplot(vals, positions=uniqs, showfliers=False)  # bins=[np.arange(30), np.arange(30)],
plt.xlim([0, maxd])
plt.ylim([0, maxd])
plt.plot([0, maxd], [0, maxd], 'b-')
plt.xlabel('Levenshtein distance')
plt.ylabel('Histogram L1 distance')
plt.savefig('dist.png')