Editing Trie (section)

== Applications ==
Trie data structures are commonly used in [[predictive text]] or [[autocomplete]] dictionaries, and [[Approximate string matching|approximate matching algorithms]].<ref name="aho75">{{Cite journal|last1=Aho|first1=Alfred V.|last2=Corasick|first2=Margaret J.|date=Jun 1975|title=Efficient String Matching: An Aid to Bibliographic Search|journal=[[Communications of the ACM]]|volume=18|issue=6|pages=333–340|doi=10.1145/360825.360855|s2cid=207735784|doi-access=free}}</ref> Tries enable faster searches, occupy less space, especially when the set contains large number of short strings, thus used in [[spell checking]], hyphenation applications and [[longest prefix match]] algorithms.<ref name="Liang1983" /><ref name="reema18">{{cite book|title= Data Structures Using C|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription|chapter=Hashing and Collision}}</ref>{{rp|p=358}} However, if storing dictionary words is all that is required (i.e. there is no need to store metadata associated with each word), a minimal deterministic acyclic finite state automaton (DAFSA) or radix tree would use less storage space than a trie. This is because DAFSAs and radix trees can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored. String dictionaries are also utilized in [[natural language processing]], such as finding [[lexicon]] of a [[text corpus]].<ref name="prieto16">{{cite journal|journal=[[Information Systems (journal)|Information Systems]]|first1=Miguel A.|last1=Martinez-Prieto|first2=Nieves|last2=Brisaboa|first3=Rodrigo|last3=Canovas|first4=Francisco|last4=Claude|first5=Gonzalo|last5=Navarro|publisher=[[Elsevier]]|volume=56|doi=10.1016/j.is.2015.08.008|url=https://www.sciencedirect.com/science/article/abs/pii/S0306437915001672|date=March 2016|title=Practical compressed string dictionaries|pages=73–108|issn= 0306-4379 }}</ref>{{rp|p=73}}

=== Sorting ===
[[Lexicographic order|Lexicographic sorting]] of a set of string keys can be implemented by building a trie for the given keys and traversing the tree in [[Tree traversal#Pre-order implementation|pre-order]] fashion;<ref>{{cite web |url=https://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf |title=Lecture 2 |first=Juha |last=Kärkkäinen |quote="The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels." |publisher=[[University of Helsinki]]}}</ref> this is also a form of [[radix sort]].<ref>{{Cite web|url=https://www.ifi.uzh.ch/dam/jcr:27d15f69-2a44-40f9-8b41-6d11b5926c67/ReportKallisMScBasis.pdf|title=The Adaptive Radix Tree (Report #14-708-887)|last=Kallis|first=Rafael|date=2018|website=University of Zurich: Department of Informatics, Research Publications}}</ref> Tries are also fundamental data structures for [[burstsort]], which is notable for being the fastest string sorting algorithm as of 2007,<ref name="cachestringsort">{{cite journal | url=https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf | doi=10.1145/1187436.1187439 | author=Ranjan Sinha and Justin Zobel and David Ring | title=Cache-Efficient String Sorting Using Copying | journal=ACM Journal of Experimental Algorithmics | volume=11 | pages=1&ndash;32 | date=Feb 2006 | s2cid=3184411 }}</ref> accomplished by its efficient use of CPU [[cache (computing)|cache]].<ref name="stringradix">{{cite book | doi=10.1007/978-3-540-89097-3_3 | author=J. Kärkkäinen and T. Rantala | chapter=Engineering Radix Sort for Strings | editor=A. Amir and A. Turpin and A. Moffat | title=String Processing and Information Retrieval, Proc. SPIRE | publisher=Springer | series=Lecture Notes in Computer Science | volume=5280 | pages=3–14 | year=2008 | isbn=978-3-540-89096-6 }}</ref>

=== Full-text search ===
A special kind of trie, called a [[suffix tree]], can be used to index all [[suffix]]es in a text to carry out fast full-text searches.<ref>{{cite journal|journal=[[SIAM Journal on Computing]]|doi=10.1137/S0097539792231982|volume=24|issue=3|url=https://epubs.siam.org/doi/abs/10.1137/S0097539792231982|title=A Generalization of the Suffix Tree to Square Matrices, with Applications|pages=520–562|issn= 0097-5397 |publisher=[[Society for Industrial and Applied Mathematics]]|date=28 May 1992|last1=Giancarlo|first1=Raffaele}}</ref>

=== Web search engines ===
A specialized kind of trie called a compressed trie, is used in [[web search engine]]s for storing the [[Web indexing|indexes]] - a collection of all searchable words.<ref name="Xu12">{{cite journal|title=An enhanced dynamic hash TRIE algorithm for lexicon search|first1=Lai|last1=Yang|first2=Lida|last2=Xu|first3=Zhongzhi|last3=Shi|doi=10.1080/17517575.2012.665483|date=23 March 2012|pages=419–432|volume=6|issue=4|journal=Enterprise Information Systems|bibcode=2012EntIS...6..419Y |s2cid=37884057 }}</ref> Each terminal node is associated with a list of [[URL]]s—called occurrence list—to pages that match the keyword. The trie is stored in the main memory, whereas the occurrence is kept in an external storage, frequently in large [[Computer cluster|clusters]], or the in-memory index points to documents stored in an external location.<ref>{{cite journal|first1=Frederik|last1=Transier|first2=Peter|last2=Sanders|volume=29|issue=1|date=December 2010|pages=1–37|doi=10.1145/1877766.1877768|title=Engineering basic algorithms of an in-memory text search engine|url=https://dl.acm.org/doi/10.1145/1877766.1877768|publisher=[[Association for Computing Machinery]]|journal=ACM Transactions on Information Systems|s2cid=932749 }}</ref>

=== Bioinformatics ===
Tries are used in [[Bioinformatics]], notably in [[sequence alignment]] software applications such as [[BLAST (biotechnology)#Algorithm|BLAST]], which indexes all the different substring of length ''k'' (called [[k-mer]]s) of a text by storing the positions of their occurrences in a compressed trie sequence databases.{{r|prieto16|p=75}}

=== Internet routing ===
{{see also|Luleå algorithm}}
Compressed variants of tries, such as databases for managing [[Forwarding information base|Forwarding Information Base]] (FIB), are used in storing [[Subnetwork|IP address prefixes]] within [[Routing|routers]] and [[Network bridge|bridges]] for prefix-based lookup to resolve [[Wildcard mask|mask-based]] operations in [[IP routing]].{{r|prieto16|p=75}}