Java中有Trie吗？ [英] Is there a Trie in Java?

问题描述

可能重复：

我在哪里可以找到基于Trie的标准地图实现？

我想在Java中使用Trie，有没有我可以使用的实现？ （我试过寻找一个，但我没有找到它。）

解决方案

核心Java中没有trie数据结构这可能是因为尝试通常用于存储字符串，而Java数据结构更通用，通常持有任何对象

code>（定义相等和散列操作），尽管它们有时仅限于 Comparable 对象（定义顺序）。虽然 CharSequence 适用于字符串，但我认为你可以用 Iterable做一些事情，而且符号序列没有常见的抽象。 code>用于其他类型的符号。

这是另一个要考虑的问题：当尝试在Java中实现传统的trie时，你很快就会遇到这样的事实： Java支持Unicode。要获得任何类型的空间效率，必须将trie中的字符串限制为符号的某个子集，或者放弃将子节点存储在由符号索引的数组中的传统方法。这可能是为什么尝试不被认为足以包含在核心库中的另一个原因，以及如果您实现自己的或使用第三方库需要注意的事项。

Possible Duplicate:
Where do I find a standard Trie based map implementation in Java?

I want to use Trie in Java, is there an implementation I can use ? (I tried looking for one but I didn't found it).

解决方案

There is no trie data structure in the core Java libraries.

This may be because tries are usually designed to store character strings, while Java data structures are more general, usually holding any Object (defining equality and a hash operation), though they are sometimes limited to Comparable objects (defining an order). There's no common abstraction for "a sequence of symbols," although CharSequence is suitable for character strings, and I suppose you could do something with Iterable for other types of symbols.

Here's another point to consider: when trying to implement a conventional trie in Java, you are quickly confronted with the fact that Java supports Unicode. To have any sort of space efficiency, you have to restrict the strings in your trie to some subset of symbols, or abandon the conventional approach of storing child nodes in an array indexed by symbol. This might be another reason why tries are not considered general-purpose enough for inclusion in the core library, and something to watch out for if you implement your own or use a third-party library.

这篇关于Java中有Trie吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！