Distance in the abstract

The first question we need to ask is “what could it mean for a string to be close to (or far from) another one?” To answer this, let’s consider what it means to be close in other domains.

Real numbers

Suppose we have two numbers $a, b \in \mathbb{R}$. How might we define the distance between them?

We could compute equality.

\[d_\text{eq}(a, b) = \begin{cases} 0 & \text{if } a = b\\1 & \text{otherwise}\end{cases}\]

Or we could compute the absolute difference.

\[d_\text{abs}(a, b) = |a - b|\]

More generally, we could define a distance on elements of a set $E$ to be any function $d: E \times E \rightarrow \mathbb{R}_+$ that satisfies a few constraints. A set equipped with such a function is called a metric space:

The distance between an object and itself is $0$: $d(x, x) = 0$
The distance between an object and any other object is not $0$: $d(x, y) > 0$ if $x \neq y$
The order of comparison doesn’t matter: $d(x, y) = d(y, x)$ (symmetry)
The distance between two elements is no more than the distance between the first element and any other element plus the distance between the second element and that other element: $d(x, y) \leq d(x, z) + d(z, y)$ (subadditivity or triangle inequality)

Metric geometry studies spaces equipped with functions like $d$, while topology studies more general ways of representing which points are near one another. For our purposes, the metric-space definition is enough.

Vectors of real numbers

Now, suppose we have two vectors of real numbers $\mathbf{a}, \mathbf{b} \in \mathbb{R}^M$—basically, tuples of real numbers. How might we define the distance between them?

Well, when $M=2$, that’s just a point in a two-dimensional plane.

import numpy as np
import matplotlib.pyplot as plt

a = [0,0]
b = [1,1]

ab = np.array([a, b])

ab

_ = plt.scatter(ab[:,0], ab[:,1])

We could again check for equality by checking for equality on each dimension.

\[d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } d_\text{eq}(a_1, b_1) = 0 \text{ and } d_\text{eq}(a_2, b_2) = 0\\1 & \text{otherwise}\end{cases}\]

Or we could again check for absolute difference, by checking for absolute difference on each dimension and then summing.

\[d_\text{abs-vec}(\mathbf{a}, \mathbf{b}) = d_\text{abs}(a_1, b_1) + d_\text{abs}(a_2, b_2) = |a_1 - b_1| + |a_2 - b_2|\]

This is called the Manhattan (or city block) distance.

_ = plt.plot([a[0], b[0]], [a[1], a[1]])
_ = plt.plot([b[1], b[1]], [a[1], b[1]])
_ = plt.scatter(ab[:,0], ab[:,1])

Or we could compute the Euclidean distance.

\[d_\text{euc}(a, b) = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2}\]

_ = plt.scatter(ab[:,0], ab[:,1])
_ = plt.plot(ab[:,0], ab[:,1])

We could get even fancier by noticing that the absolute difference and Euclidean distance can be generalized—e.g. to the Minkowski $p$-norm for some $p$.

\[d_{\text{mink}, p}(\mathbf{a}, \mathbf{b}) = \sqrt[p]{\sum_i |a_i - b_i|^p},\qquad p\geq1.\]

where absolute difference is the case where $p=1$ and the Euclidean distance is the case where $p=2$. (And this isn’t even near as fancy as we can get.)

Difficulties with strings

The reason for going through all of this is to notice:

There are many reasonable notions of the distance between two things, even when we’re talking about relatively simple things like points in a plane.
Once we have a reasonable notion, we can often parameterize it, providing us with an infinite family of related metrics.

Both points are important for understanding string distance because we can think of strings as being something like the vectors we discussed above.

There are two main differences between strings and real-valued vectors though:

The symbols in an alphabet need not have an intrinsic ordering. And even if we impose one (e.g. by mapping symbols to their ASCII or Unicode code points), it isn’t clear that the resulting ordering is linguistically useful. We could define lexicographic distance, but the order of the alphabet is largely arbitrary and doesn’t reveal the properties we usually care about.
We can only compare real-valued vectors of the same dimensions with the distance metrics we just defined, but we often want to compare strings of different dimensions (i.e. lengths).

