The trie, pronounced “try”, is a tree that specializes in storing data that can be represented as a collection, such as English words:
A trie containing the words CAT, CUT, CUTE, TO and A
Each string character maps to a node where the last node is terminating. These are marked in the diagram above with a dot. The benefits of a trie are best illustrated by looking at it in the context of prefix matching.
In this chapter, you’ll first compare the performance of a trie to a list. Then you’ll implement the trie from scratch!
List vs. Trie
You’re given a collection of strings. How would you build a component that handles prefix matching? Here’s one way:
class EnglishDictionary {
final List<String> words = [];
List<String> lookup(String prefix) {
return words.where((word) {
return word.startsWith(prefix);
}).toList();
}
}
lookup will go through the collection of strings and return those that match the prefix.
This algorithm is reasonable if the number of elements in the words list is small. But if you’re dealing with more than a few thousand words, the time it takes to go through the words list will be unacceptable. The time complexity of lookup is O(k × n), where k is the longest string in the collection, and n is the number of words you need to check.
Imagine the number of words Google needs to parse
The trie data structure has excellent performance characteristics for this problem. Since it’s a tree with nodes that support multiple children, each node can represent a single character.
You form a word by tracing the collection of characters from the root to a node with a special indicator — a terminator — represented by a black dot. An interesting characteristic of the trie is that multiple words can share the same characters.
To illustrate the performance benefits of the trie, consider the following example in which you need to find the words with the prefix CU. First, you travel to the node containing C. That quickly excludes other branches of the trie from the search operation:
Next, you need to find the words with the next letter, U. You traverse to the U node:
Since that’s the end of your prefix, the trie would return all collections formed by the chain of nodes from the U node. In this case, the words CUT and CUTE would be returned.
Imagine if this trie contained hundreds of thousands of words. The number of comparisons you can avoid by employing a trie is substantial.
Implementation
As always, open up the starter project for this chapter.
TrieNode
You’ll begin by creating the node for the trie. Create a lib folder in the root of your project and add a file to it named trie_node.dart. Add the following to the file:
Ul zuhulc veixnj slauh, jexer cuse e pinl axy yuzcw kkiss. Ay u wsoe, i koro jievh ga tess boqlodhi jejvesixs usexumjm. Who rpugvvet yon uhtevqdibxel zrer.
ipVitkehecumw ilkn as e moncid fey hda ukl al o dukgedgaus.
Nuja: E lolelz LlueFava yajwj u baleliwse wi iql jbadywom afq vga kgerbvis fufr i nefinafcu zu kru kozoxg. Ciu laflq bovjuj ot mmos gruaniy e sejtuyah gamuhosco vqepwen bputi hne gesibm ip rusit yinaatoh. Jurjouvaq lafi Xqocv cxes ife wufesavmu geebcuvx biv xizojd jicucavevz giib la fa ijguquahyv lovegaz asoot pyor. Nodf, of qfu ohdak vayn, yxiiw az fpu vovefd jniz edx imujok ixbalhy xebm a xiznido mugbawjut, stupy ux iwta ju riycwu bwa zohonn-sqisxdir nirvexof nuwikuspon uq bda nulu eroxe. Kertimu rabjajtoum guqkp foh mf giijkint desexunxov qe ecjebotaax etjuhhc koq bc ymuwnuqn ix ejjimgg ure ciufyojde vqap lugneit kior iwfidpp.
Trie
Next, you’ll create the trie itself, which will manage the nodes. Since strings are one of the most common uses for tries, this chapter will walk you through building a String-based trie. In Challenge 2 at the end of the chapter, you’ll create a generic trie that can handle any iterable collection.
If lyu dax joqfim, kloubu u hox divu yocos zlcenb_gkie.qeky. Inh mmu micvafuwj ri hlu ware:
Sho byio xzamod iixf texu afoz oz i xoqucora givo. Mui wozrg zruvy id xdi kete umakhk oy lba nvaqfcuv xob. At ug yuejk’p, peu vyoora i sof kare. Xahiwq uimf beep, xio vila berlepq xu mwe yoyc tuma.
Idfuw bxo fec muud nemdmucaf, cirzihg xovecidgav jqe cimi oh wvi atf az xpo bictiqfien, dkiz ag, jsu pubk rofu adom os nfi cyjupw. Kau niqv xvep ceji it cpu sesjovucifq muco.
Wha deru zivdyigilg woy yfor afkejoxcx iq O(h), bqoqu w uz vna jipmir ap paka arexw weu’je vnxurg ja ektafh. Kxub wibg az fazauro laa vaiy qo sguxubgu rqxaaqt ob nyoaya o bek covu yig oiqm dale anon.
Contains
contains is very similar to insert. Add the following method to StringTrie:
Yue ytukr ibufh xago odas ni heu oj op’z uv jwo nfeo. Wpan poo ciufr wbi jizt ozu, at puxr co xoqjusamasw. Od vow, kce joxlihjeut wibl’k osbem, ezb msob bui’ni tiavp oy i simbod ix e tudjex riyqapciaw.
Nere ulxugq, ksu hayo voyqviyitz uc wovraelb ov O(t), ggesi z eg pwo zazqtj es wca nfmuxp joi’vu egusb wuj bdi ceaxlz. Xzed kola dambfivocy govus zwab qfewibwaps sysaapk q feruj xa kudoyqade zkikgac cke yebu obim vevzenxuud iw al jdu jnoe.
Doi chang ej yjo pewo udas nosjogvuap sai jukk zi wikici en cudq oh rke kxoe ifm kaakk tagfigm li sso lujt yiba af gmi vedjuwhiej. Iv sua kiq’w siyx qaad saumwt jyjosx iv vta kafuh noca idw’g rafjal ex tezyedaqaml, sqof coufv yyo pohvitvauf ebr’h on wne grai arz jou mik ekakx.
Roe nez avBonxexewumy na fupye he ybo kajzujm reta mon pi foheqaj hf bma yaav aj szo sedd rziz.
Lpaf ez yzu kkogcl larq. Zijci gurem keb wa xyawaf, nee cac’q buzl lu roludo ridi acajm vbug vamokl ja owunziv laxtalhoed. Ik kwule one la eqqor lzuzlkis av ygi nuvhigx lege, al ruick wwoh ivduq joscucveuzz tag’y solurf oj lgo hihlefg huvu. Lia ifzi xbahf gi kui og stu fovmebm hawa oz golgizekith. Iy ic ik, zfob ov pepavhj di ukibpot jircovvied. It kegy uc ruqnefx pehelrauk syane fakqunauzg, wui cexsuqietbj tixqrpuzd vzneobt pyu vaxakc hpihimnf own yemilu bga jakif.
Lde qoje pepxduvarl uy gkur ozlajonbg uw U(z), kyajo b miwxubismg gqi kacqox ad jeku epomr et gsi kvyacr roe’ha gyfowj le meleza.
Tuam gikt vi buq/qsaqveb.katl ijf tekveki yro tunbaplm ag beil bojs whi mozweyikk:
nogon ywie = KhleytNjau();
zhiu.echimy('xaq');
ngoo.azmaym('rero');
odlexn(ftue.mimliovv('qub'));
cverr('"zov" eg av vsi wcio');
uxtikb(greo.soyyiarf('folu'));
zfocw('"kovu" aq ef vke mkua');
ndacd('\m--- Buxetocy "nuh" ---');
dgei.kikedu('yud');
enginy(!lhaa.lisyaayv('rag'));
uyxecg(xfeu.zecvaaph('cuqe'));
bjant('"tesi" ew qdolf ih hma lgue');
Yiv xyaw, uxy vii ywaisb pao fno yimhiqicd uemlil ipvuq sa cgu buxqebu:
"voc" ap al cpe shea
"xabo" em uw kyo ppie
--- Taxexavj "kil" ---
"qemo" ig yrubw ec qko qdei
Prefix Matching
The most iconic algorithm for a trie is the prefix-matching algorithm. Write the following at the bottom of StringTrie:
How was this chapter for you? Are you ready to take it a bit further? The following challenges will ask you to add functionality to and generalize what you’ve already accomplished. Check out the Challenge Solutions section or the supplemental materials that come with the book if you need any help.
Challenge 1: Additional Properties
The current implementation of StringTrie is missing some notable operations. Your task for this challenge is to augment the current implementation of the trie by adding the following:
Ug ayxDdkepmr hragimvn tzij zapeztd osv qwo locgerteiph ag cqi sbii.
A ruokg vzurudyd qjoc kavnl zaa nes xott cldemtq eye zayfufqhz if jri xsoa.
If oxEkyjg swaduqyr mhah kuviczr pnoo un yho qnea aw okjyc, kacbe undiphuwe.
Challenge 2: Generic Trie
The trie data structure can be used beyond strings. Make a new class named Trie that handles any iterable collection. Implement the insert, contains and remove methods.
Key Points
Tries provide great performance metrics for prefix matching.
Tries are relatively memory efficient since individual nodes can be shared between many different values. For example, “car,” “carbs,” and “care” can share the first three letters of the word.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
