5
\$\begingroup\$

I am working on a problem to develop auto-complete functionality to practice different applications of Tries. The auto-complete function will return all the possible words in the wordlist given a prefix. I came up with the following solution which returns the result as expected. I need some help to review my code, in order to enhance the OOP structure and improve the code quality over all.

Please let me know your thoughts, any feedback is welcome.

class Trie():
    def __init__(self):
        self.children = {}
        self.flag = False # Flag to represent that a word ends at this node

    def insert(self, word):
        for char in word:
            if char not in self.children:
               self.children[char]= Trie()

            self = self.children[char]
        self.flag = True

    def all_suffixes(self, prefix):
        results = set()

        if self.flag:
            results.add(prefix)

        if not self.children: 
            return results

        return reduce(lambda a, b: a | b,  [node.all_suffixes(prefix + char) for (char, node) in self.children.items()]) 

    def autocomplete(self, prefix):
        node = self
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return list(node.all_suffixes(prefix))

if __name__=="__main__":
    word_list = ['aardvark','ark', 'altimeter','altitude', 'apotactic', 'bagonet', 'boatlip', 
    'carburant', 'chyliferous', 'consonance', 'cyclospondylic', 
    'dictyostele', 'echelon', 'estadal', 'flaunty', 'gesneriaceous', 
    'hygienic', 'infracentral', 'jipijapa', 'lipoceratous', 'melanthaceae']

    c = Trie()

    for word in word_list:
        c.insert(word)
    print c.autocomplete('a')

Output - ['aardvark', 'ark', 'altimeter', 'altitude', 'apotactic']

I was thinking on the lines of having two classes one as Trie() and the other as Autocomplete(). The __init__(self,word_list) for Autocomplete() can then have the for loop code snippet to create the Trie from the word list.

\$\endgroup\$
  • \$\begingroup\$ Also see: en.wikipedia.org/wiki/Suffix_tree ; though bit more complex and unnecessary in this case... However, if you are exploring Data structures regarding string manipulations, then it could be helpful \$\endgroup\$ – kushj Nov 10 '15 at 20:02
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Nov 11 '15 at 10:02
  • \$\begingroup\$ @Vogel612 I will keep that in mind, but that snippet |results was already in the solution that I was originally referring to and for some reason it got left out while posting the question. \$\endgroup\$ – aamir23 Nov 11 '15 at 10:14
4
\$\begingroup\$

Bug

Put 'a' in word_list: it is not found by autocomplete('a'). This is because all_suffixes doesn't use the result variable when building the result in case the node has children.

Naming

  • The name self.flag tells nothing about the purpose of the variable. self.word_end would be better.
  • all_suffixes returns whole words, not suffixes. words_with_prefix would be a better name. Alternatively, the function could return suffixes only and adding the prefix would be the responsibility of autocomplete.

Other

Instead of using a set and reduce in all_suffixes, it would be simpler to use just a list and extend it in a loop. (There should be no duplicate words in the list anyway, because the trie does not store duplicates)

def words_with_prefix(self, prefix):
    results = []
    if self.word_end:
        results.append(prefix)
    for (char, node) in self.children.items():
        results.extend(node.all_suffixes(prefix + char))
    return results
\$\endgroup\$
  • \$\begingroup\$ Could you please elaborate on the bug? If you meant that the function should also return 'a', then actually I am only trying to find words that begin with the prefix. So if I pass autocomplete(art) and the word list only contained say artist then the results would have only artist and not art itself \$\endgroup\$ – aamir23 Nov 10 '15 at 23:26
  • 1
    \$\begingroup\$ @aamir23 But if both art and artist are in the list, I would expect to see both in results. Your version only returns artist. \$\endgroup\$ – Janne Karila Nov 11 '15 at 6:28
  • \$\begingroup\$ @Jane Karila You are correct, I believed the flag would take care of it indicating a word ends here, but when I tested it right now it only returned artist. Thank you for pointing it out and fixing it. \$\endgroup\$ – aamir23 Nov 11 '15 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.