Patricia-Trie - LinkFang.de





Patricia-Trie


In der Informatik ist ein Patricia-Trie (abgeleitet aus dem engl. reTrieval) eine Datenstruktur, genauer eine spezielle Art eines Tries zur gleichzeitigen Speicherung von mehreren Zeichenketten. Seinen Namen verdankt er dem Akronym PATRICIA, das für Practical Algorithm to Retrieve Information Coded in Alphanumeric steht. Er wurde 1968 von Donald R. Morrison veröffentlicht.

Der Patricia-Trie zeichnet sich im Gegensatz zum normalen Trie dadurch aus, dass die Daten komprimiert abgespeichert werden. Dazu werden Zeichen, bei denen keine Verzweigung im Baum entsteht, einfach übersprungen und die Anzahl der ausgelassenen Knoten vor dem nächsten auftretenden Zeichen gespeichert. Somit wird gewährleistet, dass ein Suchbegriff eindeutig zugeordnet werden kann.

Die Größe von Patricia-Tries hängt somit nicht von der Länge der gespeicherten Schlüsselwerte ab und jeder neue Eintrag kann durch Erstellen von nur einem neuen Knoten und einer neuen Kante eingefügt werden. Somit wachsen sie langsam, auch wenn eine große Anzahl neuer Elemente eingefügt wird.

Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Strings als Schlüsseln zu konstruieren. Hiermit wird Speicherplatz für die Schlüssel gespart.

Siehe auch

Weblinks


Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Patricia-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.