Dictionary Trie Manipulation (Insertion)

Purpose
This post is about an algorithm for creating a trie from a set of words.

To do this, I am proposing instead to come up with an algorithm to add one word to an already existing trie, and to treat the creation of a trie as a series of add operations (with an empty trie as the degenerate case).

To understand what a dictionary trie is and what its advantages are, see my previous post (A Dictionary Trie).  Or google it.

Onward
Let us use the trie we've already generated from the previous post, and consider adding the following new words:

real
relied
rebates
reb

"reb" is probably not a real word. Just pretend it is and move on.



These words were chosen to highlight all the conditions we could run into when we add a word to an existing trie:

  1. "real" will split a node and extend the branch (with the growth internal).
  2. "relied" is probably the trickiest. It will extend the branch in two directions.
  3. "rebates" will split a node and extend the branch (with the growth at the leaf node and outwards).
  4. "reb" will switch an indicator to TRUE.
Adding "real"  (insertion string is prefix of target string)

In this scenario "real" will split a node and extend the branch (with the growth internal).

The above image shows that we are inserting a new node internal to the branch and extending the branch.  BE CAREFUL -- we are not just moving the old node down, we have also modified the characters it contains within (this distinction is important when doing functional language modifications).

The above diagram shows my convention of coloring the new nodes grey, and dotting the new edges to the tree graph.  A dashed node is an old node with a modified word-fragment. 

Algorithm
We enter the "alize" node with our insertion string as "al" (to understand this, realize that we had started at the top node with our insertion string as "real" but as "re" was the word fragment contained in the top node, we removed that prefix from our insertion string and submitted the new insertion string "al" into the sub-node).

Anyways, to repeat, we enter the the "alize" node with our insertion string as "al".  We see that our insertion string is the prefix of our target string. At this point we create a new node here.  We make "al" the word-fragment of our new node, and we turn its word-indicator to ON.  We shift the old node down and change its word-fragment by removing the prefix of our "al" insertion string.  Hence, "ize" is the shifted node, still pointing to all its previous children.

Quick Summary:
if ( insertion string is prefix to target string) then "extend branch internally"
   where "extend branch internally" = use the target string as 
                                      a new node's word-fragment, 
                                      and point this new node to the 
                                      old node with shortened word-fragment. 
Adding "relied" (insertion string and target string share a prefix)

In this situation "relied" will extend the branch in two directions.  This is the trickiest of our scenarios.

Algorithm 
Here we enter the node with our insertion string as "lied" and our target string as "lief".  Unlike the previous algorithm, the insertion string is not a prefix of the target string.  Nor is the converse true, "lief" is not a prefix of "lied".  But, we do notice that both the insertion and target string share a prefix.

So now, we create two new nodes, one with the shared prefix ("lie"), the other with the suffix of the insertion string ("d"). We point the shared prefix node to the insertion suffix node and to the old node,  making sure to modify the old node to change its word-fragment to the target string suffix ("f").


Quick Summary:
if ( insertion string and target string share prefix) then "create fork"
   where "create fork" = 1) use the target string shared prefix as a new node's word-fragment,
                         2) use the target strings suffix as a new node's word-fragment, now point #1 to this one
                         3) point this new node to the old node with shortened word-fragment. 


Adding "rebates" (target string is prefix of insertion string)
In this situation "rebates" will extend the branch (with the growth outwards at the leaf node).

Algorithm 
Here we enter the node with "bates" as our insertion string and "bate" as our target string.  We notice immediately that the target string is a prefix of the insertion string.

At this point, we take the subtracted suffix of our insertion string "s" and see if there is a child for this.  If not, we add it to the graph.  We create a new node with a word-fragment of "s" and point the current node to this new node (make sure to turn on its word-indicator).

Adding "reb" (target string is equal to insertion string)
In this "reb" will switch an indicator to TRUE.  This is probably the easiest of our scenarios, since nothing what we do modifies the structure of the tree.  All we are doing is recognizing that a node that was previously an intermediate non-word node, has now become a word node.

