标签: trie

我有一个前缀trie.在关系数据库中表示此结构的推荐架构是什么？我需要子串匹配才能保持高效.

我有一个问题:我需要根据文件路径前缀节省空间的文件系统数据查找.换句话说,前缀搜索已排序的文本.你说,使用trie,我也想到了同样的事情.麻烦的是,尝试不够节省空间,没有其他技巧.

我有相当数量的数据:

• 在磁盘上以纯文本Unix格式列出大约450M
• 大约800万行
• gzip默认压缩到31M
• bzip2默认压缩到21M

我不想在内存中接近450M的任何地方吃东西.在这一点上,我很乐意在大约100M左右使用,因为前缀形式有很多冗余.

我正在使用C#来完成这项工作,并且直接实现trie仍然需要为文件中的每一行提供一个叶子节点.假定每个叶子节点都需要对最后一个文本块进行某种引用(32位,比如指向一个字符串数据数组的索引以最小化字符串重复),并且CLR对象开销是8个字节(使用windbg/SOS验证) ,我将花费> 96,000,000字节的结构开销,根本没有文本存储.

让我们看一下数据的一些统计属性.当塞进一个特里:

• 文字总数独特的"块"约110万
• 文本文件中磁盘上大约16M的唯一块总数
• 平均块长度为5.5个字符,最大值为136
• 当没有考虑重复时,总共大约5200万个字符
• 内部trie节点平均约6.5个孩子,最多44个
• 约1.8M内部节点.

叶片产生的过剩率约为15%,多余的内部节点产生率为22% - 过量创建,我的意思是在构造期间创建的叶子和内部节点,但不是在最终的trie中,作为每种类型的最终节点数的一部分.

这是来自SOS的堆分析,指示使用最多内存的位置:

 [MT    ]--[Count]----[   Size]-[Class                                          ]
 03563150       11         1584 System.Collections.Hashtable+bucket[]
 03561630       24         4636 System.Char[]
 03563470        8         6000 System.Byte[]
 00193558      425        74788      Free
 00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
 03562b9c        6     11573372 System.Int32[]
*009835a0  1456066     23297056 StringTrie+InteriorNode
 035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0  1456085     69730164 System.Object[]
*03560a00  1747257     80435032 System.String
*00983a54  8052746     96632952 StringTrie+LeafNode

将Dictionary<string,int>被用于映射串块到索引到List<string>,并能特里施工后丢弃,虽然GC似乎并没有被删除它(一对夫妇明确集合了这个转储前完成) - !gcroot在SOS并不表示任何根,但我预计后来的GC会释放它.

MiniList<T> …

我试图在Java中实现一个非常简单的Trie,支持3个操作.我希望它有一个insert方法,一个has方法(即trie中的某个单词),以及一个以字符串形式返回trie的toString方法.我相信我的插入工作正常,但是并且toString被证明是困难的.这是我到目前为止所拥有的.

特里班.

public class CaseInsensitiveTrie implements SimpleTrie {

    //root node
    private TrieNode r;

    public CaseInsensitiveTrie() {
        r = new TrieNode();
    }

    public boolean has(String word) throws InvalidArgumentUosException {
        return r.has(word);
    }

    public void insert(String word) throws InvalidArgumentUosException {
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        CaseInsensitiveTrie t = new CaseInsensitiveTrie();

        System.out.println("Testing some strings");
        t.insert("TEST");
        t.insert("TATTER");
        System.out.println(t.has("TEST"));
    }
}

和节点类

public class TrieNode {

