可能重复:
我在哪里可以找到基于Trie的标准地图实现？
我想在Java中使用Trie,是否有可以使用的实现？(我试过寻找一个,但我没找到它).
我正在使用一大组(5到2千万)字符串键(平均长度为10个字符),我需要将其存储在内存数据结构中,该结构在恒定时间或接近恒定时间内支持以下操作:
// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)
就吞吐量而言,Java的Hashmap证明是令人满意的,但占用了大量内存.我正在寻找一种内存效率高的解决方案,并且仍然支持良好的吞吐量(与散列相当或几乎一样好).
我不关心插入/删除时间.在我的应用程序中,我将仅执行插入(仅在启动时),并且随后将仅使用contains应用程序生命周期的方法查询数据结构.
我读到HAT-Trie数据结构最接近我的需求.我想知道是否有一个具有实现的库.
其他建议与实现的指针欢迎.
谢谢.
我试图了解HAMT的细节.我已经用Java实现了一个只是为了理解.我熟悉Tries,我认为我得到了HAMT的主要概念.
基本上,
两种类型的节点:
核心价值
Key Value Node:
K key
V value
指数
Index Node:
int bitmap (32 bits)
Node[] table (max length of 32)
(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31)
注意:最后一步(第7步)只有2位. integer==5 bitmap==00001
integer==6 bitmap==0101010101 index==3
我不太了解的部分是碰撞检测和缓解.在链接的论文中,他提到了:
然后将现有密钥插入新的子哈希表中并添加新密钥.每次使用5个比特的散列时,碰撞的概率减少1/32.有时可能会消耗整个32位散列,并且必须计算新的散列以区分这两个密钥.
如果我要计算一个"新"哈希并将该对象存储在该新哈希中; 你怎么能够在结构中查找对象？在进行查找时,它不会生成"初始"哈希而不是"重新计算的哈希".
我肯定错过了什么.....
BTW:HAMT表现相当不错,它在我的测试中位于哈希映射和树图之间.
Data Structure Add time Remove time Sorted add time Sorted remove time Lookup time Size
Java's Hash Map 38.67 ms 18 ms 30 ms 15 …什么是创建一个复杂线索单词列表的,什么是该线索寻找另一组字的复杂性？当我有哈希表时,我应该使用trie进行字符串搜索吗？
我正在制作一个需要数千个快速字符串查找和前缀检查的移动应用程序.为了加快速度,我从单词列表中创建了一个Trie,它有大约180,000个单词.
一切都很棒,但唯一的问题是,构建这个巨大的trie(它有大约400,000个节点)目前在我的手机上大约需要10秒,这真的很慢.
这是构建trie的代码.
public SimpleTrie makeTrie(String file) throws Exception {
String line;
SimpleTrie trie = new SimpleTrie();
BufferedReader br = new BufferedReader(new FileReader(file));
while( (line = br.readLine()) != null) {
trie.insert(line);
}
br.close();
return trie;
}
insert运行的方法O(length of key)
public void insert(String key) {
TrieNode crawler = root;
for(int level=0 ; level < key.length() ; level++) {
int index = key.charAt(level) - 'A';
if(crawler.children[index] == null) {
crawler.children[index] = getNode();
}
crawler = crawler.children[index];
}
crawler.valid …有没有人知道一个真正坚如磐石的C++库用于后缀尝试？除了哑剧者之外？
理想情况下,我想:
并发的一些概念.
良好的缓存行为.
许可证.
支持任意字母表.
我不知道这是否是询问算法的地方.但是,让我们看看我是否得到任何答案...... :)
如果有什么不清楚我很乐意澄清事情.
我刚刚在python中实现了一个Trie.然而,有一点似乎比它应该更复杂(作为一个喜欢简单的人).也许有人遇到过类似的问题？
我的目标是通过在其根中存储子trie的最大公共前缀来最小化节点数.例如,如果我们有stackoverflow,stackbase和stackbased这两个词,那么树看起来像这样:
[s]tack
[o]verflow ______/ \_______ [b]ase
\___ [d]
注意,人们仍然可以想到边缘具有一个字符(子节点的第一个).
查找 -query很容易实现. 插入并不难,但比我想要的更复杂.. :(
我的想法是一个接一个地插入密钥(从一个空的trie开始),首先搜索要插入的密钥k(Find(k)),然后在本地重新排列/拆分节点查找程序停止.结果是4种情况:(设k是我们要插入的键,k'是节点的关键,搜索结束)
似乎每个案例都是独特的,因此意味着对Trie的不同修改.但是:真的那么复杂吗？我错过了什么吗？有更好的方法吗？
谢谢 :)
我已经通过尝试和三元搜索树,我对它们有一些问题.我用Google搜索了答案,但我无法得到具体答案.所以,这是我的问题.
如果尝试空间效率低并且TST结合了最好的BST和尝试,这是否意味着尝试几乎根本不使用？
假设TST用于自动完成,那么对于Google来说,它会如何运作？我的意思是,实际上我们没有一套固定的单词等等,所以如何构建TST的树？
trie数据结构通常是用英语存储字符串的好方法.它通过构建一个树来工作,其中每个边都用字母标记,并且树中标记节点的路径拼出数据结构中的一个字.
这种数据结构在英语中运行良好,因为英语字母中只有"26"字母("合理的"分支因子),这些字符具有连续的ASCII值(因此子指针可以存储在由索引键入的数组中)每个孩子使用的字母),并且有许多带有共同前缀的英语单词(因此结构中有很多冗余).
我是一名母语为英语的人,对其他语言和字母表知之甚少,但似乎很多这些属性并不适用于其他语言.我知道法语,西班牙语,德语和匈牙利语经常使用重音字符,这些字符不会与Unicode空间中的其余字母连续存储.希伯来语和阿拉伯语都有元音标记,通常在每个字母的上方或下方标明.中文使用语标系统,韩语韩文字符由组合在一起的较小字符的三元组组成.
尝试仍然适用于存储在这些语言和字母表中的数据吗？对这类数据使用尝试需要进行哪些更改(如果有)？是否有任何数据结构适用于那些语言和字母表中的字符串,这些字符串特别适合他们但在英语中不会有用或有效？
Struct Node {
Node *N[SIZE];
int value;
};
struct Trie {
Node *root;
Node* findNode(Key *key) {
Node *C = &root;
char u;
while (1) {
u = key->next();
if (u < 0) return C;
// if (C->N[0] == C->N[0]); // this line will speed up execution significantly
C = C->N[u];
if (C == 0) return 0;
}
}
void addNode(Key *key, int value){...};
};
在前缀树(又名Trie)的这个实现中,我发现90%的findNode()执行时间是由单个操作完成的C=C->N[u];
在我试图加速这段代码的过程中,我随机添加了上面剪切的注释行,代码变得快了30%!这是为什么？
UPDATE
这是完整的计划.
#include "stdio.h"
#include "sys/time.h"
long time1000() {
timeval …trie ×10
algorithm ×6
java ×3
c++ ×2
hash ×2
performance ×2
string ×2
autocomplete ×1
bloom-filter ×1
hashtable ×1
nlp ×1
optimization ×1
pointers ×1
python ×1
tree ×1