Rechtschreibprüfung mit BK-Bäumen

Von Julian Sauer

- 9 Minuten - 1758 Wörter

Einleitung

Ach wie scjön eine autoamtische Rechtschreiborüfung wäre, die Tippfehler und Buchstabendreher wie im ersten Teil des Satzes finden würde.

Leider habe ich kein Plugin für die deutsche Sprache in meinem Texteditor installiert. Das liegt allerdings nicht an einem Mangel von Lösungen. In Form von Burkhard-Keller-Bäumen gibt es bereits seit 1973 eine verhältnismäßig einfache Struktur zur Rechtschreibprüfung. Ein Suchradius legt fest, wie viele falsche Buchstaben enthalten sein dürfen. Anschließend liefert eine Suche im Baum alle ähnlichen Wörter. Der große Vorteil besteht darin, dass nur ein kleiner Teil der Wörter im Baum betrachten muss. Es ist also nicht nötig, jedes geschriebene Wort mit dem gesamten Wortschatz der deutschen Sprache abzugleichen.

Bevor wir uns im zweiten Kapitel der Baumstruktur widmen, schauen wir uns zunächst den angesprochenen Suchradius an. Abschließend gibt es eine simple Implementierung mit Kotlin und einen kurzen Test.

Inhaltsverzeichnis

  1. Levenshtein-Distanz
  2. Burkhard-Keller-Bäume
    1. Aufbau
    2. Suche
  3. Implementierung in Kotlin
    1. Levenshtein-Distanz
    2. Einfügen
    3. Suche
    4. Benchmark
  4. Fazit

Levenshtein-Distanz

Sie gibt an, wie viele Buchstaben eingefügt, gelöscht oder ersetzt werden müssen, um ein Wort in ein anderes zu verwandeln. Die Distanz zwischen book und books beträgt beispielsweise 1, da wir zum ersten Wort einen Buchstaben hinzufügen müssen, um das Zweite zu erhalten. Genauer gesagt vergleichen wir zwei Wörter zeichenweise und schauen, welcher Fall zutrifft:

  1. Eines der Wörter besteht aus 0 Buchstaben, die Distanz ist die Anzahl der Buchstaben des anderen Wortes.
  2. Der jeweils erste Buchstabe zweier Wörter ist gleich, also wird er entfernt und die Distanz zwischen den beiden Wortresten berechnet.
  3. Der jeweils erste Buchstabe ist unterschiedlich. Die Distanz ist 1 plus dem Minimum der
    1. Distanz der beiden Wörter ohne den ersten Buchstaben des ersten Wortes
    2. Distanz der beiden Wörter ohne den ersten Buchstaben des zweiten Wortes
    3. Distanz der beiden Wörter ohne den ersten Buchstaben beider Wörter

Burkhard-Keller-Bäume

Für unsere Rechtschreibprüfung könnten wir die Levenshtein-Distanz zwischen einem eingegebenen Wort und jedem Wort im Wörterbuch berechnen. Das Wort mit der niedrigsten Distanz ist dann unser Ergebnis. Leider haben wir uns dabei natürlich viel zu viele (alle) Wörter angeschaut.

In einem BK-Baum berechnen wir dagegen Levenshtein-Distanzen zwischen einigen Wörtern im Voraus. In der Implementierung werden wir später sehen, dass wir damit beim Suchen in einem Wörterbuch mit 1000 Wörtern und maximal zwei falschen Buchstaben ungefähr 80-90% nicht mehr betrachten müssen.

Aufbau

Als Struktur wählen wir einen gewichteten, gerichteten Baum. Er enthält pro Knoten ein Wort und als Kantengewichte die Levenshtein-Distanz zwischen den beiden Knoten.

Nun fügen wir die Wörter unseres Wörterbuchs nacheinander und in beliebiger Reihenfolge in den Baum ein. Das erste Wort wird zur Wurzel. Als nächstes berechnen wir die Levenshtein-Distanz zwischen dem einzufügenden Wort und der Wurzel. Die Wurzel hat

  1. noch keine Kante mit genau diesem Gewicht. Wir fügen sie zusammen mit dem neuen Kindknoten ein.
  2. bereits eine Kante mit genau diesem Gewicht. Wir betrachten den an ihr hängenden Teilbaum und wiederholen den Schritt des Einfügens für ihn.

Als Beispiel wollen wir einen BK-Baum für die Wörter book, books, boo, cake, boon, cook, cape und cart aufbauen. Zunächst wird book zur Wurzel:

b o o k

Die Levenshtein-Distanz zwischen book und books beträgt 1, wir fügen eine entsprechende Kante zum neuen Wort ein:

