PAT Tree

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-Tries, 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

• Der Original-Artikel von Gonnet bei ACM
• Practical Algorithm to Retrieve Information Coded in Alphanumeric, Originalpapier im ACM Portal [en]
• Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen. Elektronische Rechenanlagen 10 (1968), von Gernot Gwehenberger