Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have an array of n strings. I want to select all the elements of the array that starts with the given string.

Sorry if that is not clear. I'll give an example.

input = "as"
array = ["abas", "aras", "as", "ask", "asi", "aso", "atas" ]
output =            ["as", "ask", "asi", "aso"]

Which algorithm will I need to do this selection. I need the fastest algorithm that will perform this operation since I'm using it for autoComplete in JavaScript. So the search should be faster than the typing speed of the user.

Edit: Was just thinking about the data I have to pre-process if using a data structure. The data would be dynamic, and I have to perform insert operation that many number of times. I'm fetching data dynamically using AJAX requests.

Edit 2: The array might contain 1 million entries and the search should be made at two places. One on the server side, to select all elements matching the condition. This can be restricted to 10000 entries, and the other on the client side... search size will be those 10000 entries, and this can be restricted to first 250 entries.

Sorry for the late editing of the question.

share|improve this question
1  
Nothing against developing this for fun, but if it's to be used in a production environment I'd recommend checking out some of the existing auto-complete JavaScript libraries such as jQuery –  l0b0 Jun 22 '11 at 11:08
    
I'm developing a library. So I have to code it using pure JavaScript. Searched for pure javascript autocomplete and found that it used the substring function on each element of array that is fetched.. and it was quite slow for faster typing speeds. –  Boopathi Rajaa Jun 22 '11 at 11:15
add comment

3 Answers

up vote 4 down vote accepted

As a pre-processing step turn your list into a trie.

a trie, also called digital tree or prefix tree, is an ordered tree data structure that is used to store a dynamic set or 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. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest...

The term trie comes from re-trie-val...

http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png

share|improve this answer
    
edited the question, take a look at the added part. Will trie do good then too. will insertion be like another forming the tree ?? –  Boopathi Rajaa Jun 22 '11 at 11:12
1  
@Boopathi, building the initial tree is just doing n insertions starting from an empty tree. Each insertion takes O(k) time where k is the length of the string you're inserting. –  Peter Taylor Jun 22 '11 at 12:18
add comment

How big is the set of words you want to search through?

For small sets it might be best to simply order your array and then perform a modified binary search to find the first and last matching elements.

For larger sets you probably want to ditch the array altogether and go for a trie.

Edit:
Given you've updated to say you're expecting a million words (really, a million words? There are only 171,476 words in the Oxford English Dictionary) then a Trie is your best bet. Before you roll your own implementation though, I'd seriously consider some of the freely available autocomplete tools around.

share|improve this answer
    
the array might contain 1 million entries. –  Boopathi Rajaa Jun 22 '11 at 11:13
    
hmmm. my array contains proper nouns... names of persons as well as some common nouns –  Boopathi Rajaa Jun 22 '11 at 11:20
add comment

It's definitely better to use one of the autoComplete algorithms already out there, but if your want to write your own, a trie is the ideal data structure. Insertion and searching both run in constant time i.e O(1), so speed shouldn't be an issue.

Also, this seems similar to what you want: http://webscripts.softpedia.com/script/Forms-and-Controls-C-C/Auto-Complete-Textfield-21580.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.