imported>SchlurcherBot: Bot: http → https

2026-02-18T18:02:06Z

Bot: http → https

Neue Seite

Ein '''PAT Tree''' ist eine [[Datenstruktur]] zum schnellen Auffinden von Wörtern in Texten.
Grundlegende Idee dabei ist, den gesamten Text als eine Zeichenkette zu sehen, diese in ''siStrings'' zu zerlegen und deren binäre Darstellung in einen [[Patricia-Trie]] einzufügen.

Ein ''siString'' ist dabei eine Zeichenkette, die an einer beliebigen Stelle im Text beginnt und maximal bis ans Textende reicht.

== Geschichte ==
PAT Trees wurden von Gaston H. Gonnet, Ricardo A. Baeza-Yates und Tim Snider im Jahre 1992 in ihrer Arbeit ''New indices for text: PAT Trees and PAT arrays'' beschrieben. Sie benutzen [[Patricia-Trie]]s, die von Donald R. Morrison beschrieben wurden.
Gernot Gwehenberger beschrieb unabhängig (veröffentlicht im gleichen Monat Oct. 1968) eine zum PATRICIA-Trie identische Suchmethode und Datenstruktur. 1984 verwendete Gernot Gwehenberger diese Datenstruktur zur Beantwortung der Frage: Wieweit unterscheidet sich der Informationsgehalt genetischer Information vom Informationsgehalt anderer Informationen etwa der von zufällig generierter Information (Informationsgehalt I=1). Gemeint ist hier der Informationsgehalt nach Shannon. Die vergleichende Untersuchung erfolgte, indem jeweils drei gleich lange Textfolgen in siStrings zerlegt und zu jeweils einem PATRICIA-Tree zusammengefügt wurden. Der jeweilige Informationsgehalt I ergab sich dann aus der mittleren Anzahl Suchschritte A nach der Formel A=log2(N)/I + K(I). Diese Formel wurde abgeleitet für den Fall einer Textfolge deren Redundanz R (R=1-I) davon herrührt, dass die Bits 1 und 0, aus denen die Textfolge zusammengesetzt ist, eine unterschiedliche Wahrscheinlichkeit haben. Dabei ist N die Anzahl der siStrings und K eine von I abhängige Konstante (für die eine Formel angegeben wird). Die 3 Textfolgen von je 4361 Zeichen waren genetische Information des Bakteriums Escherichia coli (Plasmid pBR322), sowie die ersten 4361 alphanumerischen Zeichen der Publikation sowie zur Kontrolle zufällig generierte Information (I=1). Es ergab sich bei der praktischen Auswertung für die genetische Information I=0.9923, für den Text I=0.834 und für die Kontrolle I=1.0014.

== Suchmethoden ==
PAT-Trees ermöglichen es, verschiedene Anfragearten effizient zu beantworten.
* Präfix Suche
* Näherungssuche
* Bereichssuche
* Häufigkeitssuche
* Längste Wiederholungssuche
* Suche nach regulären Ausdrücken
* Ermitteln des Informationsgehalts (nach Shannon) einer Textfolge

== Literatur ==
* ''Suchbäume: ein vielseitig einsetzbares Hilfsmittel.'' In: ''OUTPUT.'' Nr. 8/1984, Fachpresse Goldach CH.

== Weblinks ==
* [http://portal.acm.org/citation.cfm?id=129692&dl=GUIDE&coll=Portal&CFID=17251716&CFTOKEN=75344361 Der Original-Artikel von Gonnet bei ACM]
* [http://portal.acm.org/citation.cfm?id=321481 Practical Algorithm to Retrieve Information Coded in Alphanumeric], Originalpapier im ACM Portal [en]
* [https://cr.yp.to/bib/1968/gwehenberger.html Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen.] Elektronische Rechenanlagen 10 (1968), von Gernot Gwehenberger

[[Kategorie:Datenstruktur]]

PAT Tree - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https