CODEWITHSUNDEEP
arraysalgorithmsearchtextindexing
alphablender
alphablender

Reputation: 2238

fast indexing for slow cpu?

I have a large document that I want to build an index of for word searching. (I hear this type of array is really called a concordances). Currently it takes about 10 minutes. Is there a fast way to do it? Currently I iterate through each paragraph and if I find a word I have not encountered before, I add it too my word array, along with the paragraph number in a subsidiary array, any time I encounter that same word again, I add the paragraph number to the index. :

associativeArray={chocolate:[10,30,35,200,50001],parsnips:[5,500,100403]}

This takes forever, well, 5 minutes or so. I tried converting this array to a string, but it is so large it won't work to include in a program file, even after removing stop words, and would take a while to convert back to an array anyway.

Is there a faster way to build a text index other than linear brute force? I'm not looking for a product that will do the index for me, just the fastest known algorithm. The index should be accurate, not fuzzy, and there will be no need for partial searches.

Upvotes: 0

Views: 72

Answers (4)

Nas Banov
Nas Banov

Reputation: 29019

There are a few things unclear in your question, like what do you mean in "I tried converting this array to a string, but it is so large it won't work to include in a program file, even after removing stop words, and would take a while to convert back to an array anyway."?! What array, is your input in form of array of paragraphs or do you mean the concordance entries per word, or what.

It is also unclear why your program is so slow, probably there is something inefficient there - i suspect is you check "if I find a word I have not encountered before" - i presume you look up the word in the dictionary and then iterate through the array of occurrences to see if paragraph# is there? That's slow linear search, you will be better served to use a set there (think hash/dictionary where you care only about the keys), kind of

concord = {
    'chocolate': {10:1, 30:1, 35:1, 200:1, 50001:1}, 
    'parsnips': {5:1, 500:1, 100403:1}  
}

and your check then becomes if paraNum in concord[word]: ... instead of a loop or binary search.

PS. actually assuming you are keeping list of occurrences in array AND scanning the text from 1st to last paragraph, that means arrays will form sorted, so you only need to check the very last element there if word in concord and paraNum == concord[word][-1]:. (Examples are in pseudocode/python but you can translate to your language)

Upvotes: 0

Paddy3118
Paddy3118

Reputation: 4772

Well, apart from going along with MrSmith42's suggestion of using the built in HashMap, I also wonder how much time you are spending tracking the paragraph number?

Would it be faster to change things to track line numbers instead? (Especially if you are reading the input line-by-line).

Upvotes: 1

Save
Save

Reputation: 11938

I think the best idea is to build a trie, adding a word at the time of your text, and having for each leaf a List of location you can find that word.

This would not only save you some space, since storing word with similar prefixes will require way less space, but the search will be faster too. Search time is O(M) where M is the maximum string length, and insert time is O(n) where n is the length of the key you are inserting.

Since the obvious alternative is an hash table, here you can find some more comparison between the two.

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10151

I would use a HashMap<String, List<Occurrency>> This way you can check if a word is already in yoz index in about O(1).

At the end, when you have all word collected and want to search them very often, you might try to find a hash-function that has no or nearly no collisions. This way you can guarantee O(1) time for the search (or nearly O(1) if you have still some collisions).

Upvotes: 1

Related Questions