2.3.6.1: Entscheidungslisten

Um die Redundanz der Gesamtmenge der Regeln zu verringern, können die Regeln in eine Liste geschrieben werden, die der Reihe nach abgearbeitet wird. Solche so genannten Entscheidungslisten (decision lists) bestehen aus Zeilen, die ein Paar aus einer Bedingung und einer Kategorieangabe enthalten. Die letzte Zeile enthält eine leere Bedingung (die immer richtig ist) und eine Kategorieangabe.

Abbildung 58: Konstruktion einer Entscheidungsliste

Um ein Beispiel zu kategorisieren, wird zeilenweise geprüft, ob das Beispiel die Bedingung erfüllt. Ist das der Fall, wird die zugehörige Kategorie zugewiesen. Andernfalls wird die Bedingung der nächsten Zeile geprüft. Ist die letzte Zeile der Liste erreicht, ohne dass vorher eine Bedingung erfüllt wurde, wird die dort angegebene Kategorie zugewiesen, da die leere Bedingung ja immer erfüllt ist. Eine Art Entscheidungsliste wurde auch im Algorithmus zur Wortstammreduktion von Kuhlen in Abschnitt 1.3.2.1 eingeführt. Abbildung 58 zeigt eine Liste, die aus den Beispielen aus Abbildung 50 konstruiert wurde. Sie ist im Vergleich zu dem Entscheidungsbaum in Abbildung 53 recht handlich. Berücksichtigt man allerdings die Anzahl der benötigten Vergleiche, zeigt sich, dass sie erheblich mehr Rechenaufwand benötigt als der Baum. Ob sich der größere Programmier- und Verwaltungsaufwand für den Entscheidungsbaum lohnt, hängt von dem zu bearbeitenden Problem ab.

Entscheidungslisten sind insbesondere dann interessant, wenn es eine große Kategorie gibt, in die die Mehrzahl der zu erwartenden Beispiele fällt, und nur einzelne unsystematische Ausnahmen getrennt behandelt werden müssen. Sie sind nicht ganz einfach zu handhaben, da die Reihenfolge, in der die Regeln in die Liste eingetragen werden, natürlich entscheidend für die Kategorisierung ist. Spezialfälle bzw. Ausnahmen von allgemeineren Regeln müssen am Anfang der Liste stehen, damit in diesen Fällen abgebrochen wird, bevor die allgemeineren (und in der Regel häufigeren) Fälle erreicht werden. Das kann dazu führen, dass das System verhältnismäßig ineffektiv wird, da erst viele Spezialfälle abgeprüft werden müssen, ehe allgemeinere Fälle bearbeitet werden können. Zudem werden Bedingungen, die inhaltlich zusammengehören, in der Liste nicht unbedingt nahe beieinander stehen, weil die strikte Sequenzialität dies verhindert.