Data structure tries

This is a brief explanation of a data structure tries

1. TRIES AN EXCELLENT DATA STRUCTURE FOR STRINGS

2. Tries Instructor Md. Shamsujjoha Senior Lecturer Department of CSE East West University Presented by: Md. Naim Khan Id :2014-2-60-092 Md. Riad Khan Id :2014-1-60-040 Slide 2

3. Overview History & Definition Types of Tries Standard Tries Compressed Tries Suffix Tries Conclusion Slide 3

4. History The term trie comes from re trie val. This term was coined by Edward Fredkin , who pronounce it tri as in the word retrieval. Slide 4

5. Definition of Tries A data structure for representing a collection of strings. In computer science, a trie , also called digital tree and sometimes radix tree or prefix tree. Tries support fast pattern matching. Slide 5

6. Properties of a tries A multi-way tree. Each node has from 1 to n children. Each edge of the tree is labeled with a character. Each leaf nodes corresponds to the stored string, which is a concatenation of characters on a path from the root to this node. Slide 6

7. Standard Trie The standard trie for a set of strings S is an ordered tree such that: *Each node but the root is labeled with a character. * T he children of a node are alphabetically ordered. *The paths from the external nodes to the root yield the strings of S. Slide 7

8. Standard Tries - Insertion Strings ={an, and, any, at} n a d t y Root Slide 8

9. Example of Standard tries Example: Standard trie for the set of strings S = { bear, bell, bid, bull, buy, sell, stock, stop } t e s u i e b o l l l a d y c k p l l l r Root Slide 9

10. Handling keys(strings) When a key(string) is a prefix of another key. How can we know that “an” is a word? Example: an, and n a d t y Root Slide 10

11. Handling keys(strings) We add a special termination symbol “$’’ We append the “$’’ to each keyword Strings={ an, and, any, at} n a d t y Root $ $ $ $ Slide 11

12. Standard Tries- Searching Search hit: Node where search ends has a $ symbol Search - sea n a d t y Root a t e s $ $ $ $ $ $ Slide 12

13. Standard Tries- Deletion Three cases Word not found…! Word exists as a stand alone word. Word exists as a prefix of another word Slide 13

14. Standard Tries- Deletion Word not found return false. Word exists as a stand alone word part of any other word does not a part of any other word Slide 14

15. Standard Tries- Deletion Part of any other word Delete - sea n a d t y Root a t e s $ $ $ $ $ $ Slide 15 Deleted

16. Standard Tries-Deletion Does not a part of any other word Delete - set n a d t y Root t e s $ $ $ $ $ Slide 16 Deleted

17. Standard Tries- Deletion Word exists as a prefix of any other word. Delete - an n a d t y Root a t e s $ $ $ $ $ $ Slide 17 Deleted

18. Compressd Tries Tries with nodes of degree at least 2 Obtained by standard tries by compressing chains of redundant nodes Slide 18

19. Compressed Trie - Example In order to understand Compressed Trie we need to see the Standard Trie Example: t e s u i e b o l l l a d y c k p l l l r Root Standard Trie Slide 19

20. Compressed Tries Example Compressed Tries: S = { bear, bell, bid, bull, buy, sell, stock, stop } b s e u to id ell ll ar ll y ck p Root Compressed Trie Slide 20

21. Suffix Tries A suffix trie is a compressed trie for all the suffixes of a text. Suffix trie are a space-efficient data structure to store a string that allows many kinds of queries to be answered quickly. Slide 21

22. Example of Suffix Tries Let us consider an example text “soon $″. Root s o o n o o n n n $ $ $ $ $ Slide 22 soon$ oon $ $ n$ on$ Done

23. After alphabetically ordered the trie will look like Root s o o n o o n n n $ $ $ $ $ Example of Suffix Tries

24. Understanding Requirements Insertion is faster as compared to the Hash Table Lookup is much more faster than Hash Table implementations There are no collision of different keys in tries Slide 23

25. References Web pages http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie01.html http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr45102/Tries.pdf http://www.ideserve.co.in/learn/trie-delete http://algs4.cs.princeton.edu/lectures/52Tries.pdf Book Data Structure and Algorithm by Alfred V. Aho Jeffery D. Ullman   John E.HopcroftJohn Slide 24

26. Questions or Suggestions Slide 25

27. Thank you Slide 26 Inquiry [email protected] [email protected]