To understand how to deal with these issues, it is useful to start with Boolean vectors. Strings over a two-symbol alphabet are Boolean vectors, and strings over larger alphabets generalize them.

“Vectors” of booleans

A Boolean vector is a tuple of Boolean values $\mathbf{a} \in \mathbb{B}^M = \{\top, \bot\}^M$. Notice that the case where $M=2$ gives us the vertices of a square with sides of length 1.

a = [0,0]
b = [0,1]
c = [1,1]
d = [1,0]

abcd = np.array([a, b, c, d])
abcda = np.array([a, b, c, d, a])

_ = plt.plot(abcda[:,0], abcda[:,1])
_ = plt.scatter(abcd[:,0], abcd[:,1])

In the case where $M=3$, we get a cube; $M=4$ gives us a tesseract, etc. More generally, we refer to anything of higher dimension than a cube as an $M$-hypercube.

So how do we compute distance on boolean vectors? Let’s start with equality: how do we compute it? A natural way is the biconditional:

$d_{eq}(a, b) = \begin{cases}0 & \text{if } a \leftrightarrow b \\1 & \text{otherwise}\end{cases}$

This may look backward, but remember that (i) $d$ is supposed to be a distance, so equal elements must be at distance $0$; and (ii) $d$ has a real-valued codomain, even though its range is just $\{0, 1\}$. The definition has the same truth table as XOR if we identify $\bot$ with $0$ and $\top$ with $1$. But it is still useful to distinguish the distance function, whose outputs are real numbers, from the Boolean connective, whose outputs are truth values.

Now that we have a notion of distance for booleans, we can do the same thing we did for the real numbers:

\[d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } d_\text{eq}(a_1, b_1) = 0 \text{ and } d_\text{eq}(a_2, b_2) = 0\\1 & \text{otherwise}\end{cases}\]

And notice that if $M>2$, we can actually just generalize this to:

\[d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } \bigwedge_i \bigl(d_\text{eq}(a_i, b_i)=0\bigr)\\1 & \text{otherwise}\end{cases}\]

The set $\{0,1\}^M$ can also be treated as a vector space over the two-element field, provided that addition and multiplication are defined modulo $2$. We don’t need that vector-space structure to define Hamming distance. We need only be able to decide whether two symbols are equal.

So here’s a question: can we similarly define a reasonable distance that acts more like absolute difference? Sure. Instead of asking for strict equality at the vector level, we can count up the distances at the element level.

\[d_\text{abs-vec}(\mathbf{a}, \mathbf{b}) = \sum_i d_\text{eq}(a_i, b_i)\]

This is alternatively known as the Hamming distance.

So here’s why the thing about $M=2$ being a square, $M=3$ being a cube, etc. matters: basically what we’re doing here is counting how many sides of the square, cube, etc. we have to travel to get from one point to the other.

We can verify that this is a metric one condition at a time. Fix arbitrary $\mathbf{a},\mathbf{b},\mathbf{c}\in\mathbb{B}^M$, and write $[P]$ for $1$ when the proposition $P$ is true and $0$ otherwise. Then Hamming distance is

\[d_H(\mathbf{a},\mathbf{b})=\sum_{i=1}^M[a_i\neq b_i].\]

First, every summand is nonnegative, so $d_H(\mathbf{a},\mathbf{b})\geq0$. Second, $d_H(\mathbf{a},\mathbf{b})=0$ if and only if every summand is $0$. This happens if and only if $a_i=b_i$ at every coordinate, which is exactly the condition $\mathbf{a}=\mathbf{b}$. Third, $[a_i\neq b_i]=[b_i\neq a_i]$ at each coordinate. Summing these equalities gives $d_H(\mathbf{a},\mathbf{b})=d_H(\mathbf{b},\mathbf{a})$.

