I can't get how will u manipulate the trie DS. u'll have to look back and
see if the word already exists in the list. this will be an extra overhead.
I have thought of another algorithm. Here is an abstract explanation:
The node used will be like this
struct Word {
.........char *_word;
.........int _freq;
.........Word *Next;
}
class Category {
........Word *List;
..... bool addWord(char *word); // if the word exists in the list, then
increment the freqency, else add the word
........bool doesExist(word);
}
public void main (String[] args)
{
.... Category _cat[26];
.....while (!EOF()) {
............char *c = getNextWord();
............_cat[c[0].toInt()-97].addWord(c);
}
Categorize the words into 26 categories depending on the initial character;
Depending on the initial character, traverse the list of corresponding
category
If the word exists, then increment the counter of that word
else add the word in the list of that category.
On Thu, Mar 4, 2010 at 6:51 AM, ankur aggarwal <ankur.mast....@gmail.com>wrote:
> trie data structure
>
>
> On Sat, Feb 27, 2010 at 1:13 PM, subbu bvss <bvss.su...@gmail.com> wrote:
>
>> i think u have to use t9 algorithm.. (tree type data structure)...
>>
>>
>> On Sat, Feb 27, 2010 at 6:32 PM, abhijith reddy <abhijith200...@gmail.com
>> > wrote:
>>
>>> You can use a TRIE .. Structure can be something like this
>>>
>>> struct trie
>>> {
>>> int count; // no of occurences
>>> char *child[SIZE];
>>> };
>>>
>>> when ever u insert ( it will take just O(length) time) .. just increment
>>> count by 1
>>>
>>> For each query (also O(length) time) the no of occurrences of the word
>>> will be count of the last character
>>>
>>> Hope it helps
>>>
>>>
>>>
>>> On Sat, Feb 27, 2010 at 5:35 PM, <piyushgoe...@gmail.com> wrote:
>>>
>>>> Maintain a hash of word to freq. Keep adding words and incrementing
>>>> their frequencies while reading the documents
>>>>
>>>>
>>>> Pigol
>>>>
>>>>
>>>> On Feb 27, 2010, at 5:10 PM, vijay <auvija...@gmail.com> wrote:
>>>>
>>>> You have to count the occurances of all words in a document. You are
>>>>> given a method chat * GetNextWord, that returns the next word from the
>>>>> document.
>>>>> - Which datastructure can be userd to achieve this
>>>>> -
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>> .
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> With Regards
>
> Ankur Aggarwal
> Research internee
> Optical Zeitgeist Laboratory
> Institut National de la Recherche Scientifique (INRS) - ÉMT
> 800, de la Gauchetière Ouest, bureau 6900
> Montréal, QC, H5A 1K6
> CANADA
>
> Ph: +1 514 966-2661
> E-mail: ankur.1...@gmail.com
> Web: www.zeitgeistlab.ca
> Group Member Page: http://zeitgeistlab.ca/doc/groupmembers.html
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
