标签: trie

我最喜欢的大学数据结构之一就是Trie.如果共享前缀,它是一个很好的数据结构,用于保存大量字符串.查找也很好,因为它们是在字符串的O(| length |)处完成的,无论集合中有多少字符串.

相比之下,平衡树的设置项数量为O(log N),加上您为比较支付的费用.哈希表将涉及哈希计算,比较等.

因此,令我惊讶的是,在大多数语言的标准库中没有Trie实现.

我能想到的唯一原因是内存访问成本太高的可能性.如果进行树查找,则不是在调查O(log N)位置,而是在进行O(| length |)不同的位置,并产生所有后果.如果字符串很长,这可能会导致太多.

所以我想知道:我刚才描述的问题有多少？当您需要存储大型字符串或字符串映射时,您会怎么做？

我正在寻找在某些免费许可下发布的ANSI C HAT-trie实现.我还没找到一个.你能指点我一些独立的实现或者一个使用HAT尝试的程序,至少要知道如何以roght的方式实现它,好吗？

关于HAT-trie的原始论文可以在这里找到:http: //crpit.com/confpapers/CRPITV62Askitis.pdf

PS:如果从上面的论文编写时起,更快的缓存意识数据结构非常适合字符串演变,请指向我的论文或示例源代码.

我的联系人存储在手机中.让我们说我的联系人

Ram

Hello

Hi

Feat

Eat

At

当我输入信件时,'A'我应该得到所有匹配的联系人说"Ram, Feat, Eat, At".

现在我再打一个字母T.现在我的总字符串"AT"现在我的程序应该重用以前搜索的结果"A".现在它应该归还给我"Feat, Eat, At"

为此设计和开发一个程序.

这是三星移动开发的面试问题

我试着解决Trie data structures.无法获得重复使用已搜索字符串结果的良好解决方案.我也尝试过用字典数据结构的解决方案,解决方案也有同样的缺点Trie.

问题是我如何搜索键入的每个字母的联系人重新使用先前搜索的字符串的搜索结果？应该使用什么数据结构和算法来有效地解决问题.

我不是要求节目.所以编程语言对我来说并不重要.

状态机似乎是一个很好的解决方案.有没有人有建议？

对于百万联系人来说,解决方案应足够快

我有一系列套装,我想把它放在一个特里.

正常尝试由元素串组成 - 也就是说,元素的顺序很重要.设置缺少定义的顺序,因此可能会有更大的压缩.

例如,给定字符串"abc","bc"和"c",我将创建trie:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
      -> ('b',1) -> ('c',1)
      -> ('c',1)

但考虑到套{ 'a', 'b', 'c' },{ 'b', 'c' },{ 'c' },我可以创建上述线索,或者这些一一:

(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
      -> ('c',2) -> ('a',1)

(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
      -> ('b',1) -> ('c',1)
      -> ('c',1)

(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
      -> ('c',2) -> ('a',1)

(*,3) -> ('b',2) …

因为trie数据结构具有如此巨大的分支因子,并且每个子树完全独立于其他子树,所以似乎应该有一种方法通过并行添加所有单词来极大地加速给定字典的构造.

我关于如何执行此操作的初步想法如下:将互斥锁与trie中的每个指针相关联(包括指向根的指针),然后让每个线程遵循用于将单词插入到trie中的常规算法.但是,在遵循任何指针之前,线程必须首先获取该指针的锁定,以便在需要向trie添加新的子节点时,它可以在不引入任何数据争用的情况下执行此操作.

这种方法的缺点是它使用了大量的锁 - 一个用于trie中的每个指针 - 并且执行大量的获取和释放 - 每个输入字符串中的每个字符一个.

有没有办法在没有使用几乎同样多的锁的情况下并行构建一个trie？

在过去的谷歌集合包含了实现的TRIE.在番石榴中是否有任何TRIE实施？我需要一个有效的方法来在一组字符串中查找公共前缀.

谢谢 :-)

有谁知道我如何在多台机器上扩展 Trie？假设第一台机器空间不足，我需要从一个非常大的字典中添加更多单词，我该怎么做才能添加更多单词？（我是一名 Java 思想家，但我相信答案可能与语言无关）。我已经意识到我不能只为每个第一个角色说一台机器，但这并不能真正扩展。

问题

给定一个字符串列表,找到列表中出现在给定文本中的字符串.

例

list = ['red', 'hello', 'how are you', 'hey', 'deployed']
text = 'hello, This is shared right? how are you doing tonight'
result = ['red', 'how are you', 'hello']

'red'因为'共享'有'红色'作为子串

• 这与这个问题非常相似,只是我们需要查找的单词也可以是子字符串.
• 该列表非常大,随着用户数量的增加而增加,而文本的长度几乎相同.
• 我正在考虑一个解决方案,时间复杂度取决于文本的长度而不是单词列表,这样即使添加了大量用户,它也可以扩展.

解

• 我从给出的单词列表中构建了一个trie
• 在文本上运行dfs并检查当前单词与trie

伪代码

def FindWord (trie, text, word_so_far, index):
    index > len(text)
        return
    //Check if the word_so_far is a prefix of a key; if not return
    if trie.has_subtrie(word) == false:
       return 
    //Check if the word_so_far is a key; if ye add to …

我正在尝试构建一个Trie但是在具有非常有限的内存容量的移动电话上.

我认为最好将整个结构存储在磁盘上,并且只在必要时才加载,因为我可以容忍一些磁盘读取.但是,经过几次尝试后,这似乎是一件非常复杂的事情.

有什么方法可以将Trie存储在磁盘上(即仅部分加载)并保持快速查找属性？
这开始是一个好主意吗？

我正在寻找实现类型/自动完成搜索的乐趣.我在mongoDB中的架构中有一些属性,但我希望只能按类别,标题,预览或日期进行搜索.

这是我对单篇文章的mongoDB架构(我使用mongoose作为ORM):

{
    title: { type: String, required: true}
    , preview: { type: String, required: true}
    , body: { type: String, required: true}
    , category: {type: String}
    , created_at: { type: Date, default: Date.now }
}

每次我创建,更新或销毁时,我都必须重新编制索引,以便更新搜索.搜索将自动完成,例如,当我有两篇文章分别标题为"欢迎使用stackoverflow"和"如何避免stackoverflow"并且用户键入一个键时,'t'我会使用AJAX显示两篇文章,因为两者都有字符't'在他们的头衔.我也想强调每一个't'; 在't'中'to','t'以s 't'ackoverflow,表示查询命中东西.(我希望它看起来与我们在stackoverflow.com上搜索特定'标签'时类似)

现在的问题是我应该使用不同的模式进行索引,还是仅仅坚持我现有的模式？似乎我不会使用包含完整文章的'body'属性,并且其中包含数千个单词,因为我现在不打算进行全文搜索.

• 标题属性可能只有~45个字符,平均3或4个字.
• 类别大多只有1个单词,平均9-15个字符.
• 预览将是最大的数据集,其中包含约150个字符和20个字.

我可能想用trie数据结构来实现它.最重要的是,我可能会说,这样做的一种方法是通过AJAX请求每次击键将被路由到node.js处理程序,然后从那里进行查询到mongoDB将返回每个具有单词的条目有一个字母与用户输入的击键相匹配,作为JSON文件.然后,我将解析该JSON文件并显示每个条目.

那么问题是我如何将trie算法纳入我的计划？另一件事是我每次进行CRUD操作时都需要重建索引.

非常感谢任何有关正确方向的建议/指示或任何有助于我这样做的文章.(我希望做最好的练习/表演方式)谢谢.如果需要澄清这个问题,请告诉我.