1 b o o k s b o o k

Die Distanz zwischen dem nächsten Wort boo und der Wurzel book ist ebenfalls 1. Da book bereits eine Kante nach books mit dem Gewicht 1 hat, versuchen wir boo im Teilbaum von books unterzubringen. Die Distanz zwischen boo und books ist 2, außerdem hat books noch keinen Kindknoten mit dem Gewicht 2. Also können wir boo als Kindknoten einfügen:

1 b 2 o b o o k o s b o o k

Das Wort cake lässt sich wieder einfacher einfügen. Denn die Distanz zu book beträgt 4 und eine entsprechende Kante hat book noch nicht:

1 b 2 o b o o k o s b o o k 4 c a k e

Die nächsten beiden Wörter boon und cook haben beide eine Distanz von 1 zu book. Also folgen wir der Kante mit dem Gewicht 1 und berechnen die Distanz zu books. Sie beträgt 2, auch diese Kante haben wir schon. Letztlich fügen wir die beiden Wörter als Kinder von boo ein, denn die Distanz zu boon beträgt 1 und 2 zu cook:

1 b o o n 1 b 2 o b o o k o s 2 c o o k b o o k 4 c a k e

Die Wörter cape und cart haben eine Distanz von 4 zu book, genauso wie cake. Also landen sie im Teilbaum von cake:

1 b o o n 1 b 2 o b o o k o s 2 c o o k b o o k 1 c a p e 4 c a k e 2 c a r t

Suche

Nachdem wir jetzt unseren BK-Baum aufgebaut haben, können wir ihn zur Suche von ähnlichen Wörtern zu Rate ziehen. Dafür hilft zunächst die Erkenntnis, dass für die Levenshtein-Distanz die Dreiecksungleichung gilt. Betrachten wir drei Wörter x, y und z, dann ist die Distanz zwischen x und y maximal so groß wie die Summe der Distanzen von x nach z und von z nach y:

d(x, y) <= (x, z) + d(z, y)

In unserem Baum aus dem vorherigen Kapitel sehen wir das ebenfalls. Beispielsweise ist die Distanz von book nach books plus die Distanz von books nach boo insgesamt 3 und damit kleiner oder gleich der Distanz von book nach boo:

b o o k 1 s 2 b o b o o k o 1

Wollen wir jetzt nach einem Wort im Baum suchen, berechnen wir die Distanz zur Wurzel und können darauf basierend einen Suchradius festlegen: Dafür geben wir eine maximale Distanz dmax an, die die Ähnlichkeit zu unserem eingegebenen Wort bestimmt. Die Distanz zwischen Eingabe und Wurzel bezeichnen wir als dw. Dann wissen wir aufgrund der Dreiecksungleichung, dass alle möglichen Wörter mindestens eine Distanz von dmax - dw und maximal eine von dmax + dw zur Wurzel haben dürfen.

Am Beispiel von oben können wir etwa alle Wörter suchen, die sich in maximal einem Buchstaben von zoo unterscheiden.

1 b o o n 1 b 2 o b o o k o s 2 c o o k b o o k 1 c a p e 4 c a k e 2 c a r t

Wir stellen zunächst fest, dass die Distanz zwischen zoo und der Wurzel book 2 beträgt. Folglich betrachten wir alle Kanten von book, die ein Gewicht von mindestens 1 - 2 <= 0 und maximal 1 + 2 = 3 haben. Damit können wir bereits jetzt den Teilbaum von cake ausschließen und betrachten nur noch den Teilbaum von books. Die Distanz von zoo und books beträgt wieder 2, also ist books auch kein passender Kandidat. Erneut durchsuchen wir alle Kanten mit Gewichten zwischen 0 und 3 und finden boo. Hier haben wir den ersten Kandidaten gefunden, denn die Distanz zu zoo beträgt 1. Wir prüfen weiter alle Kindknoten von boo mit Kantengewichten zwischen 0 und 2. Die Distanzen zu boon und cook sind ebenfalls zu groß. Damit ist boo das einzige Wort, das sich nur in einem Buchstaben von zoo unterscheidet.

Implementierung in Kotlin

Levenshtein-Distanz

Eine rekursive Implementierung der Levenshtein-Distanz ist nicht die effizienteste, aber die einfachste Lösung:

class LevenshteinDistance {
 companion object {
  fun calculateDistance(word1: String, word2: String): Int {
   if (word1.isEmpty()) return word2.length
   if (word2.isEmpty()) return word1.length

   if (word1[0] == word2[0]) return calculateDistance(word1.tail(), word2.tail())
   
   return 1 + minOf(
    calculateDistance(word1.tail(), word2),
    calculateDistance(word1, word2.tail()),
    calculateDistance(word1.tail(), word2.tail())
   )
  }

  private fun String.tail(): String {
   return this.substring(1)
  }
 }
}

