实现Trie的最佳开放源码内存java应用程序

Question

我想实现Trie的高速内存实现，以创建自动建议/拼写检查器的后端。是否已经有一些基于内存中实现的好的实现，如hazlecast。此外，建议哪种java开源工具最适合此类使用

Answer 1

我会使用像TreeSet这样的普通NavigableSet。它内置并支持范围搜索。

 NavigableSet<String> words = new TreeSet<String>();
 // add words.
 String startsWith = ...
 SortedSet<String> matching = words.subSet(startsWith, startsWith + 'uFFFF');

如果你想要更高效的内存，你可以使用数组。

List<String> words = new ArrayList<String>();
words.add("aa");
words.add("ab");
words.add("ac");
words.add("ba");
Collections.sort(words);
String startsWith = "a";
int first = Collections.binarySearch(words, startsWith);
int last = Collections.binarySearch(words, startsWith.concat("uFFFF"));
if (first < 0) first = ~first;
if (last < 0) last = ~last - 1;
for (int i = first; i <= last; i++) {
    System.out.println(words.get(i));
}