Prefix Edit Distance

Formula#

Computation. Fill the same DP table $M$ as for ED, with $M[i][j] = \mathrm{ED}(x[1..i], y[1..j])$. The last row holds $M[|x|][j] = \mathrm{ED}(x, y[1..j])$, so

the minimum of the last row instead of the bottom-right entry. Time $O(|x| \cdot |y|)$.

Column cut-off. To decide $\mathrm{PED}(x, y) \le \delta$ for a threshold $\delta$, only the first $|x| + \delta + 1$ columns (column $\varepsilon$ and $y[1..j]$ for $j \le |x| + \delta$) are needed:

Properties#

• $\mathrm{PED}(x, y) \le \mathrm{ED}(x, y)$, since $y$ is a prefix of itself.
• Not symmetric: in general $\mathrm{PED}(x, y) \ne \mathrm{PED}(y, x)$. E.g. $\mathrm{PED}(\text{br}, \text{breisgau}) = 0$, but $\mathrm{PED}(\text{breisgau}, \text{br}) = \mathrm{ED}(\text{breisgau}, \text{br}) = 6$ (every prefix of br is at least 6 characters shorter).
• No length bound: $\mathrm{PED}(x, y) \ge \bigl|\,|x| - |y|\,\bigr|$ does not hold: $\mathrm{PED}(\text{br}, \text{breisgau}) = 0$ but $\bigl|\,|x| - |y|\,\bigr| = 6$.
• Padding: left-padding both strings with the same $q-1$ $ keeps PED unchanged; right-padding does not (see Q-Gram > Padding).
• PED is the relevance model for fuzzy search-as-you-type: the typed text $x$ is an incomplete, possibly misspelled prefix of the intended word. Large web search engines all offer this; the entity search on wikidata.org does not.

Example#

• $\mathrm{PED}(\text{uni}, \text{university}) = 0$ ($y' = \text{uni}$), but $\mathrm{ED} = 7$.
• $\mathrm{PED}(\text{uniwer}, \text{university}) = 1$ ($y' = \text{univer}$), but $\mathrm{ED} = 5$.
• $\mathrm{PED}(\text{fibu}, \text{freiburg})$:

$\mathrm{PED} = \min(\text{last row}) = 2$, attained at $y' = \text{freibu}$. For the test $\mathrm{PED} \le 2$, only the columns $\varepsilon$, f, r, e, i, b, u ($4 + 2 + 1 = 7$) are needed; the entries right of the cut are $\ge 3$.

Sources#

• Slides 08, p. 12 (definition), p. 13 (computation, cut-off), p. 20 (not symmetric)
• DBIS_VL08 > Prefix Edit Distance, DBIS_VL08 > Computation
• Exams: DBIS Exam WS1314 (not published) (Task 2), DBIS Exam WS1718 (not published) (Task 3), DBIS Exam WS2122 (not published) (Tasks 3.2, 3.3), DBIS Exam WS2324 (not published) (Task 4.2)