CODEWITHSUNDEEP
algorithmsearchaddressbookprefix-treepatricia-trie
Mapo
Mapo

Reputation: 115

Address book and trie structure

I'have a question for you. I have to implement a business address book that contains 30000 names. All the names contains firstname and lastname. I have to implement an autocomplete textbox that search not only typing firstname but also by lastname. Searching on google I've seen that this problem is solved using a patricia trie but it does only prefix search so if I create a trie with firstname+lastname how can I search not only by firstname but also by lastname?

Do I have to duplicate entries inserting two strings like this? Firstname+lastname And Lastname+firstname

Please help me!!!

The search have to be very efficient.

Thanks.

Upvotes: 3

Views: 1556

Answers (2)

amit
amit

Reputation: 178471

Another possibility is creating two tries.

The first one (let it be T1) is for first names, and the second (let it be T2) for last names.

When you construct the trie, from each word terminator in T1 (usually denoted as $ sign), add a list of pointers to the relevant entries in T2, and vise versa.

I.E. if John Doe is an entree:

T1:
     J
     |
     O
     |
     H
     |
     N
     |
     $1
T2:
     D
     |
     O
     |
     E
     |
     $2

$1 will hold a list, containing pointer to $2, and $2 will hold a list, containing $1.

each prefix search will search on both tries, getting you the auto completion, and then use the pointers to get the full name (the partial search gave you only first/last name, you get the second using the pointers).

Searching for full name is done by searching in both tries (look for the first name in T1 and for the last name in T2, and get the relevant $1 and $2 respectively), then you need to check if the pointers match (the list l1 in $1 contains $2 and the list l2 in $2 contains $1). If they do - the name is in the dictionary.

Note that once you have a pointer to the $ node, one can simply go back on the trie, until you get to the root to get the word this $ sign is representing. (requires pointer to parent from each node)

Also note: I explained about simple tries, but there is really no reason why not to use patricia tries instead, using the same approach.

Upvotes: 2

Stefan Haustein
Stefan Haustein

Reputation: 18803

Yes, the simplest solution is to insert both variants. However, this should only duplicate the search string, not the entry. You probably want to normalize the separation between first and last name somehow (=remove punctuation chars for the address book and for the user input), so you'll find the entries in all cases for input such as "John Doe", "Doe, John", "Doe John" etc.

I would not use a partial trie but just a balanced tree. In many languages, you'll find balanced trees as the sorted map implementation in the library (at least Java and C++).

Upvotes: 0

Related Questions