https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Patricia-TriePatricia-Trie - Versionsgeschichte2026-06-27T02:25:24ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Patricia-Trie&diff=156040&oldid=previmported>Cmglee: Patricia_trie_var.svg → radix_tree.svg2025-07-29T22:47:43Z<p>Patricia_trie_var.svg → radix_tree.svg</p>
<p><b>Neue Seite</b></p><div>[[Image:radix_tree.svg|right|250px]]<br />
<br />
In der [[Informatik]] ist ein '''Patricia-Trie''' (abgeleitet aus dem engl. re'''Trie'''val) eine [[Datenstruktur]], genauer eine spezielle Art eines [[Trie]]s zur gleichzeitigen Speicherung von mehreren [[Zeichenkette]]n. 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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
Patricia-Tries können dazu verwendet werden, [[Assoziatives Array|assoziative Arrays]] mit Strings als Schlüsseln zu konstruieren. Hiermit wird Speicherplatz für die Schlüssel gespart.<br />
<br />
== Siehe auch ==<br />
* [[Suffixbaum]]<br />
<br />
== Weblinks ==<br />
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ Monash University: Algorithms and Data Structures Research & Reference Material: PATRICIA], von Lloyd Allison [en]<br />
* [http://portal.acm.org/citation.cfm?id=321481 Practical Algorithm to Retrieve Information Coded in Alphanumeric], Originalpapier im ACM Portal [en]<br />
* [http://www.nist.gov/dads/HTML/patriciatree.html NIST's Dictionary of Algorithms and Data Structures: Patricia Tree] [en]<br />
* [http://cr.yp.to/bib/1968/gwehenberger.html Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen.] Elektronische Rechenanlagen 10 (1968), von Gernot Gwehenberger beschreibt eine unabhängig etwa zur selben Zeit entwickelte identische Suchmethode und Datenstruktur [de]<br />
<br />
[[Kategorie:Datenstruktur]]</div>imported>Cmglee