Trie

Ein Trie ([ˈtriː] oder ['traɪ]) oder Präfixbaum ist eine Datenstruktur, die in der Informatik zum Suchen nach Zeichenketten verwendet wird. Es handelt sich dabei um einen speziellen Suchbaum zur gleichzeitigen Speicherung mehrerer Zeichenketten. Dabei beinhalten Tries eine Art der Datenkompression, da gemeinsame Präfixe der Zeichenketten nur einmal gespeichert werden.

Ein Trie wird über eine Menge von beliebigen Zeichenketten aufgebaut. Jede ausgehende Kante eines Knotens innerhalb eines Tries ist mit einem einzelnen Zeichen versehen, sodass ein Pfad beginnend bei der Wurzel bis zu einem Blatt im Trie eine der Zeichenketten darstellt, aus denen der Baum konstruiert worden ist.

Tries finden ihre Anwendung im Bereich des Information Retrieval. Dort werden sie zur Indexierung von Texten verwendet, um effizient bestimmte Anfragen an den Text zu beantworten.

Kompakte Tries oder auch Patricia-Tries (eine spezielle Variante von kompakten Tries) sind im Bezug auf Speicherplatzverbrauch optimierte Varianten des Tries. Hier werden alle Knoten, von denen nur eine Kante ausgeht, mit ihrem jeweiligen Nachfolger zusammengefasst.

Der Ausdruck Trie wurde von Edward Fredkin in Anlehnung an den Begriff Information Retrieval vorgeschlagen. Dieser Autor spricht ihn wie den englischen Begriff tree ['triː] aus. Eine andere übliche Aussprache ist wie der englische Begriff try ['traɪ], wodurch der Trie verbal von der Datenstruktur Tree unterschieden wird.^[1][2] Diese zweite Variante hat sich mittlerweile durchgesetzt.

1. ↑ Paul E. Black: trie. In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology, 16. November 2009, abgerufen am 10. Januar 2024 (englisch). 
2. ↑ Donald Knuth: The Art of Computer Programming Volume 3: Sorting and Searching. 2nd Auflage. Addison-Wesley, 1997, ISBN 0-201-89685-0, 6.3: Digital Searching, S. 492 (englisch).