Tries Data Structure

Tries Data Structure. Tries. Trie is a special structure to represent sets of character strings. Can also be used to represent data types that are objects of any type e.g. strings of integers. The word “trie” is derived from the middle letters of the word “ retrieval ”. Tries: Example.

Share Presentation

Embed Code

Link

• node
• character strings
• node node
• trie node
• represent data types
• words character strings separated

bianca-mullins + Follow

Tries Data Structure

An Image/Link below is provided (as is) to download presentation Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author. Content is provided to you AS IS for your information and personal use only. Download presentation by click this link. While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server. During download, if you can't get a presentation, the file might be deleted by the publisher.

Presentation Transcript

1. Tries Data Structure
2. Tries • Trie is a special structure to represent sets of character strings. • Can also be used to represent data types that are objects of any type e.g. strings of integers. • The word “trie” is derived from the middle letters of the word “retrieval”.
3. Tries: Example One way to implement a spelling checker is • Read a text file. • Break it into words( character strings separated by blanks and new lines). • Find those words not in a standard dictionary of words. • Words in the text but not in the dictionary are printed out as possible misspellings.
4. Tries: Example It can be implemented by a set having operations of : • INSERT • DELETE • MAKENULL • PRINT A Trie structure supports these set operations when the element of the set are words.
5. T S H I I E I N N $ N N S $ $ G $ $ $ $ Tries: Example
6. Tries: Example • Tries are appropriate when many words begin with the same sequence of letters. • i.e; when the number of distinct prefixes among all words in the set is much less than the total length of all the words. • Each path from the root to the leaf corresponds to one word in the represented set. • Nodes of the trie correspond to the prefixes of words in the set.
7. Tries: Example • The symbol $ is added at the end of each word so that no prefix of a word can be a word itself. • The Trie corresponds to the set • Each node has at most 27 children, one for each letter and $ • Most nodes will have many fewer than 27 children. • A leaf reached by an edge labeled $ cannot have any children.
8. Tries nodes as ADT • A node in a trie can be viewed as: • Mapping whose domain is • And whose value set is the type “Pointer to trie node”. • A trie can be identified with its root. • => ADT’s TRIE and TRIENODE have the same data type. • However, there operations are different.
9. Operations on Tries nodes • ASSIGN(node,c,p): Assign value p (a pointer to a node) to character c in node node. • VALUEOF(node, c): Produce the value associated with character c in node. • GETNEW(node, c): Make the value of node for character c be a pointer to a new node. • MAKENULL(node): Makes node to be null mapping.
10. Sets • A Set is a collection of members (or elements). • Each member of a set is either itself a set or is a primitive element called an atom. • All elements of a set are different.
11. Sets • Set can be integers, characters or strings. • All elements can be of the same type. • Atoms in a set can be linearly ordered. • A linear order (denoted by <) on a set S (“less than” or precedes”) satisfies two properties: • For any a and b in S, exactly one of a < b, a = b, or b < a is true. • For all a, b and c in S, if a < b and b < c, then a < c (transitivity).
12. Set Notation • A set of atoms is generally exhibited by putting curly brackets around its members. • Example: , denotes the set whose members are 1 and 4. • Set is not a list, since order of elements in a set is not important. • is the same set as
13. Operations on Set • UNION: If A and B are sets then A B is the set of elements that are members of A or B or both. • INTERSECTION:A B is the set of elements, that are present both in A and B. • DIFFERENCE:A – B is the set of elements that are members of A but are not members of B.
14. Abstract Data Types Based on Sets The Set ADT can incorporate some other operations as well. • MERGE(A,B,C): Assigns to the set variable C the value A  B, the operator is not defined if A B Ø • MEMBER(x,A): Returns true if x A and returns false if x  A. • MAKENULL(A): makes the Null set be the value for set variable A.
15. Abstract Data Types Based on Sets • INSERT(x,A): xis an element of the type of A’s members. Makes x a member of A. A = A  • DELETE(x,A): removes x from A. A = A – < x >• ASSIGN(A,B): sets the value of set variable A to be equal to the value of set variable B.
16. Abstract Data Types Based on Sets • MIN(A): Returns the least element in set A.This operator is applicable only when the member of A are linearly ordered. • MAX(A): Returns the largest element in set A.This operator is applicable only when the member of A are linearly ordered. • EQUAL(A,B): Returns true if and only if sets A and B consists of the same elements. • FIND(x): Works for collection of disjoint sets. Returns the name of the unique set of which x is a member.
17. Reference • “Data Structures and Algorithms” by A. V. Aho, J. E. Hopcroft, J. D. Ullman.

• Related
• More by User

Tries

Tries. Outline and Reading. Standard tries ( §9.2.1 ) Compressed tries ( §9.2.2 ) Suffix tries ( §9.2.3 ) Huffman encoding tries ( §9.3.1 ). Preprocessing the pattern speeds up pattern matching queries

296 views • 15 slides

Tries

Tries. Standard Tries Compressed Tries Suffix Tries. Text Processing. We have seen that preprocessing the pattern speeds up pattern matching queries

502 views • 11 slides

Data Structure

Data Structure. Chapter 1 – Basic Concepts. 1.5 Algorithm Specification. Definition An algorithm is a finite set of instructions that, if followed, accomplishes a particular task and satisfies: Input: 0 or more quantities are externally supplied. Output: At least one quantity is produced.

