import java.util.*; import java.util.stream.Collectors; /** * The TextTrie tree can perform fast prefix matching. By traversing the tree based on the characters in * the prefix being searched, it is possible to find all strings in the Trie that have the given prefix. */ public interface TextTrie { /** * Try to find any strings which start with the given prefix. Matching strings are always in lexicographical order. * * @param prefix to look for * @param limit maximum number of found strings * @return collection of words with the same substring */ Collection startsWith(String prefix, int limit); /** * Checks if a string exists in this tree. * @param string to check * @return true if word is in this tree */ boolean contains(String string); /** * Inserts a word into the tree. Duplicate words will be ignored. * * @param string word to be inserted * @return true if the word was inserted false if it already existed */ boolean insert(String string); /** * Deletes a word from the tree. * * @param string to be deleted * @return true if word is successfully deleted false if word was not in the tree */ boolean delete(String string); /** * The number of nodes in this tree. * @return number of nodes */ int size(); /** * The number of complete words in this tree. * * @return number of complete words */ int completeWords(); /** * A detailed string representation of the structure of this tree. * * @return detailed string */ String prettyString(); } public class NaiveTextTrieDemo { public static void main(String[] args) { final Collection list = List.of("apple", "apricot", "avocado", "ant", "app", "ants", "apps", "apis", "analyse", "alms", "alarm", "alarms"); final TextTrie trie = new NaiveTextTrie(); list.forEach(trie::insert); System.out.println(trie); System.out.println(trie.prettyString()); startsWithDemo(trie, "a"); startsWithDemo(trie, "ap"); startsWithDemo(trie, "app"); startsWithDemo(trie, "apple"); deleteDemo(trie, "appi"); deleteDemo(trie, "app"); startsWithDemo(trie, "app"); deleteDemo(trie, "api"); startsWithDemo(trie, "a"); System.out.println(trie.prettyString()); list.forEach(s -> deleteDemo(trie, s)); System.out.println(trie); System.out.println(trie.prettyString()); startsWithDemo(trie, "a"); System.out.println("size: " + trie.size()); System.out.println("words: " + trie.completeWords()); } private static void deleteDemo(TextTrie trie, String toDelete) { final String msg = trie.delete(toDelete) ? "true" : "false, reason: not present in trie"; System.out.printf("deleting '%s' -> deleted:%s%n", toDelete, msg); } private static void startsWithDemo(TextTrie trie, String prefix) { System.out.printf("looking up '%s' %s%n", prefix, trie.startsWith(prefix, 4)); } } class NaiveTextTrie implements TextTrie { private static final String LINE_SEPARATOR = System.lineSeparator(); private final NaiveTrieNode root; private int completeWords; private int size; public NaiveTextTrie() { this.root = new NaiveTrieNode(); } @Override public Collection startsWith(String substring, int limit) { final List leaves = new ArrayList<>(); doSearch(this.root, substring, 0, leaves, limit); return getWords(leaves); } @Override public boolean insert(String string) { if (string == null || string.isEmpty()) return false; final NaiveTrieNode inserted = insert(string, this.root, 0); if (inserted.isWord) { // was inserted before return false; } this.completeWords++; inserted.setIsWord(true); return true; } @Override public boolean delete(String string) { return delete(this.root, string, 0); } @Override public int size() { return size; } @Override public int completeWords() { return completeWords; } @Override public String toString() { return startsWith("", completeWords).toString(); } @Override public boolean contains(String string) { final List result = new ArrayList<>(); doSearch(this.root, string, 0, result, 1); return !result.isEmpty(); } @Override public String prettyString() { if (this.root.children.isEmpty()) { return "empty trie"; } else { final StringBuilder sb = new StringBuilder("NaiveTrie total nodes: ") .append(size).append(LINE_SEPARATOR) .append("total complete words:") .append(completeWords).append(LINE_SEPARATOR); visitAllNodes(0, this.root, ">>>", sb); return sb.toString(); } } private void visitAllNodes(int size, NaiveTrieNode node, String prefix, StringBuilder visitor) { final String pointer = "├─► "; final String hookPointer = "└─► "; final String pointerConnection = "│"; // depth-first search // visit current if (node != this.root) { if (size > 1) visitor.append(prefix).append(pointer); else { visitor.append(prefix).append(hookPointer); } visitor.append((char) node.c); } // if current is word append the whole word to the current node if (node.isWord) { NaiveTrieNode c = node; visitor.append(": ("); final int l = visitor.length(); while (c != this.root) { visitor.insert(l, (char) c.c); c = c.parent; } visitor.append(")"); } visitor.append(LINE_SEPARATOR); final String nextPrefix; if (node.parent != null && size > 1) { nextPrefix = prefix + pointerConnection + " ".repeat(pointer.length()); } else if (node != this.root) { nextPrefix = prefix + " ".repeat(pointer.length()); } else { nextPrefix = prefix; } // visit children int s = node.children.size(); for (NaiveTrieNode child : node.children.values()) { visitAllNodes(s--, child, nextPrefix, visitor); } } private NaiveTrieNode insert(String word, NaiveTrieNode root, int i) { if (i == word.length()) { return root; } else { final int c = word.charAt(i); NaiveTrieNode child = root.children.get(c); if (child == null) { child = new NaiveTrieNode(c, root); size++; root.children.put(c, child); } return insert(word, child, i + 1); } } private Collection getWords(List leaves) { return leaves.stream().map(l -> { final StringBuilder sb = new StringBuilder(); while (l != this.root) { sb.insert(0, (char) l.c); l = l.parent; } return sb.toString(); }).collect(Collectors.toList()); } private void doSearch(NaiveTrieNode n, String needle, int i, Collection result, int resultLimit) { if (n == null || result.size() >= resultLimit) { return; } if (n.isWord && i >= needle.length()) { result.add(n); } if (i >= needle.length()) { for (NaiveTrieNode c : n.children.values()) { doSearch(c, needle, i + 1, result, resultLimit); } } else { final int c = needle.charAt(i); doSearch(n.children.get(c), needle, i + 1, result, resultLimit); } } private boolean delete(NaiveTrieNode n, String word, int i) { if (n == null || i > word.length()) { return false; } if (n.isWord && i == word.length()) { completeWords--; if (!n.children.isEmpty()) { n.setIsWord(false); } else { removeNode(n.parent, n.c); } return true; } else if (i < word.length()) { final int c = word.charAt(i); return delete(n.children.get(c), word, i + 1); } else { return false; } } private void removeNode(NaiveTrieNode parent, int c) { if (parent != null) { parent.children.remove(c); if (parent.children.isEmpty()) { removeNode(parent.parent, parent.c); } size--; } } private static class NaiveTrieNode { private final Map children; private boolean isWord; private int c; private int distanceFromRoot; private NaiveTrieNode parent; NaiveTrieNode() { children = new TreeMap<>(); this.distanceFromRoot = 1; } NaiveTrieNode(int c, NaiveTrieNode parent) { this(); this.c = c; this.parent = parent; this.distanceFromRoot = parent.distanceFromRoot + 1; } void setIsWord(boolean isWord) { this.isWord = isWord; } } }

NaiveTrieTree