我正在使用一些Java代码来执行快速前缀查找,使用java.util.TreeSet,我可以使用scala的TreeSet吗？还是另一种解决方案？
/** A class that uses a TreeSet to do fast prefix matching
*/
class PrefixMatcher {
private val _set = new java.util.TreeSet[String]
def add(s: String) = _set.add(s)
def findMatches(prefix: String): List[String] = {
val matches = new ListBuffer[String]
val tailSet = _set.tailSet(prefix)
for ( tail <- tailSet.toArray ) {
val tailString = tail.asInstanceOf[String]
if ( tailString.startsWith(prefix) )
matches += tailString
else
return matches.toList
}
matches.toList
}
}
我正在开发一个Trie数据结构,其中每个节点代表一个单词.所以的话st,stack,stackoverflow并overflow会安排为
root
--st
---stack
-----stackoverflow
--overflow
我的Trie在HashTable内部使用,因此所有节点查找将花费恒定时间.以下是我将算法插入到trie中的算法.
key并检查单词是否存在.这样做直到我们得到一个节点,其中新值可以作为子节点添加.如果未找到任何节点,则将添加到根节点下.我不确定这是实现trie的正确方法.欢迎任何建议或改进.
使用的语言:C++
我研究过Tries和Suffix Trees,并希望实现相同的功能.请分享一些链接,我可以从中了解实施的结构和基本概念.
任何好的例子,如果包括在内,都会是一个加分.
在C中实施
我有一个很大的域名列表(大约六千个),我希望看到哪些词对于我们的投资组合的粗略概述是最高的.
我遇到的问题是列表被格式化为域名,例如:
examplecartrading.com
examplepensions.co.uk
exampledeals.org
examplesummeroffers.com
5996
只运行字数会带来垃圾.所以我想最简单的方法是在整个单词之间插入空格然后运行单词计数.
为了我的理智,我宁愿编写这个.
我知道(非常)小python 2.7但是我对接近这个的任何建议持开放态度,代码的例子真的会有所帮助.我被告知使用简单的字符串trie数据结构将是实现此目的的最简单方法,但我不知道如何在python中实现它.
我在Tries,hashing,Map(stl)和BST上阅读了一些博客和教程.我很困惑哪一个更好用,哪里.我知道在它们之间做出这样的区别是无稽之谈,因为它们都是依赖于实现的.请您告诉我更具体的内容,请不要忘记提及复杂性(最差,平均和最佳情况).
提前致谢...
hash trie time-complexity binary-search-tree data-structures
我在内存中有一个T9字典(trie/hash_map).该词典包含词级对,因此当从词典中选取一个词时,其等级增加,并且词等级对在词列表中上升.
假设有一种方法可以从字典中选择一个单词.该方法也做了一些单词评级例程.
在输入中,我有一串数字(1-9,'*'来改变单词和''),这些是在电话上按下的.
问题:
UPD:
完整问题文本(问题D)
从这个问题来看,似乎有一个Patricia Trie实现,但它没有maven repo.在任何情况下,我都找不到Gauva/Google Collections中的trie.有没有人知道java中的任何Trie实现库,它有一个maven repo？
注意:它基本上是为前端的自动完成功能创建后端.任何其他有助于实现这一目标的东西都应该足够好.
由于每个整数都可以表示为一系列长度的位,因此您似乎可以按以下方式对一堆整数进行排序:
这种排序算法是否曾在实践中使用过？
我今天正在解决一个问题.但我被困了.我知道trie是如何工作的,但问题是我知道如何使用静态数组和类来实现它.今天在网上冲浪我读到有一种方法可以使用stl :: map实现尝试.我今天试过,但我还是不知道如何在int上插入元素.这个结构.
编辑1:我正在尝试解决这个问题:spoj.com/problems/TAP2012D我想知道如何使用edit2将单词添加到trie中:我知道地图是如何工作的,我只是不知道如何使用地图作品.我想要一个了解尝试的人.
这是我到目前为止所做的
const int ALPH_SIZE = 26;
using namespace std;
struct trie{
map<char,int> M;
int x,y;
trie();
};
trie T[1000000];
trie::trie()
{
x=y=0;
}
int maximo;
void addtrie(string palabra)
{
int tam=palabra.size();
int pos=0;
for(int i=0;i<tam;i++)
{
if(T[pos].M.find(palabra[i])==T[pos].M.end())
{
T[pos].M[palabra[i]]=new trie();
T[pos].M[palabra[i]]=
}
}
}
Python似乎是从类方法的封闭范围推断出一些kwargs,我不确定为什么.我正在实施一个Trie:
class TrieNode(object):
def __init__(self, value = None, children = {}):
self.children = children
self.value = value
def __getitem__(self, key):
if key == "":
return self.value
return self.children[key[0]].__getitem__(key[1:])
def __setitem__(self, key, value):
if key == "":
self.value = value
return
if key[0] not in self.children:
self.children[key[0]] = TrieNode()
self.children[key[0]].__setitem__(key[1:], value)
在倒数第二行,我创建了一个新的TrieNode,可能是一个空的儿童字典.但是,当我检查结果数据结构时,树中的所有TrieNode都使用相同的子字典.即,如果我们这样做:
>>>test = TrieNode()
>>>test["pickle"] = 5
>>>test.children.keys()
['c', 'e', 'i', 'k', 'l', 'p']
测试的子项应该只包含指向新TrieNode的"p".另一方面,如果我们进入该代码的倒数第二行并将其替换为:
self.children[key[0]] = TrieNode(children = {})
然后它按预期工作.不知怎的,然后,self.children字典被隐式地作为一个kwarg传递给TrieNode(),但为什么呢？