The triangle inequality is the only condition that requires an argument. Fix an arbitrary coordinate $i$. If $a_i=b_i$, then

\[[a_i\neq b_i]=0\leq[a_i\neq c_i]+[c_i\neq b_i].\]

If $a_i\neq b_i$, $c_i$ cannot equal both of them. At least one of $a_i\neq c_i$ and $c_i\neq b_i$ must thus hold, giving

\[[a_i\neq b_i]=1\leq[a_i\neq c_i]+[c_i\neq b_i].\]

The coordinatewise inequality holds in both cases. Summing it over all $M$ coordinates yields

\[d_H(\mathbf{a},\mathbf{b})\leq d_H(\mathbf{a},\mathbf{c})+d_H(\mathbf{c},\mathbf{b}).\]

Thus, Hamming distance satisfies nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality. It is a metric on $\mathbb{B}^M$.

The thing to notice here is that we didn’t need an ordering on the Boolean elements. Equality was enough. And we weren’t forced to return only $0$ or $1$, since we could count the coordinatewise mismatches.

Okay, so what if we want to compare Boolean vectors of different lengths? Suppose we have a vector $\mathbf{a} \in \mathbb{B}^2$ and another $\mathbf{b} \in \mathbb{B}^3$.

Let’s return to the idea about squares and cubes: $\mathbf{a}$ would be a vertex of a square while $\mathbf{b}$ would be a vertex of a cube. But a square can be embedded as a face of a cube. That gives us a possible strategy.

The basic idea is to ask: what if I treated $\mathbf{a}$ as denoting a vertex of the cube containing $\mathbf{b}$? Then I could compute the distance between the two using the distance we already defined.

The complication is deciding how to map $\mathbf{a}$ to a cube vertex. Here are three possibilities.

If you’re mapping $\mathbf{a}$ from $\mathbb{B}^M$ to $\mathbb{B}^N$, where $N>M$, for comparison to $\mathbf{b} \in \mathbb{B}^N$…

Add $N-M$ $\bot$s (or $\top$s) to the beginning or end of $\mathbf{a}$
Add the first (or last) $N-M$ elements of $\mathbf{b}$ to the beginning (or end) of $\mathbf{a}$
Copy $N-M$ elements of $\mathbf{b}$ into $\mathbf{a}$ (in order), slotting them between any two elements of $\mathbf{a}$ so that the distance between the two is minimized.

These all involve choosing a “face” of the higher dimensional thing to compare $\mathbf{a}$ to $\mathbf{b}$ on. The first just chooses the same face every time. The second chooses the the face dependent on $\mathbf{b}$ and will always result in a distance that is no longer than the one computed for the first, but it is not necessarily optimal. The last one will give us the shortest distance possible (by definition), but it is significantly more complicated to compute. You can get a sense for this by considering how many different ways you can spin a cube around to try to match a face.

Of course, we could go in the other direction. Instead of treating $\mathbf{a}$ as a cube vertex, we could treat $\mathbf{b}$ as a square vertex by deleting coordinates. But the same challenge comes up: which coordinates do we delete?

Delete $N-M$ elements from the beginning or end of $\mathbf{b}$.
Delete the $N-M$ elements at some fixed set of positions in $\mathbf{b}$.
Delete $N-M$ elements from $\mathbf{b}$ so that the distance between $\mathbf{a}$ and $\mathbf{b}$ is minimized.

There is a problem with letting the direction of comparison determine the operation. Deleting from the longer vector gives at most $M$ coordinatewise mismatches, while adding to the shorter vector gives at most $N$. The two directions can thus give different answers, violating symmetry. We could define a canonical direction, but methods 1 and 2 would still require an arbitrary choice of where to add or delete coordinates.

