Best Open Source Java Application for Implementing Trie

Question

I want to implement a high-speed implementation of Trie memory to create a backend for automatic query / spelling. Is there some good implementation based on memory implementations like hazlecast. Also, which open source Java tool is best suited for such use.

Answer 1

I would use a simple NavigableSet like TreeSet. It is built-in and supports range searching.

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

If you want something more memory efficient, you can use an array.

 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)); }