Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$.

Assume that the Levenshtein distance (minimum number of single-character edits (i.e. insertions, deletions or substitutions)) between $S_1$ and $S_2$ over binary alphabet is $L(2)$.

For any $b$ such that $b>1$ and $b|c$ consider the strings $S_1$ and $S_2$ over alphabet $\{0,1,\dots,2^b-1\}$. Assume the Levenshtein distance between $S_1$ and $S_2$ over $b$-ary alphabet is $L(2^b)$.

Is there any relation between $L(2)$ and $L(2^b)$ in general?

Can we say anything for LCS (minimum number of insertions or deletions) distance as well?


Obviously, $L(2^b) \leq L(2)$.

The Levenshtein distance is at most the length of the longest string, so $L(2^b) \leq \max(cn,cm) / b$ whereas $L(2) \leq \max(cn,cm)$.

You cannot avoid $L(2^b)(S_1,S_2) = L(2)(S_1,S_2)$ when $L(2)(S_1,S_2) \leq \max(cn,cm) / b$: consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = (01)^{p} (00)^{n-p}$.

When $L(2)(S_1,S_2) > \max(cn,cm) / b$, you cannot avoid $L(2^b)(S_1,S_2) = \max(cn,cm) / b$. Consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = 1^{2n}$.

  • $\begingroup$ I think that the same observations hold for LCS distance, but I have not carefully checked. $\endgroup$
    – Boson
    Feb 16 '16 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.