Trie - LinkFang.de





Trie


Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Trie (Begriffsklärung) aufgeführt.

Ein Trie 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 der der Baum konstruiert worden ist.

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

Eine im Bezug auf Speicherplatzverbrauch optimierte Variante des Tries sind kompakte Tries oder auch Patricia Tries (eine spezielle Variante von kompakten Tries), bei denen jeder Knoten mit nur einer ausgehenden Kante mit seinem Vaterknoten zusammengefasst wird.

Der Ausdruck Trie wurde von Edward Fredkin vorgeschlagen in Anlehnung an den Begriff Information Retrieval. Dieser Autor spricht es 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.

Definition

Sei [math]S = \{ S_1, \dots ,S_k \} [/math] eine Menge von [math]k[/math] Zeichenketten über dem Alphabet [math]\Sigma[/math] mit der Größe [math]\sigma[/math] = [math]|\Sigma|[/math]. Ein Trie über [math]S[/math] ist ein Baum der Form [math]T=(V,E)[/math], wobei [math]V[/math] die Menge der Knoten und [math]E[/math] die Menge der Kanten ist, der die folgenden Eigenschaften besitzt:[3]

  • [math]\forall e \in E \colon e[/math] besitzt ein Label aus dem Alphabet [math]\Sigma[/math],
  • [math]\forall v \in V \colon[/math] alle ausgehenden Kanten des Knotens [math]v[/math] besitzen ein unterschiedliches Label [math] a \in \Sigma[/math],
  • [math]\forall S_i \in S \colon[/math] gibt es ein Knoten [math]v[/math], so dass [math]S_i[/math] ein Präfix der Konkatenation der Labels des Pfades beginnend bei der Wurzel bis zum Knoten [math]v[/math] ist (diese Knoten werden im Trie besonders ausgezeichnet, z.B. durch Setzen eines Bits),
  • [math]\forall[/math] Blätter [math]b \in V \colon[/math] gibt es einen String [math]S_i \in S[/math], so dass der Pfad von der Wurzel zum Blatt [math]b[/math] genau [math]S_i[/math] buchstabiert.

Ein Beispiel für einen Trie über der folgenden Menge an Strings [math]S[/math] = {"Java", "Rad", "Rand", "Rau", "Raum", "Rose"} ist dem Bild zu entnehmen, wobei die doppelt umrandeten Knoten die Strings aus [math]S[/math] darstellen. Man beachte insbesondere, dass das Wort "Rau" Präfix eines anderen Wortes "Raum" ist.

Anwendungen

Mit Hilfe von Tries können unterschiedliche Anfragen an eine gegebene Menge verschiedener Zeichenketten [math]S[/math] gestellt werden. Beispielhafte Anfragen könnten sein:[3]

  • Existenzanfragen der Art „Ist ein Muster [math]M[/math] einer der Strings aus [math]S[/math]?
  • Präfixanfragen der Art „Welche Strings aus [math]S[/math] haben [math]M[/math] als Präfix?
  • Nachfolger- und Vorgängeranfragen wie „Welche Strings in [math]S[/math] sind lexikographische Nachfolger bzw. Vorgänger des Musters [math]M[/math]?“

Damit finden Tries Anwendung in unterschiedlichen Bereichen. Eine mögliche Verwendung von Tries könnte die Realisierung von Suchanfragen innerhalb einer Kontakte- bzw. Telefonbuch-App für Smartphones sein. Mit Hilfe des Tries kann eine Personensuche nach Namen erfolgen (Existenzanfragen). Ebenso können bei Eingabe eines Namens bereits Kontakte, deren Namen mit den bisher eingegebenen Buchstaben beginnen (Präfixanfragen), angezeigt werden. Des Weiteren können Kontakte, die im Telefonbuch hinter bzw. vor der angefragten Person stehen (Nachfolger- und Vorgängeranfragen), gefunden werden.

Implementierungsarten

Zur Beantwortung von Anfragen an den Trie wird nach dem Top-Down-Prinzip, beginnend bei der Wurzel ein Pfad zu einem Knoten gesucht, der dem angefragten Muster [math]M[/math] entspricht. Die Laufzeiten, in der diese Anfragen durchgeführt werden können, sowie der Platzbedarf des Tries hängen somit stark von der Art der Implementierung der Speicherung der ausgehenden Kanten ab. Im Folgenden werden einige der möglichen Implementierungsarten vorgestellt:[3]

  1. Eine einfache Variante ist die Speicherung aller ausgehenden Kanten pro Knoten in einer Liste. Dies resultiert in einer Laufzeit von [math]O(| M| \cdot |\Sigma|)[/math]. Der Platzbedarf dieser Lösung beträgt [math]O(n)[/math], wobei [math] n = \sum_{i=1}^k |s_i|[/math] die Gesamtlänge aller Strings in [math]S[/math] bezeichnet.
  2. In der nächsten Variante werden die ausgehenden Kanten, anstatt in einer Liste, in einem sortierten Array für jeden Knoten vorgehalten. Durch Verwendung der binären Suche zum Auffinden der Nachfolgerkante wird hierbei eine Laufzeit von [math]O(|M| \cdot \log |\Sigma|)[/math] erreicht. Der Platzbedarf entspricht dem von Variante 1 und beträgt somit [math]O(n)[/math].
  3. Pro Knoten werden die ausgehenden Kanten in einem Array der Größe [math]|\Sigma|[/math] abgelegt. Dadurch wird eine Laufzeit von [math]O(|M|)[/math] erreicht. Hierbei wächst jedoch der Platzbedarf des Tries auf [math]O(|\Sigma| \cdot n)[/math].
  4. Zur Speicherung der ausgehenden Kanten wird eine Hashtabelle verwendet. Diese kann pro Knoten oder global für den gesamten Trie angelegt werden. Mit beiden Varianten wird eine erwartete Laufzeit von [math]O(|M|)[/math] erreicht. Der Nachteil dieser Variante ist allerdings, dass hiermit keine Vorgänger- bzw. Nachfolgeranfragen beantwortet werden können (da Hashtabellen per se unsortiert sind). Diese Variante erreicht einen Platzbedarf von [math]O(n)[/math].

Vergleich der Laufzeit und des Platzbedarfs

Variante Laufzeit Platzbedarf
1. [math]O(| M| \cdot |\Sigma|)[/math] [math]O(n)[/math]
2. [math]O(|M| \cdot \log |\Sigma|)[/math] [math]O(n)[/math]
3. [math]O(|M|)[/math] [math]O(|\Sigma| * n)[/math]
4. erwartet [math]O(|M|)[/math] [math]O(n)[/math]

Siehe auch

Literatur

Weblinks

 Commons: Trie  – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Paul E. Black: trie . In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. 16. November 2009. Archiviert vom Original am 19. Mai 2010. Abgerufen am 7. Dezember 2014.
  2. Donald Knuth: 6.3: Digital Searching. In: The Art of Computer Programming Volume 3: Sorting and Searching, 2nd, Addison-Wesley, 1997, ISBN 0-201-89685-0.
  3. 3,0 3,1 3,2 Johannes Fischer: Vorlesungsskriptum "Text-Indexierung und Information Retrieval" . Wintersemester 2014/2015. Abgerufen am 28. November 2014.

Kategorien: Datenstruktur | Suchbaum

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Trie (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.