Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
628 views
in Technique[技术] by (71.8m points)

indexing - How to create a simple prefix index in Java?

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...