What data type would be best to store a bag of strings and calculate the frequency of each?

Question

I need to read in a list of words (don't know which words or how many so it needs to be dynamic) and calculate the frequency of each. I was thinking of either doing a balanced BST of records or a hash table of records. Each record storing the word and the number of occurrences. Also a global variable storing the total number of words to calculate the frequency with.
Any better suggestions than mine. I am thinking the hash table would be best but I have never implemented one before.

Is a dynamic array the same as a linked list? If so would a binary search tree not be more efficient?

By calculate the frequency I mean calculate the percentage of each. So I need to store the frequency of each word and the total number of words.

Answer 1

Looks like you're going to need the following:

1) Dynamic memory allocation for each new word read in from the file
2) Dynamic arrays whereby each new word is added to the array along with a counter
3) use the hash or sorting algorithm to sort the array
4) use a search algorithm to locate the word in the arrray

Of course, the volume of information may dictate which method above for #3 and #4 you will use; extremely large amounts of data may dictate a hash method as opposed to a sor/search method.

process as follows:

1) read a word from the file
2) If not in the array, add it and initialize the counter
3) if in the array, increment the counter

to avoid excessive memory allocation calls, you would want to implement memory blocks so that you're allocating chunks at a time rather than once for each word. Again though, this depends on the number of words being processed; larger amounts and more frequent processing would dictate the block allocation approach.

Hope this helps...

Answer 2

Both dynamic array and linked list will work. I would use linked list to calculate frequency faster.

Both hash table and BST are well. But for this case, I will sugest to use BST. You need extra job using Hash table to compare the word "eat", "tea" and "ate", that will slow down a bit.

 

Answer 3

A Hash table will give you the most flexibility if the language you're using supports the data type well.

Answer 4

Hashtable, all the way. I would hash each string, and if it exists in the hashtable, increment the value. If it doesn't exist, add it and set the value to 1. When you're done you'll have a collection of name / value pairs containing (string, count).

Answer 5

I'd use a good, old-fashioned array.