问题标签 [ternary-search-tree]

Hello fellow stackoverflowers!

I have a word list of 200.000 string entries, average string length is around 30 characters. This list of words are the key and to each key i have a domain object. I would like to find the domain objects in this collection by only knowing a part of the key. I.E. the search string "kov" would for example match the key "stackoverflow".

Currently I am using a Ternary Search Tree (TST), which usually will find the items within 100 milliseconds. This is however too slow for my requirements. The TST implementation could be improved with some minor optimizations and I could try to balance the tree. But i figured that these things would not give me the 5x - 10x speed improvement I am aiming at. I am assuming that the reason for being so slow is that i basically have to visit most nodes in the tree.

Any ideas on how to improve the speed of the algorithm? Are there any other algorithms that I should be looking at?

Thanks in advance, Oskar

我一直在使用三元搜索树作为实现自动完成下拉组合框的数据结构。这意味着，当用户键入“fo”时，将显示下拉组合框

foo 食品 足球

问题是，我目前使用的三元搜索树是区分大小写的。我的实现如下。它已被现实世界使用了大约 1++ 年。因此，我认为它非常可靠。

我的三元搜索树代码

但是，我正在寻找不区分大小写的三元搜索树，这意味着，当我输入“fo”时，下拉组合框将显示我

foo 食物 足球

以下是 TST 的一些关键接口，我希望新的不区分大小写的 TST 也可能有类似的接口。

使用示例如下。TSTSearchEngine 使用 TernarySearchTree 作为核心骨干。

三元搜索树的示例用法

我需要知道三叉树是否比哈希表更好。

我在回答另一个问题时遇到了这个问题，有人说三叉树通常比哈希表快。我发现这很难相信，所以我决定研究一下。

普林斯顿的这个网站似乎是这种信念的来源。我查看了描述为 O(log n + k) 的算法，其中 n 是存储的单词数，k 是密钥的长度。

在我看来，这可能更快的唯一方法是如果您经常搜索尚未存储的元素。另一件困扰我的事情是，不连续爬取 trie 往往会导致您点击已换出的页面，但这是否是主要影响只能通过基准测试才能看到。

现在我知道它们可能各有利弊，如果是这样，我想知道它们是什么。基准测试也很有帮助。

如何“平衡”三元搜索树？大多数 tst 实现不解决平衡问题，但建议以最佳顺序插入（我无法控制。）

我正在尝试为学校项目构建三元搜索树。据我所知，我的代码看起来还不错。
但是，当我使用 malloc 时，原始根函数的叶节点没有被初始化。因此，除了第一个字符串比较（无论根的字符串是什么）之外的每个字符串比较都会为空（不是 null，而是“”）。我没有将任何指针作为函数参数传递，所以我无法弄清楚问题所在。请帮忙！
我怀疑问题出在这部分代码中。我真的绞尽脑汁搜索并无法弄清楚我的问题是什么。
如果您愿意，可以使用更多代码。

我已经检查并且 root->right 指向一个完全不同的位置，而不是第一次通过时 current->right 。那是我真正的问题。我认为这一定是声明中的错误之类的，但我就是想不通。

当我使用字符串添加单词序列时，add()在段内打印 if(t==NULL)但树没有形成，即节点没有链接。

根据我对三元搜索树的理解，它们在可以搜索和找到的项目中是反向确定的（不确定正确的术语）。我的意思是，如果你为cat、bike、axis创建一个三元树，然后给某人三元树，他应该能够从中扣除这三个词。

它是否正确？

我在问，因为我有一个三元树结构，其中包含诸如 ISMAP、SELECTED 和 COMPACT 之类的词（实际上是 HTML 4 的属性），我想知道是否可以获得存储在该树中的项目的完整列表（原始文档离开了）。结构如下所示：

我想知道是否可以修改三元搜索树以检查该单词是否存在并找到以该单词开头的所有单词（或以该单词结尾？）？例如do=>dog dogs等。

从这个站点是一个示例代码。首先将所有单词加载到三叉树中，然后我们可以使用方法检查单词是否存在。

这让我在我脑海中浮现出巨大的:(
任何得到那个词的方法都可以。但是我在那个级别的算法上很弱。
我希望我不会重复任何关于这个的问题。任何建议我都会感激.

我目前正在研究预测文本短信系统。我想使用 TST 数据结构和二元语法来实现它（根据当前键序列 12 键盘预测下一个可能的单词）。
目前我有一个语料库，并使用可用的应用程序来提出字典、二元语法和频率。目前有以下几个问题：

1. 我可以在这种情况下找到 J2ME TST 实现或合适的 Trie 吗？（对可用的 TST trie 进行更详细的解释会很棒）
2. 此项目方法的一般指导

注意：我看过类似的 Trie 实现，但仍然无法找到前进的方向

我想从“三元搜索树”库（sourceforge和http://code.google.com/p/ternary-search-tree/）中修改递归函数。默认行为是在三元搜索树中搜索与指定通配符字符串匹配的所有字符串。即如果我搜索“KE*”，在树中拥有“KEY”、“KE1”、“KE2”会找到所有条目。但我需要相反的行为 - 在三元搜索树（包含通配符）中搜索与指定字符串匹配的所有条目。即如果我搜索“KEY”，在树中有“KE*”、“KEY”、“K*”应该会找到所有条目。

树/节点定义如下：

以及具有默认行为的函数：

pmVectorPtr 是一个指向 int 向量的指针，函数 get 以根元素和 searchkey 作为参数调用。我已经尝试过适应它，但还无法理解它。我自己的代码：

我已经广泛使用调试器对此进行了编码，据我所知，它“似乎”可以工作（即使通配符位于字符串的开头或中间）。但是，如果我在树中添加示例：“K*”和“Ke*”，它只会为“Key”找到一个解决方案（在本例中为 Ke*）。如果我从树中删除“Ke*”，它会为“Key”的搜索查询找到“K*”。我还是不明白为什么。

有什么想法吗？

附录（我的测试用例）：