Algorithm 
Here we enter the node and see that our target string "b" and our insertion string "b" are the same. All we do is switch the word-indicator to ON if it was not already on.  If it was already on, then I think that proves that this word has already been inserted. Right?

Finally (or is it?)
After all these words have been added, and we have:
where this tree shows the transformations that took place. 

Remember, my arbitrary legend:
  • a grey node is brand new with a dotted arrow showing a new edge
  • a dashed node is a modification to a node (whether changing the word fragment or switching an indicator on)
Let's let this thing cool down, and we get our final tree:


But Are We Done?

At the top of this post we said that creation of a trie should be treated as repeated applications of insertion, and if we want to use these collected algorithms, we will need to do one more thing and that is define a starting trie.

So let's define the degenerate case.

Degenerate Trie (aka Empty Trie, aka the Top Node)

Our degenerate trie should be empty.  It should be the prefix of all words but not actually have a word-fragment, (or if you prefer, it's word-fragment should be "").  In any case, this is analogous to how regular expressions have beginning of line characters (^) or beginning of word characters (\b) -- anchors.


The key to using this degenerate case is to make sure that any `isPrefix` operator in any programming language will treat this as a prefix to all words.  If not, we can always add an is-top indicator to our data structure and modify our algorithms to check prefixes and whether the node is the top node.  We'll discuss that later.

Now that we have defined a degenerate trie, we can see what our first insertion will look like:

Bully!

Our final tree upon repeated applications of insertion will be:

yay!

Next Steps

In our first post on dictionary tries, we discussed 1) what a trie was, 2) how to retrieve words from it, and 3) what its advantages were.

This post focused on how to create that trie from insertions.  We got two things at once.

For our next step we could go many different ways.  Perhaps we could write delete code?  Maybe we need to start implementing this in some programing language?  Is there anyway to create an extremely basic algebra for tries (to add and subtract tries from each other)?  

