我有一个我用词典创建的特里.我想用它来进行拼写检查(并在字典中建议最接近的匹配,也许是对于给定数量的编辑x).我想我会在目标单词和字典中的单词之间使用levenshtein距离,但有没有一种智能的方法可以遍历trie而不会分别在每个单词上运行编辑距离逻辑？我该如何进行遍历和编辑距离匹配？
例如,如果我有单词MAN,MANE,我应该能够在MANE中重用MAN上的编辑距离计算.否则Trie不会用于任何目的
我期待实现VBA 特里路技术算法,该算法能够处理的时间(小于15-20秒)相对较短量大幅英语词汇(〜50,000字).由于我是一名C++程序员(这是我第一次做任何实质性的VBA工作),我构建了一个快速概念验证程序,能够在大约半秒钟内完成计算机上的任务.然而,当测试VBA端口的时候,它花了差不多两分钟来做同样的事情 - 为了我的目的,这是一个不可接受的长时间.VBA代码如下:
节点类模块:
Public letter As String
Public next_nodes As New Collection
Public is_word As Boolean
主要模块:
Dim tree As Node
Sub build_trie()
Set tree = New Node
Dim file, a, b, c As Integer
Dim current As Node
Dim wordlist As Collection
Set wordlist = New Collection
file = FreeFile
Open "C:\corncob_caps.txt" For Input As file
Do While Not EOF(file)
Dim line As String
Line Input #file, line
wordlist.add line
Loop
For a = 1 To …我试图了解如何实现trie等不可变性,与JS中的不变性相关.我理解应该如何进行重要的结构共享.
我的问题是你有一个图形结构,如下所示:
a -- b
|
c
|
d -- h
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
那么你添加一个x系统.我将尝试两种不同的方式:
a -- b
|
c
|
d -- h -- x
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
那个只是作为叶子节点添加的.
a -- b
|
c
|
d -- h
|
x
|
e -- i -- …我必须实现一个自制的Trie,我被困在Iterator部分.我似乎无法弄清楚trie的增量方法.
我希望有人能帮助我解决问题.
这是Iterator的代码:
template <typename T> class Trie<T>::IteratorPrefixe{
friend class Trie<T>;
public:
IteratorPrefixe() : tree(NULL), currentNode(NULL), currentKey("") {};
pair<string, T*> operator*() {return make_pair(currentKey, currentNode -> element);} ;
IteratorPrefixe operator++()throw(runtime_error);
void operator=(IteratorPrefixe iter) {tree = iter.tree; currentNode = iter.currentNode; currentKey = iter.currentKey;};
bool operator==(IteratorPrefixe iter) {return tree == iter.tree && currentNode == iter.currentNode;};
bool operator!=(IteratorPrefixe iter) {return tree != iter.tree || currentNode != iter.currentNode;};
private:
Trie<T> * tree;
Trie<T> * currentNode;
string currentKey;
};
这是我的特里:
template <typename T> class 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:如果从上面的论文编写时起,更快的缓存意识数据结构非常适合字符串演变,请指向我的论文或示例源代码.
我正在研究一个自动完成脚本,正在考虑使用trie.我的问题是我希望返回匹配的所有内容.因此,例如我输入字母,r我希望r返回所有条目.然后所有条目都以re等等开头.这对于trie是可行的,它将如何工作.此外,如果有更好的方式,我愿意接受建议.我问的原因是它似乎很复杂,并且需要进行大量处理才能将所有节点都归结为r分支.
是的,我可能正在重新发明轮子,但我想了解它是如何工作的.
我需要有关任何标准python包的信息,这些包可用于URL上的"最长前缀匹配".我已经通过两个标准包不见了http://packages.python.org/PyTrie/#pytrie.StringTrie&"http://pypi.python.org/pypi/trie/0.1.1",但他们似乎并没有对URL的最长前缀匹配任务有用.
例如,如果我的设置包含以下网址1-> http://www.google.com/mail,2-> http://www.google.com/document,3-> http://www.facebook.com等等..
现在,如果我搜索"http://www.google.com/doc",则应返回2并搜索"http://www.face"应返回3.
我想确认是否有任何标准的python包可以帮助我这样做,或者我应该实现Trie的前缀匹配.
我不是在寻找一种正则表达式的解决方案,因为随着URL数量的增加它不可扩展.
非常感谢.
我的联系人存储在手机中.让我们说我的联系人
Ram
Hello
Hi
Feat
Eat
At
当我输入信件时,'A'我应该得到所有匹配的联系人说"Ram, Feat, Eat, At".
现在我再打一个字母T.现在我的总字符串"AT"现在我的程序应该重用以前搜索的结果"A".现在它应该归还给我"Feat, Eat, At"
为此设计和开发一个程序.
这是三星移动开发的面试问题
我试着解决Trie data structures.无法获得重复使用已搜索字符串结果的良好解决方案.我也尝试过用字典数据结构的解决方案,解决方案也有同样的缺点Trie.
问题是我如何搜索键入的每个字母的联系人重新使用先前搜索的字符串的搜索结果？应该使用什么数据结构和算法来有效地解决问题.
我不是要求节目.所以编程语言对我来说并不重要.
状态机似乎是一个很好的解决方案.有没有人有建议？
对于百万联系人来说,解决方案应足够快
我正在使用这个marisa trie库的自定义Cython包装器作为键值多图.
我的trie条目看起来像key 0xff data1 0xff data2映射key到元组(data1, data2).data1是一个可变长度的字符串,但data2始终是一个4字节的无符号整数.这0xff是一个分隔符字节.
从理论角度来看,我知道trie不是最优化的数据结构,但是各种实际考虑因素使其成为最佳选择.
在这个用例中,我有大约1000万到2000万个密钥,每个密钥平均有10个数据点.data2对于许多条目来说是多余的(在某些情况下,data2给定密钥的所有数据点总是相同的),所以我想到了最频繁的data2输入并("", base_data2)为每个密钥添加了一个数据点.
由于MARISA trie,据我所知,没有后缀压缩,并且对于给定的密钥,每个data1都是唯一的,我假设这将为使用冗余密钥的每个数据元组节省4个字节(加上添加一个4字节的"值") "为每把钥匙).重建了trie后,我检查了冗余数据不再存储.我预计序列化和内存大小都会大幅减少,但实际上磁盘上的trie从566MB增加到557MB(并且加载的trie的RAM使用量也有类似的减少).
由此我得出结论,没有后缀压缩我一定是错的.我现在用多余的data2数字存储条目key 0xff data1 0xff,所以为了测试这个理论,我删除了尾随0xff并调整了使用trie处理的代码.新的trie从557MB下降到535MB.
因此,删除单个冗余尾随字节比删除相同数量的4字节序列提高了2 倍,因此后缀压缩理论是错误的,或者它以某种非常复杂的方式实现.
我剩下的理论是,在("", base_data2)trie中更高点添加条目会以某种可怕的方式抛出压缩,但是当我从中删除多于下来时,它应该只增加4个字节.线索.
我对修复并不乐观,但我非常想知道为什么我会看到这种行为!感谢您的关注.