How to create a simple prefix index in Java?

Question

I have big set of urls and I want to implement an autocompletion. I don't like the complexity of the naive approach as it is linear with the set size:

for(String url: urls) if(url.startsWith(input) {doSomething();}

Now I know that in a Hash Set, the function "contains()" works in "O(1)" but there is no "containsPrefix()". Is there a simple way without using a big library like Lucene or coding it myself? I would have no problem doing it but it seems overkill for such a simple problem so I want to know if there is an existing simple solution :-)

From my computer science classes I remember a tree which consists of string fragments but I forget how it was called. It worked like this:

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

P.S.: How do I call the methods that returns all strings that a string is prefix of? Like if a is prefix of b, what is b to a?

what you want to do ? automatically add some text in the beginning of every String ? — Android Killer, Mar 27 '12 at 10:31
I want to know which strings my string is a prefix of so I can give them as autocompletion suggestions. — Konrad Höffner, Mar 27 '12 at 10:47

score 2 · Accepted Answer · answered Mar 27 '12 at 10:36

If you need to efficiently find prefixes of strings, use a Trie, a data structure designed precisely for that purpose:

A trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string

Two links with sample implementations.

Perfect! I used the one from https://forums.oracle.com/forums/thread.jspa?messageID=8787521 and it worked on the first try! — Konrad Höffner, Mar 27 '12 at 11:49

score 1 · Answer 2 · answered Jun 18 '13 at 20:57

1

A great alternative algo is a ternary search tree (more memory efficient) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

here is a trie in java http://algs4.cs.princeton.edu/52trie/TrieST.java.html

answered Jun 18 '13 at 20:57

varun

4,522
33
28

score 1 · Answer 3 · answered Jul 09 '14 at 14:23

The Regexp implementation java.util.regex.Pattern can efficiently handle prefixes:

StringBuilder buffer = new StringBuilder();
for (String prefix : prefixes) {
    if (buffer.length() > 0)
        buffer.append("|");
    buffer.append(prefix);
}
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")");

You can test all prefixes:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find();

Note: for simplicity, prefix strings are not escaped. Regexp characters [, ], \, *, ?, $, ^, (, ), {, } and | have to be prefixed by \.

score 1 · Answer 4 · answered Mar 27 '12 at 10:44

1

Long time ago I put a simple Trie implementation here:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

However this is not a compact Trie, so it creates one node per character, creating a compact one is a bit trickier.

answered Mar 27 '12 at 10:44

mdakin

1,310
11
17

This is great! I don't mind if it's one node per character but I will leave the question open just in case someone has one with multiples. – Konrad Höffner Mar 27 '12 at 10:49
Np, compact version uses about %50 less nodes (At least for Turkish words in a dictionary) This is t he test code, so you can see it in action, I hope there are no bugs :) http://code.google.com/p/triebag/source/browse/trunk/test/triebag/tries/SimpleTrieTest.java – mdakin Mar 27 '12 at 10:52
I tried out your SimpleTrie but it doesn't seem to work for me. First the constructor was not public and after I changed that, the following test returned nothing: `SimpleTrie trie = new SimpleTrie<>(); trie.add("x","x"); trie.add("xy","xy"); Iterator it = trie.getItemsWithPrefix("x"); while(it.hasNext()) System.out.println(it.next());` – Konrad Höffner Mar 27 '12 at 11:43

How to create a simple prefix index in Java?

4 Answers4

Linked