I worked a bit more on this, against my better judgement :). A* search, more complicated than my other answer.
import collections
import heapq
import itertools
class SubsumptionTrie:
def __init__(self):
self.max_len = 0
self.min_v = float('inf')
self.children = {}
def insert(self, k, v, i=0):
self.max_len = max(self.max_len, len(k) - i)
self.min_v = min(self.min_v, v)
if i >= len(k):
return
c = k[i]
if c not in self.children:
self.children[c] = SubsumptionTrie()
self.children[c].insert(k, v, i + 1)
def subsumption_test(self, k, v, i=0):
if i >= len(k):
return self.min_v <= v
if (self.min_v > v) or (self.max_len < (len(k) - i)):
return False
c = k[i]
for b, child in self.children.items():
if b < c and self.children[b].subsumption_test(k, v, i):
return True
if c in self.children:
return self.children[c].subsumption_test(k, v, i + 1)
return False
def heuristic(s0, s1, n0, n1, substs):
substs0 = {a for a, _ in substs} | set(s1.keys())
substs1 = {b for _, b in substs} | set(s0.keys())
if n0 > n1:
s0, s1 = s1, s0
n0, n1 = n1, n0
substs0, substs1 = substs1, substs0
h0 = 0
m1 = sum(n for c, n in s1.items() if c in substs1)
for c, n in sorted(s0.items(), key=lambda t: t[1]):
if (c not in substs0) or (m1 < 0):
h0 += 1
else:
m1 -= n
h1 = 0
for c, n in sorted(s1.items(), key=lambda t: (t[0] in substs1, t[1]), reverse=True):
n0 -= n
if n0 < 0:
excess = min(-n0, n)
h1 += excess
n -= excess
if n and (c not in substs1):
h1 += 1
return max(h0, h1)
def dist(s0, s1):
labels = itertools.count()
relabel = collections.defaultdict(lambda: next(labels))
s0, s1 = [relabel[c] for c in s0], [relabel[c] for c in s1]
label_count = next(labels)
l0, l1 = len(s0), len(s1)
suffix_counts = tuple([collections.Counter(s[i:]) for i in range(len(s) + 1)] for s in (s0, s1))
q = []
def push_node(g, i, j, substs):
suff0, suff1 = suffix_counts[0][i], suffix_counts[1][j]
substs = frozenset(
t for t in substs if t[0] in suff0 and t[1] in suff1
)
h = heuristic(suff0, suff1, l0 - i, l1 - j, substs)
heapq.heappush(q, (g + h, -g, -len(substs), i, j, substs))
push_node(0, 0, 0, frozenset())
closed = collections.defaultdict(lambda: SubsumptionTrie())
while True:
(f, neg_g, _, i, j, substs) = heapq.heappop(q)
g = -neg_g
if (i == l0) or (j == l1):
return f
closed_ij = closed[(i, j)]
k = sorted(a * label_count + b for a, b in substs)
if closed_ij.subsumption_test(k, g):
continue
closed_ij.insert(k, g)
c0, c1 = s0[i], s1[j]
if (c0 == c1) or ((c0, c1) in substs):
push_node(g, i + 1, j + 1, substs)
continue
push_node(g + 1, i + 1, j + 1, substs | frozenset(((c0, c1),)))
push_node(g + 1, i + 1, j, substs)
push_node(g + 1, i, j + 1, substs)