What about a ternary Search tree?
On 4 March 2010 16:21, Umer Farooq <[email protected]> wrote:
> 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
> <[email protected]>wrote:
>
>> trie data structure
>>
>>
>> On Sat, Feb 27, 2010 at 1:13 PM, subbu bvss <[email protected]> wrote:
>>
>>> i think u have to use t9 algorithm.. (tree type data structure)...
>>>
>>>
>>> On Sat, Feb 27, 2010 at 6:32 PM, abhijith reddy <
>>> [email protected]> 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, <[email protected]> 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 <[email protected]> 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 [email protected].
>>>>>> To unsubscribe from this group, send email to
>>>>>> [email protected]<algogeeks%[email protected]>
>>>>>> .
>>>>>> 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 [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected]<algogeeks%[email protected]>
>>>>> .
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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: [email protected]
>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
