Solusi D.8.1.
Untuk awalan sepanjang \(i\) dan \(j\text{,}\) definisikan \(D(i,j)\) sebagai jarak keduanya. Nilai batasnya \(D(i,0)=i\) dan \(D(0,j)=j\text{.}\) Jika huruf terakhir sama, letakkan \(\epsilon_{ij}=0\text{;}\) jika berbeda, letakkan \(\epsilon_{ij}=1\text{.}\) Meninjau operasi terakhir memberi rekurensi
\begin{equation*}
D(i,j)=\min\{D(i-1,j)+1,\ D(i,j-1)+1,\ D(i-1,j-1)+\epsilon_{ij}\}.
\end{equation*}
Argumen berdasarkan operasi terakhir menunjukkan bahwa setiap urutan edit masuk ke salah satu dari tiga kasus ini; karena itu, tabel tersebut memberi batas bawah sekaligus batas atas.
Untuk sumber “tupotagry”, baris terakhir tabel, mulai dari awalan sasaran kosong, adalah
\begin{align*}
\text{topography}: \amp (9,8,7,7,6,5,4,4,5,6,5),\\
\text{topology}: \amp (9,8,7,7,6,6,6,5,4),\\
\text{tautology}: \amp (9,8,7,7,7,7,7,7,6,5).
\end{align*}
Unsur terakhir memberi jarak \(5,4,5\text{.}\) Batas atas itu juga tampak pada urutan edit berikut; setiap anak panah adalah satu operasi:
“tupotagry” → “topotagry” → “topogtagry” → “topogragry” → “topograpry” → “topography”;
“tupotagry” → “topotagry” → “topolagry” → “topologry” → “topology”;
“tupotagry” → “taupotagry” → “tautotagry” → “tautolagry” → “tautologry” → “tautology”. Karena nilai minimum terkecil adalah empat dan hanya dimiliki “topology”, itulah koreksi menurut aturan tetangga terdekat.