1. String symbol table implementations cost summary (in terms of how many characters are compared)
2. Tries [from retrieval, but pronounced "try"]
-- Store characters in nodes (not keys).
-- Each node has R children, one for each possible character.
-- For now, we do not draw null links.
-- Search in a trie: Follow links corresponding to each character in the key.
- Search hit: node where search ends has a non-null value.
- Search miss: reach null link or node where search ends has null value.
-- Insertion into a trie: Follow links corresponding to each character in the key.
- Encounter a null link: create new node.
- Encounter the last character of the key: set value in that node.
-- To delete a key-value pair:
- Find the node corresponding to key and set value to null.
- If node has null value and all null links, remove that node (and recur).
-- Java implementation:
public class TrieST<Value> { private static final int R = 256; private Node root = new Node(); private static class Node { private Object value; private Node[] next = new Node[R]; } public void put(String key, Value val) { root = put(root, key, val, 0); } private Node put(Node x, String key, Value val, int d) { if (x == null) x = new Node(); if (d == key.length()) { x.val = val; return x; } char c = key.charAt(d); x.next[c] = put(x.next[c], key, val, d+1); return x; } public boolean contains(String key) { return get(key) != null; } public Value get(String key) { Node x = get(root, key, 0); if (x == null) return null; return (Value) x.val; } private Node get(Node x, String key, int d) { if (x == null) return null; if (d == key.length()) return x; char c = key.charAt(d); return get(x.next[c], key, d+1); } public void delete(String key) { delete(root, key, 0); } private Value delete(Node x , String key, int d) { if ( x == null) return null; if ( d == key.length() ) { x.val = null; } else { char c = key.charAt(d); x.next[c] = delete(x.next[c] , key, d+1); } if ( empty(x) ) x = null; return x; } private boolean empty(Node x) { if ( x.val != null ) return false; for ( int i = 0 ; i < x.next.length ; i ++ ) { if ( x.next[i] != null ) return false; } return true; } }
-- Performance:
-- Search hit. Need to examine all L characters for equality.
-- Search miss.
- Could have mismatch on first character.
- Typical case: examine only a few characters (sublinear).
-- Space. R null links at each leaf.
(but sublinear space possible if many short strings share common prefixes)
3. Ternary search tries
-- Store characters and values in nodes (not keys).
-- Each node has 3 children: smaller (left), equal (middle), larger (right).
-- Search in a TST: Follow links corresponding to each character in the key.
-- If less, take left link; if greater, take right link.
-- If equal, take the middle link and move to the next key character.
-- Search hit. Node where search ends has a non-null value.
-- Search miss. Reach a null link or node where search ends has null value.
-- Java Implementation:
public class TST<Value> { private Node root; private class Node { private Value val; private char c; private Node left, mid, right; } public void put(String key, Value val) { root = put(root, key, val, 0); } private Node put(Node x, String key, Value val, int d) { char c = key.charAt(d); if (x == null) { x = new Node(); x.c = c; } if (c < x.c) x.left = put(x.left, key, val, d); else if (c > x.c) x.right = put(x.right, key, val, d); else if (d < key.length() - 1) x.mid = put(x.mid, key, val, d+1); else x.val = val; return x; } public boolean contains(String key) { return get(key) != null; } public Value get(String key) { Node x = get(root, key, 0); if (x == null) return null; return x.val; } private Node get(Node x, String key, int d) { if (x == null) return null; char c = key.charAt(d); if (c < x.c) return get(x.left, key, d); else if (c > x.c) return get(x.right, key, d); else if (d < key.length() - 1) return get(x.mid, key, d+1); else return x; } }
4. TST with R^2 branching at root: Hybrid of R-way trie and TST.
-- Do R^2-way branching at root.
-- Each of R^2 root nodes points to a TST.
5. String symbol table implementation cost summary:
6. TST vs. hashing
-- Hashing:
-- Need to examine entire key.
-- Search hits and misses cost about the same.
-- Performance relies on hash function.
-- Does not support ordered symbol table operations.
-- TSTs:
-- Works only for strings (or digital keys).
-- Only examines just enough key characters.
-- Search miss may involve only a few characters.
-- Supports ordered symbol table operations (plus others!).
-- Bottom line. TSTs are:
-- Faster than hashing (especially for search misses).
-- More flexible than red-black BSTs.
7. Ordered iteration: To iterate through all keys in sorted order:
-- Do inorder traversal of trie; add keys encountered to a queue.
-- Maintain sequence of characters on path from root to node.
public Iterable<String> keys() { Queue<String> queue = new Queue<String>(); collect(root, "", queue); return queue; } private void collect(Node x, String prefix, Queue<String> q) { if (x == null) return; if (x.val != null) q.enqueue(prefix); for (char c = 0; c < R; c++) collect(x.next[c], prefix + c, q); }
8. Character-based operations:
-- Prefix match: Find all keys in a symbol table starting with a given prefix.
-- Ex. Keys with prefix sh: she, shells, and shore.
-- application:
- Autocomplete in a cell phone, search bar, text editor, or shell.
- User types characters one at a time.
- System reports all matching strings.
public Iterable<String> keysWithPrefix(String prefix) { Queue<String> queue = new Queue<String>(); Node x = get(root, prefix, 0); collect(x, prefix, queue); return queue; }
-- Wildcard match. Keys that match .he: she and the.
-- Longest prefix: Find longest key in symbol table that is a prefix of query string.
-- Ex. Key that is the longest prefix of shellsort: shells.
public String longestPrefixOf(String query) { int length = search(root, query, 0, 0); return query.substring(0, length); } private int search(Node x, String query, int d, int length) { if (x == null) return length; if (x.val != null) length = d; if (d == query.length()) return length; char c = query.charAt(d); return search(x.next[c], query, d+1, length); }
9. String symbol tables summary:
-- Red-black BST.
- Performance guarantee: log N key compares.
- Supports ordered symbol table API.
-- Hash tables.
- Performance guarantee: constant number of probes.
- Requires good hash function for key type.
-- Tries. R-way, TST.
- Performance guarantee: log N characters accessed.
- Supports character-based operations.
相关推荐
SuRF: Practical Range Query Filtering with Fast Succinct Tries
字典数据结构的基准测试: hash tables, maps, tries等
Tries and suffix tries Ben LangmeadYou are free to use these slides. If you do, please sign the guestbook (www.langmead-lab.org/teaching-materials), or email me (ben.langmead@gmail.com) and tell me ...
leetcode 2 尝试 2 问题 1:单词方块列表() 问题 2:匹配 Camelcases() 问题3:前K个频繁重复的元素()
对大量的字符串采用字典树前缀压缩,比目前最优的存储结构还节省68%的存储空间。纯内存索引。
Redis尝试欢迎使用Redis Tries模块存储库! 该存储库的目的是在Redis中添加并实现对前缀尝试的支持。 什么是尝试? 特里树(也称为数字树,基数树或前缀树)是一种高效的搜索树,其中的键是字符串。 数据结构的名称...
E D I C TThe internal ...generalization of the formula holds for compacted tries, replacing the role of paths with the notion of extent, and the value 2n�2with the trie measure, an estimation of the
Tries and String MatchingWhere We've Been● Fundamental Data Structures ● Red/black trees, B-trees, RMQ, etc.● Isometries ● Red/black trees ≡ 2-3-4 trees, binomialheaps ≡ binary numbers, etc.● ...
Contents Overview 1 Lesson 1: Concepts – Locks and Lock Manager 3 Lesson 2: Concepts – Batch and Transaction 31 Lesson 3: Concepts – Locks and Applications 51 Lesson 4: Information Collection and ...
try and try i hope after several tries i ve get it
Image_Processing_Tries 尝试实现一些图像滤镜和图像处理算法
ADS 项目第 2 部分使用 Dijkstra 和 Binary Tries 为网络中的路由器实现数据包转发方案。 这是作为高级数据结构类的一部分完成的。
这是使用Merkle Prefix Tries的Authenticated Dictionary (一组键-值映射)和Authenticated Sets (一组值)的完整实现。 此数据结构允许非常小的(对数)成员资格和非成员资格证明。 这些数据结构还支持在动态...
#Tries — javascript 简单实现##什么是特里? 特里是一棵树。 它是一个 n 叉树,专为高效检索而设计。 效率有多高? trie 允许我们在 O(m) 中搜索字符串,其中 m 是该字符串中的字符数。 其他数据结构表现更好吗? ...
尝试
This project tries to target the vacuum behind the enormous evolution of online mapping the last decade. There are situations when keeping a lot of structured map data in a device for the field is ...
Resume: By default, gwget tries to continue any download. Notification: Gwget tries to use the Gnome notification area support, if available. You can close the main window and gwget runs in the ...
integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps and randomized meldable heaps; and graphs, including adjacency matrix and ...
使用dom4j解析xml,包括节点的操作、属性的操作、document对象写入新文件等操作。
projector, tries to generate a modality-invariant representation in the common subspace and to confuse the other process, modality classifier, which tries to discriminate between different modalities ...