28 comments:

  1. Our College is top engineering colleges in up As we all know, Entrepreneurship is applicable to all- those who are working as well as those who aspire to work for themselves or for some other entity. Whether an individual believes that he/she is a born entrepreneur or is forced to become one, it is always part of the work journey. With this thought, the Department of Business Administration best pgdm college in delhi ncr.. Our College is organizing a Workshop

    ReplyDelete
  2. Netrockdeals is India's most trusted website for online shopping. If you are someone who loves online shopping but are tired of wasting all your money then this is your one-stop solution for all types of shopping. Whether you want clothes, cosmetics, footwear, sportswear, sports gear, home appliances, gadgets, tickets for anything, travel accommodation or flights, food coupons, or anything else. you will find it on Netrockdeals. Myntra Coupons BookMyShow coupons Beardo coupon code Dominos Coupon 2gud Coupons They offer amazing deals, discounts, offers, and promo codes in all these categories. They have all the top and non-recognizable brands all on one page. Ajio Coupons Oyo coupons Decathlon coupons GoDaddy promo code booking.com offers 1mg Coupon FirstCry Coupons Redbus coupons You won't have to skim through the internet for different brands and products but you will find everything on Netrockdeals. Then you can look through all the deals and coupons of your selected product and can avail of that coupon on the portal of the main website while making the payment on the checkout page.NNnow coupons BigRock Coupon ResellerClub Bigbasket Offers Medlife coupon code best ac brands best laptops under 50000 Mamaearth Coupon Code  The best part is that not only you will save money by getting these coupons but also, you have the chance of earning cashback. They also have special deals and offers for every occasion, like Diwali, Christmas, Summer session, Best Air cooler in India, and all the other occasions where you will require to purchase gift right now they have amazing deals and offers regarding Summer sales that you can checkout and save your money. so shop from Netrockdeals and save money on all the occasions

    ReplyDelete
  3. Microsoft 365 has been designed to help worldwide users become more productive without building up work pressure. It comes with innovative Office applications and intelligent services along with world-class security. Today, Office 365 has become an integral part of numerous small or big organizations. Whether you want to complete or manage some personal work-related tasks, or you want to manage an entire office!Office.com/setup Webroot Login mcafee.com/activate TPLinkRepeater www.webroot.com/safe Gobank Login TP Link Extender Setup Norton Login Belkin Range Extender Setup You can do that in a very organized manner with the help of the feature-loaded Office 365 suite. Thus, it serves as your productivity booster across work and life. Moreover, Microsoft provides Office applications for different operating systems, including Windows, macOS, and Android devices

    ReplyDelete
  4. Your life is as good as your mindset
    mm88

    fastbet

    ReplyDelete
  5. Ill most likely can be purchased further formerly ever again since the exact approximately a lot sometimes in just claim most people screen this unique increase. เกมสล็อตออนไลน์

    ReplyDelete
  6. เกมส์สล็อตออนไลน์ PGSLOT เครดิตฟรี PGSLOT เกมสล็อตที่ได้รับความนิยมจากผู้เล่นทั่วโลกในตอนนี้ การเล่นสล็อตของเพื่อนๆสมาชิกทุกท่านจะไม่น่าเบื่ออีกต่อไปด้วยความพิเศษของ ทางเข้า MEGA GAME มือถือ ที่มีรูปแบบที่เล่นง่าย แจ็คพอตของ PGSLOT แตกง่ายแตกบ่อยที่สุด ด้วยเว็บไซต์ของเรา
    BETFLIX PG คือผู้ให้บริการเกมสล็อตจากค่าย ยักษ์ใหญ่ ที่มีผู้เล่นเข้าใช้บริการ มากที่สุด ทางเข้า PGSLOT รวมเกมสล็อตออนไลน์ กว่าหลายร้อย เล่นผ่านเว็บไซต์ตรง PGSLOT ผู้เล่นทุกท่านเล่นได้ตลอด ทั้งวัน สมัครสมาชิกผ่านเว็บ BETFLIX PG เล่นได้มือถือ และ คอมพิวเตอร์ ค้นหาเกมสล็อต ที่ดียอดเยี่ยมกราฟฟิก สวยงาม พร้อมฟังก์ชั่น เกมสล็อต ที่น่าสนใจ รวมเกมสล็อตออนไลน์ ที่

    ReplyDelete
  7. BETFLIX เว็บไซต์ที่ให้บริการเกมสล็อตออนไลน์ในรูปแบบมือถือและคอมพิวเตอร์ โดยมีค่ายเกมสล็อตยอดฮิตอย่าง slot online ฟรีเครดิต มาอยู่บนเว็บของ เว็บ BETFLIX ซึ่งเป็นเกมสล็อตที่ผู้เล่นสามารถทำเงินได้จริง และสร้างกำไรให้กับการเล่นสล็อต BETFLIX ได้แน่นอน โดยเกมสล็อตส่วนใหญ่ เป็นเกมสล็อตที่เล่นได้ง่าย พร้อมมี

    ReplyDelete
  8. MEGA GAME ทางเว็บของเรามีเคล็ดลับหารายได้จากการเล่นสล็อตทุกค่ายมาแนะนำให้ท่านได้เรียนรู้ และสนุกไปด้วยกันอีกมากมาย ในตอนนี้การหารายได้ออนไลน์มีหลากหลายรูปแบบ เล่นสล็อต MEGA GAME ไม่ว่าจะมาจากวิธีขายผลิตภัณฑ์เสริมของเกม MEGA GAME หรือไม่ PGSLOT ก็การขายของได้เงินจริง เกี่ยวกับบนสิ่งออนไลน์ แต่ว่าไม่ว่าจะอะไรก็แล้วแต่อย่างไรก็ตามบางครั้งก็อาจจะจำต้องใข้ทุนที่สูงมากมาย ๆ

    ReplyDelete
  9. BETFLIX สล็อตออนไลน์ PG SLOT ที่สุดของเกมออนไลน์ เล่นเกมบนสมาร์ทโฟน แบบล้ำเลิศสุด เข้าเกมสล็อตPG สมัครเล่นสล็อตกับ BETFLIX วันนี้รับโบนัส แรกเข้า 100% ทันที โบนัส 50% สำหรับสมาชิกใหม่ ด้วยความพิเศษของ พีจี สล็อต ที่มีรูปแบบของการเล่นที่ง่าย รูปแบบเกมแบบใหม่ ไม่น่าเบื่อ ไม่จำเจ ในแบบการเล่นเดิมๆ อีกต่อไป เข้าเกมสล็อตPG เป็นเกมที่แจ๊คพอต mega game แตกบ่อยที่สุด ได้โบนัส อย่างรวดเร็ว แค่ 5 นาที ก็สามารถเปลี่ยนท่าน เป็นเศรษฐีคนใหม่พร้อมที่จะรวย ไปกับ pg slot เว็บตรง หรือยัง? ถ้าพร้อมแล้ว ปุ่มสมัครสมาชิกด้านล่าง สมัครเล่นได้เลย ตอนนี้ และรับโบนัส สมัครใหม่ ไปด้วยเลย สมาชิกเก่า ก็มีโปรโมชั่นทุกวัน รับได้ทุกวันเลย mega game

    ReplyDelete
  10. betflixหากเอ่ยถึง ค่ายเกมสล็อต HACKSAW GAMING ผู้เล่นหลายท่าน อาจจะยังไม่คุ้น กับค่ายเกมนี้ เว็บ BETFLIX จึงอยากจะให้ สมาชิกทุกท่าน ทำความรู้จัก กับสล็อตค่ายนี้ ซึ่งสามารถ ทดลองเล่นสล็อต hacksaw เพื่อทำความ คุ้นเคยกับเกมสล็อต ในค่าย ที่มีอยู่จำนวนหนึ่ง มีความหลากหลาย และ น่าสนใจไม่น้อย ผู้พัฒนาเกม สร้างสรรค์ออกมา ให้ตอบโจทย์ ผู้เล่น เดิมพันสล็อตออนไลน์ ในยุคปัจจุบัน ทดลองเล่นสล็อต hacksaw

    ReplyDelete
  11. MEGA GAME เว็บตรงของทางเรานั้น จะมีทางเข้าจากทางเว็บตรง เว็บสล็อตอันดับ1 ของโลก มาโดยตรง เล่นกับเรา แหล่งรวมเกมสล็อตได้เงินจริง เข้าบัญชีที่มีเงินนจริง มีค่ายสล็อตให้เลือกเล่นครบครันภายในเว็บไซต์เดียวที่เราได้จัดขึ้นมาแล้ว เลือกเล่นที่มากมายและยังลุ้นรับความสนุกสนานเพียบ มาเล่นเกมจากเว็บสล็อตที่มาแรงอันดับ 1 ของโลกจากทางเราได้อย่างเต็มที่ MEGA GAME และเล่นอย่างไม่มีขีดจำกัด

    ReplyDelete
  12. BETFLIX คาสิโนออนไลน์ เว็บตรง ใหม่ล่าสุด BETFLIX ความบันเทิงรูปแบบใหม่ บนมือถือสมาร์ทโฟน ฝากถอน ไม่มีขั้นต่ำ การเล่นเกมคาสิโนออนไลน์ SA GAMING ท่านสามารถเข้า มาเล่นเกมเดิมพันได้ง่าย ๆ ตอบโจทย์ลูกค้า คน ที่จะเข้ามาร่วมเล่น เกมเดิมพันออนไลน์ อย่างมากในตอนนี้ ไม่ว่าเวลาจะผ่าน ไปนานแค่ไหน ก็ตามเว็บไซต์ เกมเดิมพันของเรา ก็ยังคงเป็นเว็บไซต์ เกมคาสิโนออนไลน์ที่ ตอบโจทย์ และ มีลูกค้าเข้ามาร่วมสนุกใน 1 วันเป็นจำนวนมาก เป็นเว็บเดิมพัน megagame ที่กล้า การันตีเลยว่าลูกค้า ที่เข้ามาร่วมเล่นเกม คาสิโนออนไลน์ กับทางเว็บไซต์ ของเราจะต้องชื่นชอบ sa gamingเข้าสู่ระบบ จะต้องไปครับใจ ในเรื่องของงาน บริการเกมเดิมพัน คาสิโนออนไลน์ เว็บไซต์เกมของเราอยู่แล้ว megagame

    ReplyDelete
  13. MEGA GAME สมัครลงทุนเดิมพัน สล็อตเว็บตรงแท้ ถือว่าเป็นช่องทางที่กำลังได้รับการการรันตี จากผู้เล่นทั้งหลาย ว่าเป็นอย่างมากในปัจจุบันนี้ยิ่งในปี 2022 ผู้คนยิ่งหันมาชื่นชอบและสนใจลงทุนกันเล่นเกมสล็อตออนไลน์กันเป็นจำนวนมากยิ่งขึ้นนั่นก็เพราะว่าลงทุนน้อย MEGAGAMEแต่ว่าผลตอบแทนคุ้มค่ายิ่งหากใครสามารถทำรางวัลแจ็คพอตภายในเกมแตกได้ผู้เล่นก็จะได้รับการจ่ายตอบแทน

    ReplyDelete
  14. สล็อต การเล่นเกมมีความสนุกสนานกับ MEGA GAME ค่ายเกมบาคาร่า จะกลายเป็นอีกหนึ่งช่อง ทางการเล่นเกม ที่หลากหลายขึ้นให้คุณ นั้นได้มีโอกาสที่ จะสร้างความ บันเทิงให้กับตัวคุณเองได้ อย่างแน่นอน เพราะทุกวันนี้การเดิมพัน เกมไพ่บาคาร่าออนไลน์ นั้นก็มีหลากหลาย ผู้ที่คอยสร้างเกมไพ่ มาให้คุณได้เข้าเล่น กันเป็นอย่างดี นั่นเอง และรวมไปถึงในเรื่อง

    ReplyDelete
  15. betflixสวัสดีนักเสี่ยงโชคชาว BETFLIX สำหรับใครที่เป็นักเสี่ยงโชคมือใหม่กับเรา BETFLIX เครดิตฟรี 100 เมื่อนักเสี่ยงโชคเข้าสู่ระบบ เครดิตฟรีแค่สมัครล่าสุด 2022 แล้วเข้าเล่นสล็อต เครดิตฟรีถอนได้นักเสี่ยงโชคสามารถได้รับโบนัส หรือโปรโมชั่นได้ทุกวัน Bmk999 เครดิต ฟรี เพียงสมัครครั้งแรก ก็รับเครดิตฟรี กันไปได้เลย เพื่อให้นักเสี่ยงโชคได้สร้างรายได้ กลับไปจากการเล่นเว็บ MEGA GAME เครดิตฟรี

    ReplyDelete
  16. เว็บไซต์เกมที่มีความทันสมัย PG SLOT AUTO เล่นได้หลากหลาย ทั้งสล็อตออนไลน์ คาสิโนออนไลน์ อาเขต และยิงปลา ให้ได้เล่นตลอด 24 ชั่วโมง เดิมพันได้ดั่งใจต้องการ ไม่ว่าจะอยู่ที่ใดของประเทศ ฝากถอนได้สะดวกสบาย แจ็คพ็อตแตกได้ตลอดเวลา

    ReplyDelete
  17. เว็บเกมสล็อตรูปแบบใหม่ มีให้เล่นหลากหลาย มากถึง 300 เกม แบบที่คุณสามารถเล่น และดาวน์โหลด PG SLOT AUTO เหมาะสำหรับนักเล่นเกมมือใหม่ สมัครสมาชิกวันนี้ ฝากเข้ามาเพียง 29 บาทก็สามารถรับเครดิตไปเลยมากถึง 100 บาท รองรับการเล่นผ่านมือถือทุกรุ่น

    ReplyDelete
  18. เล่นได้มากมาย กับเกมสล็อตของค่าย PG เล่นได้ดั่งใจ PG เครดิตฟรี ทำได้โดยไม่มีเงื่อนไข เล่นได้เลยผ่านเว็บไซต์ PGSLOTGAMES เดิมพันการเล่นได้ตั้งแต่หนักหน่วย ไปจนถึงหลักพัน ทำกำไรได้ดั่งใจ เพียงแค่ทำการสมัครสมาชิก ก็สามารถทำกำไรได้อย่างง่ายดาย เล่นได้ตอนนี้เลย

    ReplyDelete
  19. เพียงแค่สมัคร ก็สามารถได้รับเครดิตฟรีกับเราได้แล้ว ผ่านเว็บไซต์ PGSLOT-AUTO เล่นได้ตื่นต้น รับเงินรางวัลมากมายได้ตลอด 24 ชั่วโมง เครดิตฟรี PG หากเล่นแล้วมีความผิดปกติก็สามารถติดต่อเราได้ตลอด ผ่านไลน์แอด PGXX เราพร้อมตอบทุกปัญหา แล้วแก้ไขได้ทุกปัญหา

    ReplyDelete
  20. Very amusing as well as exciting details offered in this post. Really taken joy in while reviewing it.
    urlopener.co.uk
    onlinefilmek.co.uk

    ReplyDelete
  21. พร้อมให้คุณได้เล่นเกมผ่าน สมาร์ทโฟน แอพลิเคชั่น สนุกกับการเล่นที่แสนจะเสถียร อำนวยความสะดวก เล่นได้ทุกที่ ทุกกเวลา เล่นได้ผ่านโทรศัพท์ในหลากหลายเวอร์ชั่น ดาวน์โหลดPG มีเกมให้เล่นมากกว่า 300 เกม เล่นเกมได้เลยตอนนี้ผ่านเว็บไซต์ PGSLOTGAMES

    ReplyDelete
  22. PGSLOTGAMES เว็บเกมสล็อตน้องใหม่ เล่นได้ไม่ซ้ำ กับการบริการที่ดีที่สุด เล่นได้อย่างไม่มีสะดุด เล่นได้แบบไม่ต้องดาวน์โหลด เหมาะมากสำหรับมือใหม่ เล่นได้หลากหลายรูปแบบ ดาวน์โหลด PG SLOT พร้อมรับรางวัล และแจ็คพ็อตใหญ่ได้เลยผ่านเว็บไซต์ พีจีสล็อต

    ReplyDelete
  23. Many thanks for this educative as well as mind-blowing site. I am pretty jubilant to get a hold of this kind of information on your web site. uwatchfree

    ReplyDelete
  24. I enjoyed going through this beneficial material shared with interesting simple facts. Appreciations for sharing this kind of understanding.
    uwatchfree
    Playtubes

    ReplyDelete
  25. I really love to review your posts because of your appealing thoughts discussed in the post that not just entertain yet additionally help us find out lots of aspects.
    Akhtar Iqbal
    Muhammad Usman
    Muhammad Ali

    ReplyDelete
  26. I genuinely experienced while taking a look at those unique information in this article.
    Discover Everything
    The Knowledge Hub

    ReplyDelete
  27. Great blog, I'm so much in love with this article for the well-researched content

    ReplyDelete
  28. Wonderful article. I love your style of writing. It’s inspiring, and I am happy

    ReplyDelete