公开(公告)号：US20130226885A1

公开(公告)日：2013-08-29

申请号：US13406549

申请日：2012-02-28

申请人： Giuseppe OTTAVIANO

发明人： Giuseppe OTTAVIANO

IPC分类号： G06F7/00

CPC分类号： G06F17/30961

摘要： Path-decomposed trie data structures are described, for example, for representing sets of strings in a succinct manner whilst still enabling fast operations on the string sets such as string retrieval or looking up a string with a specified identifier. A path-decomposed trie is a trie (tree data structure for storing a set of strings) where each node in the path decomposed trie represents a path in the trie. In various embodiments a path-decomposed trie data structure is represented succinctly by interleaving node labels and node degrees in an array and optionally by compressing the node labels using a static dictionary. Node labels may be string characters and a node degree may be a number of children of a node. In some embodiments a path-decomposed hollow trie data structure is used to provide a hash function for string sets.

摘要翻译： 描述路径分解的特里数据结构，例如，用于以简洁的方式表示字符串集合，同时仍然能够对字符串集进行快速操作，例如字符串检索或查找具有指定标识符的字符串。 路径分解的线索是路径中的每个节点分解的线索代表该线索中的路径的特里（树形数据结构，用于存储一组字符串）。 在各种实施例中，路径分解的特里数据结构通过在阵列中交织节点标签和节点度并且可选地通过使用静态字典压缩节点标签来简洁地表示。 节点标签可以是字符串字符，并且节点度可以是节点的子数。 在一些实施例中，使用路径分解的中空特里数据结构来提供用于字符串组的散列函数。