<p>Obviously, $L(2^b) \leq L(2)$.</p>

<p>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)$.</p>

<p>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}$.</p>

<p>When $L(2)(S_1,S_2) &gt; \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}$.</p>

CC BY-SA 3.0
2016-02-16T11:40:27.563Z
I think that the same observations hold for LCS distance, but I have not carefully checked.
Boson
CC BY-SA 3.0
2016-02-16T11:39:03.567Z
2016-02-16T11:39:03.567Z
Boson
<p>Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$.</p>

<p>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)$.</p>

<p>For any $b$ such that $b&gt;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)$.</p>

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

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

<edit-distance>
Relation between edit distances over different alphabets
Turbo
# Relation between edit distances over different alphabets

(Asked by: username_0 on 2016-02-16)

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?

**Tags:** edit-distance


---

## 1 answers

### Answer by username_1 on 2016-02-16. Score: 1

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}$.

> **Comments:**
> **username_1**: I think that the same observations hold for LCS distance, but I have not carefully checked.  

---