Method 3 handles the alignment problem, but it introduces another one. If inserted symbols are copied from the longer vector and insertion itself costs nothing, then two unequal vectors can have distance $0$. For instance, $(\top)$ can be aligned perfectly with the first coordinate of $(\top,\bot)$, leaving the copied $\bot$ with no cost. The result violates identity of indiscernibles. We thus need to assign a positive cost to insertions and deletions, and those costs must be the same if the resulting distance is to be symmetric. This is exactly the move made by edit distance.

The problem is figuring out the best insertion or deletion alignment. In either direction, an order-preserving alignment of an $M$-element vector with $M$ of the $N$ positions is determined by choosing those positions. There are

\[\binom{N}{M}=\binom{N}{N-M}\]

such choices. In the insertion view, the remaining $N-M$ positions are filled from the corresponding positions of $\mathbf{b}$; there is no second independent choice. In the deletion view, they are exactly the positions deleted from $\mathbf{b}$. For instance, aligning a one-element vector with a three-element vector gives $\binom31=3$ possibilities, whereas the old product count would incorrectly give $\binom12\binom32=0$. Checking all alignments naively still requires $M\binom{N}{M}$ element comparisons.

It turns out there’s a better way, which we’ll see in a second. But first, how does any of this relate to strings?

Strings

Everything we just discussed about boolean vectors can be thought of in terms of strings by thinking of boolean vectors as strings from an alphabet with two elements: $\top$ and $\bot$. And indeed, Hamming distance (the analogue of absolute difference we talked about earlier) is straightforwardly defined for strings by replacing the element-wise biconditional with element-wise equality.

The reason to go through boolean vectors first is strings built from alphabets with more than two elements are hard to visualize, but the idea is basically the same: when we’ve got strings of different lengths, how do we determine how we should insert and/or delete elements? That is the question that Levenshtein distance answers.

