% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

%\newcommand{\code}[1]{\texttt{#1}}

\begin{document}

\title{Levenshteins Edit–Distanz}
%\ifx\shorttitle\undefined\else
%\shorttitle{}
%\fi
\author{Ulrich Hoffmann}
\maketitle

Wie findet man Schreibfehler in seiner elektronischen CD--Sammlung oder den Mitgliederlisten der Forth--Gesellschaft?
Für Texte bieten moderne Betriebssysteme bzw. Office--Pakete Rechtschreibprüfungen an, aber wie konfiguriert man die für Spezialaufgaben? Schöner wäre es, wenn man den Kern einer Rechtschreibprüfung in Forth hätte, um damit speziell zugeschnittene
Überprüfer programmieren zu können. Unten findet sich die Definition der Edit--Distanz, die Wladimir Lewenstein 1965 definiert hat und die eine gute Basis für eine Spezial--Rechtschreibprüfung bilden kann.

\begin{multicols}{2}

\section{Levenshtein-Distanz}
Die Levenshtein--Distanz ist ein Maß für den Unterschied zweier Text--Strings,
bei dem gezählt wird, wieviele der elementaren Zeichen--Editier--Operationen ---
\begin{itemize}
\item Ersetzen: ein Zeichen wird durch genau ein anderes Zeichen ersetzt,
\item Einfügen: ein Zeichen muss eingefügt werden und
\item Löschen: ein Zeichen muss gelöscht werden ---
\end{itemize} 
verwendet werden müssen, um den einen String in den anderen zu überführen.

Zum Beispiel benötigt man 2 Operationen, um den Text \emph{Forth} in den Text \emph{Forst} zu
verwandeln:
\begin{enumerate}
  \item \emph{Forth} $\rightarrow$ \emph{Forsth} (\emph{s} einfügen) und  
  \item \emph{Forth} $\rightarrow$ \emph{Forst}  (\emph{h} löschen).
\end{enumerate}

Der Standard--Algorithmus für die Levenshtein--Distanz bedient sich einer $(m+1)\times (n+1)$--Matrix $D$ ($m,n$ sind die Längen der zu vergleichenden Strings), die nach folgender Rekursionsgleichung berechnet wird:
\columnbreak
\begin{eqnarray*}
D_{i,0} &=& i\ \ \mathrm{f"ur\ alle}\ i\in\{0,\ldots, m\}\\
D_{0,j} &=& j\ \ \mathrm{f"ur\ alle}\ j\in\{0,\ldots, n\}\\
D_{i,j} &=& \min\left\{
                \begin{array}{lll}
                  D_{i-1,j-1} & +\ 0\ & \textrm{gleicher Buchstabe}\\
                  D_{i-1,j-1} & +\ 1\ & \textrm{ersetzen}\\
                  D_{i,j-1}   & +\ 1\ & \textrm{einfügen}\\
                  D_{i-1,j}   & +\ 1\ & \textrm{löschen}\\
                \end{array}
             \right.\\
        & & \mathrm{f"ur\ alle}\ i\in\{1,\ldots, m\}\ \mathrm{und}\ j\in\{1,\ldots, n\},
\end{eqnarray*}
wobei schließlich in $D_{m,n}$ der Wert der Levenshtein--Distanz berechnet wird.

\section*{Schreibfehlererkennung}
Wie kann man nun mit der Levenshtein--Distanz Schreibfehler erkennen?
Nun --- man vergleicht die Worte mit einer Referenz--Menge, im einfachsten Fall mit sich selbst, und betrachtet die Worte, die eine Edit-Distanz zwischen 1 und 2 haben. Bei 1 ist möglicherweise ein Buchstabe falsch, bei 2 hat man eventuell einen Buchstabendreher. Es ist erstaunlich, wie viele Fehler sich schon mit dieser einfachen Methode finden lassen\ldots
\end{multicols}

\section*{Links}
\begin{tabular}{lp{16cm}}
{[1]} &Levenshtein-Distanz, Wikipedia, \url{http://de.wikipedia.org/wiki/Levenshtein-Distanz}\\
{[2]} &Vladimir I. Levenshtein: Binary codes capable of correcting deletions, insertions, and reversals. In: Doklady Akademii Nauk SSSR, 163(4) S. 845–848, 1965 (Russisch). Englische Übersetzung in: Soviet Physics Doklady, 10(8) S. 707–710, 1966.
\end{tabular}

\section{Listing}
\begin{small}
\begin{quote}
\listinginput{1}{2009-03/levenshtein.fs}
\end{quote}
\end{small}

%\end{document}