Einfügen

Wir benutzen einige Hilfsfunktionen, um beim Einfügen vorhandene Kanten zu prüfen:

class Edge(val from: Node, val to: Node, val distance: Int)

class Node(val word: String) {
 val edges = mutableListOf<Edge>()

  fun getChild(distance: Int): Node? {
   return edges.find { edge -> edge.distance == distance }?.to
  }

  fun hasChild(distance: Int): Boolean {
   return edges.any { edge -> edge.distance == distance }
  }

  fun addChild(node: Node, distance: Int) {
   edges.add(Edge(this, node, distance))
  }
}

Das Einfügen selber ist wieder rekursiv:

class Tree {
 var root: Node? = null

 fun insert(word: String) {
  val node = Node(word)
  if (root == null) root = node
  else insert(root!!, node)
 }

 private fun insert(currentRoot: Node, newNode: Node) {
  val distance = LevenshteinDistance.calculateDistance(currentRoot.word, newNode.word)

  if (currentRoot.hasChild(distance)) insert(currentRoot.getChild(distance)!!, newNode)
  else currentRoot.addChild(newNode, distance)
 }
}

Suche

Die Suche erwartet ein Wort und eine maximale Distanz als Eingabe. Es wird die Distanz zwischen Eingabe und aktueller Wurzel berechnet. Anschließend betrachten wir rekursiv alle in Frage kommenden Teilbäume und geben alle dabei gefundenen Wörter zurück:

class Tree {

 // [...]

 fun similarWords(word: String, maxDistance: Int): List<String> {
  if (root == null) return listOf()
  return similarWords(root!!, word, maxDistance)
 }

 private fun similarWords(currentRoot: Node, word: String, maxDistance: Int): MutableList<String> {
  val similarWords = mutableListOf<String>()

   val distance = LevenshteinDistance.calculateDistance(currentRoot.word, word)
   if (distance <= maxDistance) similarWords.add(currentRoot.word)

   val lowerSearchLimit = distance - maxDistance
   val upperSearchLimit = distance + maxDistance

   for (i in lowerSearchLimit..upperSearchLimit) {
    if (currentRoot.hasChild(i)) {
     val result = similarWords(currentRoot.getChild(i)!!, word, maxDistance)
     similarWords.addAll(result)
    }
   }

   return similarWords
  }
}

Benchmark

Ich habe mir die Liste der 1.000 häufigsten deutschen Wörter rausgesucht (jede Liste von Zeichenketten hätte natürlich genauso gut funktioniert, aber man will ja ein realistisches Szenario). Nachdem die Liste in der Implementierung von oben gespeichert wurde, habe ich darin nach einigen Wörtern mit einer Distanz von 0 gesucht. Anschließend habe ich die Wörter mit Tippfehlern versehen und mit größeren Distanzen gesucht. Besonders kurze Wörter mit großer Distanz funktionieren natürlich nicht so gut, weil es schlichtweg zu viele Möglichkeiten gibt. Auch als Mensch fällt es uns bei zu hoher Fehlerquote schwer, das gemeinte Wort zu erraten, was soll zum Beispiel mxx sein? Wörter mit nur einem Fehler sorgen dagegen dafür, dass ungefähr 80-90% aller Wörter gar nicht betrachtet werden müssen:

Wort Levenshtein-Distanz Betrachtete Knoten
Buch 0 5
mal 0 8
fest 0 7
Publikum 0 5
Bxch 1 102
mxl 1 206
fxst 1 171
ublikum 1 89
Bxxh 2 671
mxx 2 687
fxxt 2 709
ubxxkum 2 317

Fazit

Burkhard-Keller Bäume sind eine verhältnismäßig einfache Lösung für ein sehr alltägliches Problem. Abhängig von Wortlänge und Fehleranzahl lassen sich bereits gute Ergebnisse erzielen. Darüber hinaus gibt es natürlich viel Optimierungspotenzial. Zum Beispiel ist die Rekursion nicht praxistauglich. Außerdem können wir davon ausgehen, dass Nutzer die meisten Wörter richtig schreiben und jede Eingabe zunächst mit einer Distanz von 0 durch unsere Prüfung jagen. Denn das ist eine verhältnismäßig günstige Operation. Erst wenn dadurch ein Fehler festgestellt wird, erhöhen wir die Distanz, um Verbesserungsvorschläge anbieten zu können.

Den gesamten Code gibt es übrigens auf Github.