--- title: Distance in the abstract --- The first question we need to ask is "what could it mean for a string to be *close* to (or *far from*) another one?" To answer this, let's consider what it means to be close in other domains. ### Real numbers Suppose we have two numbers $a, b \in \mathbb{R}$. How might we define the distance between them? We could compute equality. $$d_\text{eq}(a, b) = \begin{cases} 0 & \text{if } a = b\\1 & \text{otherwise}\end{cases}$$ Or we could compute the absolute difference. $$d_\text{abs}(a, b) = |a - b|$$ More generally, we could define a distance on elements of a set $E$ to be any function $d: E \times E \rightarrow \mathbb{R}_+$ that satisfies a few constraints. A set equipped with such a function is called a [metric space](https://en.wikipedia.org/wiki/Metric_space): 1. The distance between an object and itself is $0$: $d(x, x) = 0$ 2. The distance between an object and any other object is not $0$: $d(x, y) > 0$ if $x \neq y$ 3. The order of comparison doesn't matter: $d(x, y) = d(y, x)$ (*symmetry*) 4. The distance between two elements is no more than the distance between the first element and any other element plus the distance between the second element and that other element: $d(x, y) \leq d(x, z) + d(z, y)$ (*subadditivity* or *triangle inequality*) [Metric geometry](https://en.wikipedia.org/wiki/Metric_geometry) studies spaces equipped with functions like $d$, while topology studies more general ways of representing which points are near one another. For our purposes, the metric-space definition is enough. ### Vectors of real numbers Now, suppose we have two vectors of real numbers $\mathbf{a}, \mathbf{b} \in \mathbb{R}^M$—basically, tuples of real numbers. How might we define the distance between them? Well, when $M=2$, that's just a point in a two-dimensional plane. ```{python} import numpy as np import matplotlib.pyplot as plt a = [0,0] b = [1,1] ab = np.array([a, b]) ab ``` ```{python} _ = plt.scatter(ab[:,0], ab[:,1]) ``` We could again check for equality by checking for equality on each dimension. $$d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } d_\text{eq}(a_1, b_1) = 0 \text{ and } d_\text{eq}(a_2, b_2) = 0\\1 & \text{otherwise}\end{cases}$$ Or we could again check for absolute difference, by checking for absolute difference on each dimension and then summing. $$d_\text{abs-vec}(\mathbf{a}, \mathbf{b}) = d_\text{abs}(a_1, b_1) + d_\text{abs}(a_2, b_2) = |a_1 - b_1| + |a_2 - b_2|$$ This is called the Manhattan (or city block) distance. ```{python} _ = plt.plot([a[0], b[0]], [a[1], a[1]]) _ = plt.plot([b[1], b[1]], [a[1], b[1]]) _ = plt.scatter(ab[:,0], ab[:,1]) ``` Or we could compute the Euclidean distance. $$d_\text{euc}(a, b) = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2}$$ ```{python} _ = plt.scatter(ab[:,0], ab[:,1]) _ = plt.plot(ab[:,0], ab[:,1]) ``` We could get even fancier by noticing that the absolute difference and Euclidean distance can be generalized—e.g. to the Minkowski $p$-norm for some $p$. $$d_{\text{mink}, p}(\mathbf{a}, \mathbf{b}) = \sqrt[p]{\sum_i |a_i - b_i|^p},\qquad p\geq1.$$ where absolute difference is the case where $p=1$ and the Euclidean distance is the case where $p=2$. (And this isn't even near as [fancy](https://en.wikipedia.org/wiki/Hilbert_space) as we can get.) ### Difficulties with strings The reason for going through all of this is to notice: 1. There are many reasonable notions of the distance between two things, even when we're talking about relatively simple things like points in a plane. 2. Once we have a reasonable notion, we can often *parameterize* it, providing us with an infinite family of related metrics. Both points are important for understanding string distance because we can think of strings as being something like the vectors we discussed above. There are two main differences between strings and real-valued vectors though: 1. The symbols in an alphabet need not have an intrinsic ordering. And even if we impose one (e.g. by mapping symbols to their ASCII or Unicode code points), it isn't clear that the resulting ordering is linguistically useful. We could define lexicographic distance, but the order of the alphabet is largely arbitrary and doesn't reveal the properties we usually care about. 2. We can only compare real-valued vectors of the same dimensions with the distance metrics we just defined, but we often want to compare strings of different dimensions (i.e. lengths). To understand how to deal with these issues, it is useful to start with Boolean vectors. Strings over a two-symbol alphabet are Boolean vectors, and strings over larger alphabets generalize them. ### "Vectors" of booleans A Boolean vector is a tuple of Boolean values $\mathbf{a} \in \mathbb{B}^M = \{\top, \bot\}^M$. Notice that the case where $M=2$ gives us the vertices of a square with sides of length 1. ```{python} a = [0,0] b = [0,1] c = [1,1] d = [1,0] abcd = np.array([a, b, c, d]) abcda = np.array([a, b, c, d, a]) _ = plt.plot(abcda[:,0], abcda[:,1]) _ = plt.scatter(abcd[:,0], abcd[:,1]) ``` In the case where $M=3$, we get a cube; $M=4$ gives us a tesseract, etc. More generally, we refer to anything of higher dimension than a cube as an $M$-hypercube. So how do we compute distance on boolean vectors? Let's start with equality: how do we compute it? A natural way is the biconditional: $d_{eq}(a, b) = \begin{cases}0 & \text{if } a \leftrightarrow b \\1 & \text{otherwise}\end{cases}$ This may look backward, but remember that (i) $d$ is supposed to be a distance, so equal elements must be at distance $0$; and (ii) $d$ has a real-valued codomain, even though its range is just $\{0, 1\}$. The definition has the same truth table as XOR if we identify $\bot$ with $0$ and $\top$ with $1$. But it is still useful to distinguish the distance function, whose outputs are real numbers, from the Boolean connective, whose outputs are truth values. Now that we have a notion of distance for booleans, we can do the same thing we did for the real numbers: $$d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } d_\text{eq}(a_1, b_1) = 0 \text{ and } d_\text{eq}(a_2, b_2) = 0\\1 & \text{otherwise}\end{cases}$$ And notice that if $M>2$, we can actually just generalize this to: $$d_\text{eq-vec}(\mathbf{a}, \mathbf{b}) = \begin{cases} 0 & \text{if } \bigwedge_i \bigl(d_\text{eq}(a_i, b_i)=0\bigr)\\1 & \text{otherwise}\end{cases}$$ The set $\{0,1\}^M$ can also be treated as a vector space over the [two-element field](https://en.wikipedia.org/wiki/GF(2)), provided that addition and multiplication are defined modulo $2$. We don't need that vector-space structure to define Hamming distance. We need only be able to decide whether two symbols are equal. So here's a question: can we similarly define a reasonable distance that acts more like absolute difference? Sure. Instead of asking for strict equality at the vector level, we can count up the distances at the element level. $$d_\text{abs-vec}(\mathbf{a}, \mathbf{b}) = \sum_i d_\text{eq}(a_i, b_i)$$ This is alternatively known as the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance). So here's why the thing about $M=2$ being a square, $M=3$ being a cube, etc. matters: basically what we're doing here is counting how many sides of the square, cube, etc. we have to travel to get from one point to the other. We can verify that this is a metric one condition at a time. Fix arbitrary $\mathbf{a},\mathbf{b},\mathbf{c}\in\mathbb{B}^M$, and write $[P]$ for $1$ when the proposition $P$ is true and $0$ otherwise. Then Hamming distance is $$d_H(\mathbf{a},\mathbf{b})=\sum_{i=1}^M[a_i\neq b_i].$$ First, every summand is nonnegative, so $d_H(\mathbf{a},\mathbf{b})\geq0$. Second, $d_H(\mathbf{a},\mathbf{b})=0$ if and only if every summand is $0$. This happens if and only if $a_i=b_i$ at every coordinate, which is exactly the condition $\mathbf{a}=\mathbf{b}$. Third, $[a_i\neq b_i]=[b_i\neq a_i]$ at each coordinate. Summing these equalities gives $d_H(\mathbf{a},\mathbf{b})=d_H(\mathbf{b},\mathbf{a})$. The triangle inequality is the only condition that requires an argument. Fix an arbitrary coordinate $i$. If $a_i=b_i$, then $$[a_i\neq b_i]=0\leq[a_i\neq c_i]+[c_i\neq b_i].$$ If $a_i\neq b_i$, $c_i$ cannot equal both of them. At least one of $a_i\neq c_i$ and $c_i\neq b_i$ must thus hold, giving $$[a_i\neq b_i]=1\leq[a_i\neq c_i]+[c_i\neq b_i].$$ The coordinatewise inequality holds in both cases. Summing it over all $M$ coordinates yields $$d_H(\mathbf{a},\mathbf{b})\leq d_H(\mathbf{a},\mathbf{c})+d_H(\mathbf{c},\mathbf{b}).$$ Thus, Hamming distance satisfies nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality. It is a metric on $\mathbb{B}^M$. The thing to notice here is that we didn't need an ordering on the Boolean elements. Equality was enough. And we weren't forced to return only $0$ or $1$, since we could count the coordinatewise mismatches. Okay, so what if we want to compare Boolean vectors of different lengths? Suppose we have a vector $\mathbf{a} \in \mathbb{B}^2$ and another $\mathbf{b} \in \mathbb{B}^3$. Let's return to the idea about squares and cubes: $\mathbf{a}$ would be a vertex of a square while $\mathbf{b}$ would be a vertex of a cube. But a square can be embedded as a face of a cube. That gives us a possible strategy. The basic idea is to ask: what if I treated $\mathbf{a}$ as denoting a vertex of the cube containing $\mathbf{b}$? Then I could compute the distance between the two using the distance we already defined. The complication is deciding how to map $\mathbf{a}$ to a cube vertex. Here are three possibilities. If you're mapping $\mathbf{a}$ from $\mathbb{B}^M$ to $\mathbb{B}^N$, where $N>M$, for comparison to $\mathbf{b} \in \mathbb{B}^N$... 1. Add $N-M$ $\bot$s (or $\top$s) to the beginning or end of $\mathbf{a}$ 2. Add the first (or last) $N-M$ elements of $\mathbf{b}$ to the beginning (or end) of $\mathbf{a}$ 3. Copy $N-M$ elements of $\mathbf{b}$ into $\mathbf{a}$ (in order), slotting them between any two elements of $\mathbf{a}$ so that the distance between the two is minimized. These all involve choosing a "face" of the higher dimensional thing to compare $\mathbf{a}$ to $\mathbf{b}$ on. The first just chooses the same face every time. The second chooses the the face dependent on $\mathbf{b}$ and will always result in a distance that is no longer than the one computed for the first, but it is not necessarily optimal. The last one will give us the shortest distance possible (by definition), but it is significantly more complicated to compute. You can get a sense for this by considering how many different ways you can spin a cube around to try to match a face. Of course, we could go in the other direction. Instead of treating $\mathbf{a}$ as a cube vertex, we could treat $\mathbf{b}$ as a square vertex by deleting coordinates. But the same challenge comes up: which coordinates do we delete? 1. Delete $N-M$ elements from the beginning or end of $\mathbf{b}$. 2. Delete the $N-M$ elements at some fixed set of positions in $\mathbf{b}$. 3. Delete $N-M$ elements from $\mathbf{b}$ so that the distance between $\mathbf{a}$ and $\mathbf{b}$ is minimized. There is a problem with letting the direction of comparison determine the operation. Deleting from the longer vector gives at most $M$ coordinatewise mismatches, while adding to the shorter vector gives at most $N$. The two directions can thus give different answers, violating symmetry. We could define a canonical direction, but methods 1 and 2 would still require an arbitrary choice of where to add or delete coordinates. Method 3 handles the alignment problem, but it introduces another one. If inserted symbols are copied from the longer vector and insertion itself costs nothing, then two unequal vectors can have distance $0$. For instance, $(\top)$ can be aligned perfectly with the first coordinate of $(\top,\bot)$, leaving the copied $\bot$ with no cost. The result violates identity of indiscernibles. We thus need to assign a positive cost to insertions and deletions, and those costs must be the same if the resulting distance is to be symmetric. This is exactly the move made by edit distance. The problem is figuring out the best insertion or deletion alignment. In either direction, an order-preserving alignment of an $M$-element vector with $M$ of the $N$ positions is determined by choosing those positions. There are $$\binom{N}{M}=\binom{N}{N-M}$$ such choices. In the insertion view, the remaining $N-M$ positions are filled from the corresponding positions of $\mathbf{b}$; there is no second independent choice. In the deletion view, they are exactly the positions deleted from $\mathbf{b}$. For instance, aligning a one-element vector with a three-element vector gives $\binom31=3$ possibilities, whereas the old product count would incorrectly give $\binom12\binom32=0$. Checking all alignments naively still requires $M\binom{N}{M}$ element comparisons. It turns out there's a better way, which we'll see in a second. But first, how does any of this relate to strings? ### Strings Everything we just discussed about boolean vectors can be thought of in terms of strings by thinking of boolean vectors as strings from an alphabet with two elements: $\top$ and $\bot$. And indeed, Hamming distance (the analogue of absolute difference we talked about earlier) is straightforwardly defined for strings by replacing the element-wise biconditional with element-wise equality. The reason to go through boolean vectors first is strings built from alphabets with more than two elements are hard to visualize, but the idea is basically the same: when we've got strings of different lengths, how do we determine how we should insert and/or delete elements? That is the question that [Levenshtein distance](levenshtein-distance.qmd) answers.