我想在内存中实现 Trie 的高速实现,以创建自动建议/拼写检查器的后端。 是否已经有一些基于内存实现的良好实现,如 hazlecast。 还有哪种 Java 开源工具最适合这些用途
最佳答案
我会使用像 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));
}
关于java - 用于实现 Trie 的最佳开源内存 Java 应用程序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8959578/