403 views • 32 slides

Tries

Tries. A useful data structure of storing and retrieving Strings and things. Tries.

398 views • 10 slides

T9 and Tries

T9 and Tries. CSE 374 Homework 5 , Spring 2009. T9 Predictive Text. What is T9? Demo T9onyms: 1. 22737: acres, bards, barer, bares, baser, bases, caper, capes, cards, cares, cases 2. 46637: goner, goods, goofs, homer, homes, honer , hones, hoods, hoofs, inner

232 views • 10 slides

T9 and Tries

T9 and Tries. T9 Predictive Text. What is T9? Demo T9onyms: 1. 22737: acres, bards, barer, bares, baser, bases, caper, capes, cards, cares, cases 2. 46637: goner, goods, goofs, homer, homes, honer , hones, hoods, hoofs, inner 3. 2273: acre, bard, bare, base, cape, card, care, case

218 views • 10 slides

DATA STRUCTURE

DATA STRUCTURE. Instructor: Dai Min Office: XNA602 Fall 2006. CHAPTER 4 Graphs. Basic terminology Graph Implementation Graph Traversals Minimal Cost Spanning Tree Shortest Path Problem. 4. 1 Graphs. 1) Definition A graph G consists of two sets

1k views • 65 slides

Data Structure

Data Structure. Sang Yong Han http://ec.cse.cau.ac.kr/. Arrays. Array: a set of pairs ( index and value ) data structure For each index, there is a value associated with that index. representation (possible) implemented by using consecutive memory.

462 views • 34 slides

Tries

Tries. [Fredkin, CACM 1960]. 1. 2. 2. 0. 5. 1. 4. 5. 6. 7. 2. 3. (Compacted) Trie. Performance: Search ≈ O(|P|) time Space ≈ O(K + N). s. y. z. omo. aibelyite. stile. zyg. ( 2 ; 3,5). czecin. etic. ygy. ial.

444 views • 27 slides

Tries

Tries. Multiway Trees. Trees with possibly more than two branches at each node are know as Multiway trees. 1. Orchards, Trees, and Binary Trees 2. Lexicographic Search Trees: Tries 3. External Searching: B-Trees 4. Red-Black Trees. Lexicographic Search Trees: Tries.

1.23k views • 59 slides

Tries

Tries. Trees of order >= 2 Variable length keys The decision on what path to follow is taken based on potion of the key Static environment, fast retrieval but large space overhead Applications : dictionaries text searching (patricia tries) compression (Ziv-Lembel encoding). Example.

412 views • 29 slides

DATA STRUCTURE

DATA STRUCTURE. 第 5 章 数组和广义表. 第 5 章 数组和广义表. 前述线性结构 其中的数据元素是非结构的原子类型 （值不可分解） 数组、广义表 是线性表的扩展： 数据元素本身也是一种数据结构 ( 线性表 ). §1 数组的定义和操作. 数组是所有程序设计语言都设定的固有类型 数组的基本概念和运算已在 C 程序设计中熟悉 从数据结构的观点讨论 ●逻辑结构 ●存储方式. 一、逻辑结构. 以二维数组为例

602 views • 38 slides

Data Structure

Data Structure. Spring Semester 2012 School of Computer Science & Engineering Chung-Ang University. Sang Yong Han (Professor) Office hour: Tuesday 14:00 – 14:50 eMail: hansy@cau.ac.kr. Administrative Matters. http://ec.cse.cau.ac.kr (web site). Teaching Assistant

838 views • 73 slides

Data Structure

Data Structure. Dr. Mohamed Khafagy. Abstraction. . Abstraction is a technique in which we construct a model of an entity based upon its essential Characteristics while ignoring the inessential details. . The principle of abstraction also helps in handling the

392 views • 15 slides

Tries

Tries. Definition. A trie is an index structure that is particulary useful when key values are of varying size. Trie is a tree of degree m >= 2 in which the branching at any level is determined not by the entire key value, but by only a potion of it.

267 views • 14 slides

Tries

Tries. When searching for the name “Smith” in a phone book, we first locate the group of names starting with “S”, then within those we search for “m”, etc. Idea: Perform a search based on a prefix of the key, rather than a comparison of the whole key.

141 views • 11 slides

Tries

Tries. Preprocessing the pattern speeds up pattern matching queries After preprocessing the pattern, KMP’s algorithm performs pattern matching in time proportional to the text size

160 views • 13 slides

Data structure

Data structure. The logical and mathematical model of a particular organization of data is called Data structure . The main characteristics of a data structure are: Contains component data items which may be atomic or another data structure

1.35k views • 124 slides

Higher Order Tries

0. 1. 2. 3. 4. 5. 6. 7. 8. 9. Higher Order Tries. Key = Social Security Number. 441-12-1135 9 decimal digits. 10 -way trie (order 10 trie). Height <= 10. Social Security Trie. 10 -way trie Height <= 10 . Search => <= 9 branches on digits plus 1 compare. 100 -way trie

285 views • 27 slides

Data Structure

Data Structure. Lecture 10 Thursday, 28 Aug 2005. Algorithms and Complexity. Examples of some well-known algorithms: Euclid algorithm for GCD, Gaussian elimination, quick sort, fast Fourier transform Complexity: how long does it take to do a computation, and how much memory do we use.

407 views • 29 slides