Trie
Ein Trie ([<templatestyles src="IPA/styles.css" />
| ] <phonos file="{{{Tondatei}}}"></phonos>
}}{{#invoke:TemplatePar|check
|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }}] oder ['traɪ]) 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 denen der Baum konstruiert worden ist.
Tries finden ihre Anwendung im Bereich des Information Retrieval. Dort werden sie zur Indexierung von Texten verwendet, um effizient bestimmte Anfragen an den Text zu beantworten.
Kompakte Tries oder auch Patricia-Tries (eine spezielle Variante von kompakten Tries) sind im Bezug auf Speicherplatzverbrauch optimierte Varianten des Tries. Hier werden alle Knoten, von denen nur eine Kante ausgeht, mit ihrem jeweiligen Nachfolger zusammengefasst.
Der Ausdruck Trie wurde von Edward Fredkin in Anlehnung an den Begriff Information Retrieval vorgeschlagen. Dieser Autor spricht ihn wie den englischen Begriff {{#invoke:Vorlage:lang|flat}} [<templatestyles src="IPA/styles.css" />
| ] <phonos file="{{{Tondatei}}}"></phonos>
}}{{#invoke:TemplatePar|check
|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }}] aus. Eine andere übliche Aussprache ist wie der englische Begriff {{#invoke:Vorlage:lang|flat}} [<templatestyles src="IPA/styles.css" />
| ] <phonos file="{{{Tondatei}}}"></phonos>
}}{{#invoke:TemplatePar|check
|all= 1= |opt= 2= Tondatei= |template=Vorlage:IPA |errNS= 0 |cat=Wikipedia:Vorlagenfehler/Vorlage:IPA |format=@@@ }}], wodurch der Trie verbal von der Datenstruktur Tree unterschieden wird.<ref name = DADS>{{#if:Vorlage:Cite book/URL|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:{{#if:
|
| {{#if: Black
| {{#if:
| [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}
}}Vorlage:Cite book/Name|{{#if:
|
| {{#if: Black
| {{#if:
| [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:
| {{#if:
| , [[|Vorlage:Cite book/Name]]
| Vorlage:Cite book/Name
}}
}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}
}}Vorlage:Cite book/Name: }}{{#if:Vorlage:Cite book/URL|{{#if:{{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1=Vorlage:Cite book/URL}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}}}]{{#if:| ()}}{{#if:{{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}| {{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}}}}}}}|{{#if:https://xlinux.nist.gov/dads/HTML/trie.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7CVorlage:Cite book/URL}}|{{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1={{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}}}}}|[{{#invoke:URLutil|getNormalized|1=https://xlinux.nist.gov/dads/HTML/trie.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1={{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}}}}}]}}{{#if:| ({{#if:{{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}Vorlage:Cite book/URLDictionary of Algorithms and Data StructuresNational Institute of Standards and Technology {{#if: | via {{{via}}} }}Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||1}}}}
| )
| {{#if:{{#ifeq:en|de||{{#if:en|1}}}}{{#if: | {{{at}}}{{#if: | , }}}}{{#if: | {{{id}}}{{#if: | , }}}}{{#if: | {{{doi}}}{{#if: | , }}}}{{#if: | PMID {{{pmid}}}{{#if: | , }}}}{{#if: | {{{arxiv}}}{{#if: | , }}}}{{#if: | Bibcode: {{{bibcode}}}{{#if: | , }}}}{{#if: | Volltext bei PMC: {{{pmc}}}{{#if: | , }}}}| ;
| )}}}}}}{{#if:{{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}| {{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}}}}}}}}}{{#if:https://xlinux.nist.gov/dads/HTML/trie.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://xlinux.nist.gov/dads/HTML/trie.html}}%7C%7C}}}}{{#if:{{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}|{{#if:{{#invoke:WLink|isValidLinktext|1={{#if: trie | {{#invoke: WLink|getEscapedTitle|1=trie}} | ? }}|lines=0}}||}}}}{{#if: Dictionary of Algorithms and Data Structures| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Dictionary of Algorithms and Data Structures}}}}{{#if: National Institute of Standards and Technology {{#if: | via {{{via}}} }}| National Institute of Standards and Technology {{#if: | via {{{via}}} }}{{#if: Vorlage:Cite book/DateVorlage:Cite book/URL|,|{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||,}}}}}}}}{{#if: Vorlage:Cite book/Date| {{#if:{{#invoke:DateTime|format|Vorlage:Cite book/Date|noerror=1}}
|{{#invoke:DateTime|format|Vorlage:Cite book/Date|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=Vorlage:Cite book/Date|class=Zitationswartung}} }}{{#if: Vorlage:Cite book/URL|,|{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||,}}}}}}}}{{#if: | S. {{#if: Vorlage:Cite book/URL|,|{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||,}}}}}}}}{{#if: Vorlage:Cite book/URL{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}| {{#if:Vorlage:Cite book/DateNational Institute of Standards and Technology {{#if: | via {{{via}}} }}|{{#if:Vorlage:Cite book/URL|archiviert|ehemals}}|{{#if:Vorlage:Cite book/URL|Archiviert|Ehemals}}}} {{#if:Vorlage:Cite book/URL|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}| (nicht mehr online verfügbar)}}{{#if: Vorlage:Cite book/URL| am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|Vorlage:Cite book/URL{{#if:130026||(?)}}}}}}{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}}|;}}}}{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}}| {{#if:Vorlage:Cite book/DateNational Institute of Standards and Technology {{#if: | via {{{via}}} }}Vorlage:Cite book/URL{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf={{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}}|class=Zitationswartung}} }} {{#invoke:DateTime|format|{{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}}|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}{{#if: | {{{at}}}{{#if: | , }}}}{{#if: | {{{id}}}{{#if: | , }}}}{{#if: | {{{doi}}}{{#if: | , }}}}{{#if: | PMID {{{pmid}}}{{#if: | , }}}}{{#if: | {{{arxiv}}}{{#if: | , }}}}{{#if: | Bibcode: {{{bibcode}}}{{#if: | , }}}}{{#if: | Volltext bei PMC: {{{pmc}}}{{#if: | , }}}}|{{#if:{{#if: | ( }}{{#if: | Originaltitel: {{{script-title}}} }}{{#if: | {{#if: | , }}deutsch: {{{trans-title}}} }}{{#if: | ) }}Vorlage:Cite book/URLDictionary of Algorithms and Data StructuresNational Institute of Standards and Technology {{#if: | via {{{via}}} }}Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:en|en|de}}|de||
{{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: {{#if: | {{{at}}}{{#if: | , }}}}{{#if: | {{{id}}}{{#if: | , }}}}{{#if: | {{{doi}}}{{#if: | , }}}}{{#if: | PMID {{{pmid}}}{{#if: | , }}}}{{#if: | {{{arxiv}}}{{#if: | , }}}}{{#if: | Bibcode: {{{bibcode}}}{{#if: | , }}}}{{#if: | Volltext bei PMC: {{{pmc}}}{{#if: | , }}}}|{{#ifeq:{{#if:en|en|de}}|de||, }}{{#if: | {{{at}}}{{#if: | , }}}}{{#if: | {{{id}}}{{#if: | , }}}}{{#if: | {{{doi}}}{{#if: | , }}}}{{#if: | PMID {{{pmid}}}{{#if: | , }}}}{{#if: | {{{arxiv}}}{{#if: | , }}}}{{#if: | Bibcode: {{{bibcode}}}{{#if: | , }}}}{{#if: | Volltext bei PMC: {{{pmc}}}{{#if: | , }}}}}})}}{{#if: Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2024-01-10
| {{#iferror: {{#invoke:DateTime|format|2024-01-10|ISO}}
| 0001-01-01
}}
| 0001-01-01
}} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2024-01-10
| {{#if: {{#invoke:DateTime|format|2024-01-10 |ISO|noerror=1}} || 1 }}
| 1
}}}}||1}} }}en{{#if: | {{{at}}}{{#if: | , }}}}{{#if: | {{{id}}}{{#if: | , }}}}{{#if: | {{{doi}}}{{#if: | , }}}}{{#if: | PMID {{{pmid}}}{{#if: | , }}}}{{#if: | {{{arxiv}}}{{#if: | , }}}}{{#if: | Bibcode: {{{bibcode}}}{{#if: | , }}}}{{#if: | Volltext bei PMC: {{{pmc}}}{{#if: | , }}}}|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if:
| {{#if:
| {{#if:
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}|{{#if:Vorlage:Cite book/URL||{{#ifeq: Vorlage:Cite book/URL | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if:{{#invoke:URLutil|isWebURL|https://xlinux.nist.gov/dads/HTML/trie.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://xlinux.nist.gov/dads/HTML/trie.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if:{{#invoke:URLutil|isWebURL|https://xlinux.nist.gov/dads/HTML/trie.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://xlinux.nist.gov/dads/HTML/trie.html }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if:{{#invoke:URLutil|isWebURL|https://xlinux.nist.gov/dads/HTML/trie.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://xlinux.nist.gov/dads/HTML/trie.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://xlinux.nist.gov/dads/HTML/trie.html | {{#if:{{#invoke:URLutil|isWebURL|https://xlinux.nist.gov/dads/HTML/trie.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://xlinux.nist.gov/dads/HTML/trie.html }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp=|text={{#if:Vorlage:Cite book/URL|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}{{#invoke:TemplatePar|check
|all = url= title= |opt = script-title= trans-title= archive-url= archiveurl= archive-date= archivedate= authors= vauthors= author= author1= authorlink= authorlink1= author-link= author-link1= author2= author-link2= author3= author-link3= author4= author-link4= author5= author-link5= author6= author7= author8= author9= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= others= language= lang= format= website= work= publisher= via= pages= page= at= date= year= id= bibcode= doi= pmid= pmc= arxiv= archivedate= archive-date= archivebot= accessdate= access-date= quote= comment= url-status= ref= url-access= orig-year= editor= editor-link= editor-last= editor-first= editor1-link= editor1-last= editor1-first= editor2= editor2-last= editor2-first= editor2-link= department= series= agency= location= place= publication-place= publication-date= type= asin= doi-broken-date= isbn= issn= jfm= jstor= lccn= mr= oclc= ol= osti= rfc= ssrn= zbl= postscript= df= mode= display-authors= display-editors= book-title= contribution-url= offline= coauthors= month= authorlink2= authorlink3= authorlink4= authorlink5= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite web |errNS = 0 |template = Vorlage:Cite web |format = |preview = 1 }}Vorlage:Cite book/URL{{#if: Vorlage:Cite book/Webarchiv | Vorlage:Cite book/Meldung }}{{#if: | Vorlage:Cite book/Meldung }}Vorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:Black|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:Dictionary of Algorithms and Data Structures|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:2024-01-10|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:en|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1 | Vorlage:Cite book/Meldung }}</ref><ref name = KnuthVol3>{{#invoke:Vorlage:Literatur|f}}{{#if:
| {{#if: Vorlage:Cite book/ParamBool | Vorlage:Toter Link/archivebot | Vorlage:Webarchiv/archiv-bot }}
}}{{#invoke:TemplatePar|check
|all = title= |opt = vauthors= author= author-link= authorlink= author1= author-link1= author1-link= first= last= first1= last1= first2= last2= author2= first3= last3= author3= first4= last4= author4= first5= last5= author5= first6= last6= author6= first7= last7= author7= first8= last8= author8= others= coauthors= script-title= trans-title= orig-date= orig-year= chapter= chapter-url= editor= editor-first= editor-last= editor-first1= editor-last1= editor-first2= editor-last2= editor-first3= editor-last3= editor-link= editor-link1= language= format= others= series= issue= number= edition= volume= publisher= location= date= year= isbn= page= at= pages= arxiv= doi= jstor= bibcode= pmc= pmid= lccn= oclc= id= url= url-status= access-date= accessdate= archive-url= archiveurl= archive-date= archivedate= quote= url-access= ref= coauthors= origyear= archivebot= offline= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite book |errNS = 0 |template = Vorlage:Cite book |format = |preview = 1
}}Vorlage:Cite book/URLVorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:Knuth|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:492|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref> 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:<ref name="JF">Johannes Fischer: Vorlesungsskriptum "Text-Indexierung und Information Retrieval". Wintersemester 2014/2015. Abgerufen am 28. November 2014.</ref>
- <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> es gibt einen Knoten <math>v</math>, sodass <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> es gibt eine Zeichenkette <math>S_i \in S</math>, sodass der Pfad von der Wurzel zum Blatt <math>b</math> genau <math>S_i</math> buchstabiert.
Ein Beispiel für einen Trie über <math>S</math> = {„Java“, „Rad“, „Rand“, „Rau“, „Raum“, „Rose“} ist dem Bild zu entnehmen, wobei die doppelt umrandeten Knoten die Zeichenketten aus <math>S</math> darstellen. Man beachte insbesondere, dass das Wort „Rau“ Präfix des Wortes „Raum“ ist, d. h. eine Zeichenkette aus <math>S</math> kann Präfix einer anderen sein.
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:<ref name="JF" />
- Existenzanfragen der Art „Enthält <math>S</math> das Muster <math>M</math>?“
- Präfixanfragen der Art „Welche Zeichenketten in <math>S</math> beginnen mit dem Muster <math>M</math>?“
- Nachfolger- und Vorgängeranfragen wie „Welche Zeichenketten in <math>S</math> sind lexikographische Nachfolger bzw. Vorgänger des Musters <math>M</math>?“
Eine mögliche Verwendung von Tries könnte beispielsweise 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 angezeigt werden, deren Namen mit den bisher eingegebenen Buchstaben beginnen (Präfixanfragen). Des Weiteren können Kontakte gefunden werden, die im Telefonbuch hinter bzw. vor der angefragten Person stehen (Nachfolger- und Vorgängeranfragen).
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 davon ab, wie die Speicherung der ausgehenden Kanten implementiert ist. Im Folgenden werden einige der möglichen Implementierungsarten vorgestellt:<ref name="JF" />
- 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.
- 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>.
- 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>.
- 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. | M| \cdot |\Sigma|)</math> | <math>O(n)</math> |
| 2. | M| \cdot \log |\Sigma|)</math> | <math>O(n)</math> |
| 3. | M|)</math> | \Sigma| \cdot n)</math> |
| 4. | M|)</math> | <math>O(n)</math> |
Siehe auch
Literatur
- Rene de la Briandais: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959, S. 295–298, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}
- Edward Fredkin: Trie Memory. Communications of the ACM, 3(9): 490–499, Sept. 1960, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}
- Donald E. Knuth: The Art of Computer Programming. Vol. 3, 2nd ed. Boston 1998. S. 492–512.
Weblinks
|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if: 00
| {{#switch: {{#invoke:TemplUtl|faculty|0}}/{{#invoke:TemplUtl|faculty|0}}
|1/= und Videos
|1/1=, Videos und Audiodateien
|/1= und Audiodateien}}
| , Videos und Audiodateien
}}
|#default= – }}{{#if:
| {{#ifeq: {{#invoke:Str|left||9}}
| category:
| FEHLER: Ohne Category: angeben!}}}}Vorlage:Wikidata-Registrierung
- NIST's Dictionary of Algorithms and Data Structures: Trie (englisch)
- Lloyd Allison: Tries (englisch)
- An Implementation of Double-Array Trie (englisch)
Einzelnachweise
<references />
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Wikipedia:Vorlagenfehler/Schwesterprojekt
- Datenstruktur
- Suchbaum