wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Dictionary lookup that works on multiple values
        
(Message started by: Ved on Jul 29^th, 2011, 4:26am)

Title: Dictionary lookup that works on multiple values
Post by Ved on Jul 29^th, 2011, 4:26am

In a Contact book that has "Name" and "Phone number", I want to implement suggestion based on the entered value on both name as well as phone number.
E.g: contact = "ABC", 123-234-345
contact = "ABD", 134-345-456

So when I type either "A" or "1" it should suggest both the contacts above. In a standard TRIE implementation, we usually use just one field. Is there a way to use both name and number as the TRIE fields ?

Title: Re: Dictionary lookup that works on multiple value
Post by towr on Jul 29^th, 2011, 8:35am

The answer is probably yes, but I'd just use two tries.

Title: Re: Dictionary lookup that works on multiple value
Post by Ved on Jul 29^th, 2011, 10:05am

Thanks Towr. Any suggested approach, reading etc?

Title: Re: Dictionary lookup that works on multiple value
Post by towr on Jul 29^th, 2011, 12:00pm

What programming language are you using? If it has a standard trie library, it's probably easiest to use that.
Abstractly a trie is just a way to store a key-value pair, so you'd have trie_alpha['ABC'] = contact1, trie_alpha['ABD'] = constact2, trie_num['123-234-345'] = contact1, trie_num['123-345-456'] = contact2. So you could even input the same contact under both fields in the same trie if you prefer, but you may want the trie to work slightly differently for names and numbers (such as ignoring -'s when inputting numbers, and perhaps treat it like space in names)
I suppose there's also the question of how you want the suggestions ordered, if you input a number, should suggestions be ordered by number or name? (Or perhaps frequency of use.)

Title: Re: Dictionary lookup that works on multiple value
Post by Ved on Jul 30^th, 2011, 10:58am

For this discussion, lets say we do not have a TRIE library in our language.
In our example lets say I have contact = "GMC","234-456-456"
My problem is somewhat tricky in that if I type "A" or "1" - both contact appear but if I type "2" or "G" only third contact appears. In this case we will have to keep two TRIEs one for name and the other for the phone number. Is that correct ? or is there any optimization