    //make child nodes
    private TrieNode[] c;
    //flag for end …

我一直在阅读一些有关尝试的内容，以及它们如何成为提前设计的良好结构。除了 trie 之外，您通常还有节点的键/值对和预先计算的 top-n 建议，以缩短响应时间。

通常，根据我收集的信息，最好将它们保留在内存中以便快速搜索，例如这个问题中建议的内容：拼字游戏单词查找器：构建特里树，存储特里树，使用特里树？。但是，如果您的 Trie 太大而您必须以某种方式对其进行分片怎么办？（例如，也许是一个大型电子商务网站）。

预先计算建议的键/值对显然可以在键/值存储中实现（保存在内存中，如 memcached/redis 或数据库中，并根据需要水平调用），但是存储的最佳方式是什么如果内存无法容纳的话，会使用 trie 吗？是否应该这样做，或者每个分布式系统都应该在内存中保存部分 trie，同时复制它以使其不会丢失？

或者，可以使用搜索服务（例如 Solr 或 Elasticsearch）来生成搜索建议/自动完成，但我不确定性能是否达到此特定用例的标准。Trie 的优点是您可以根据其结构预先计算前 N 个建议，让搜索服务处理网站上的实际搜索。

我知道有现成的解决方案，但我最感兴趣的是学习如何重新发明轮子，或者如果有人想讨论这个主题，至少可以了解一下最佳实践。

你怎么看？

编辑：我还看到了这篇文章： https: //medium.com/@prefixyteam/how-we-built-prefixy-a-scalable-prefix-search-service-for-powering-autocomplete-c20f98e2eff1，它基本上涵盖了使用使用 Redis 作为跳跃列表的主要数据存储，并使用 mongodb 作为 LRU 前缀。似乎是一个不错的方法，但我仍然想了解是否有其他可行/更好的方法。

假设构建了一个字典单词的一般Trie,那么在遍历期间检查4种拼写错误 - 替换,删除,转置和插入的最佳方法是什么？

一种方法是找出给定单词的n个编辑距离内的所有单词,然后在Trie中检查它们.这不是一个糟糕的选择,但这里更好的直觉似乎是使用动态编程(或递归等效)方法来确定在遍历期间修改单词后的最佳子尝试.

任何想法都会受到欢迎!

PS,会欣赏实际输入,而不仅仅是答案中的链接.

我很困惑Trie实现如何以最紧凑的形式节省空间并存储数据!

如果你看下面的树.在任何节点上存储字符时,还需要存储对该字符的引用,因此对于存储其引用所需的字符串的每个字符.好的,我们在公共角色到达时节省了一些空间,但是在存储对该角色节点的引用时我们失去了更多的空间.

那么维护这棵树本身是不是有很多结构开销呢？相反,如果使用TreeMap代替这个,让我们说实现一个字典,这可以节省更多的空间,因为字符串将被保存在一个片段中因此没有浪费存储引用的空间,不是吗？

鉴于以下......

(def inTree
 '((1 2)
   (1 2 3)
   (1 2 4 5 9)
   (1 2 4 10 15)
   (1 2 4 20 25)))

你会如何将它变成这个特里？

(def outTrie
 '(1
    (2 ()
       (3 ())
       (4 (5
            (9 ()))
          (10
            (15 ()))
          (20
            (25 ()))))))

我是第一次使用trie.我想知道哪个是用于trie的最佳数据结构,同时决定哪个是应该遍历的下一个分支.我正在寻找一个数组,一个hashmap和一个链表.

用于插入和搜索的trie数据结构的最佳/最差/平均情况复杂度(以Big-O表示法)是多少？

我认为这适用O(K)于所有情况,其中K是插入或搜索的任意字符串的长度.有人会证实吗？

我有一个我用词典创建的特里.我想用它来进行拼写检查(并在字典中建议最接近的匹配,也许是对于给定数量的编辑x).我想我会在目标单词和字典中的单词之间使用levenshtein距离,但有没有一种智能的方法可以遍历trie而不会分别在每个单词上运行编辑距离逻辑？我该如何进行遍历和编辑距离匹配？

例如,如果我有单词MAN,MANE,我应该能够在MANE中重用MAN上的编辑距离计算.否则Trie不会用于任何目的