DAWG

Definition

DAWG (Directed Acyclic Word Graph) ist eine speichereffiziente Datenstruktur zur Speicherung und schnellen Suche von Wörtern in einem Lexikon. Er kombiniert die Vorteile eines Tries mit denen eines endlichen Automaten, indem gemeinsame Suffixe geteilt werden. DAWGs werden in Rechtschreibprüfungen, Wortspielen und der Textverarbeitung eingesetzt.