Tukukkk

Problem

Given a Dictionary with user_id and a list of alert_words (words and phrases too look for in an sentence) and a string content. We have to look if the alert_words appears in the content and return the list of user_ids who's alert_words appears in the content

Example

input = { 1 : ['how are you'], 2 : ['you are'] }

content = 'hello, how are you'

output = [1]

user_id = 1 has 'how are you' while user_id = 2 has the words but not in the correct order so only user 1 is returned.

Solution

I'm using Google's pygtrie implementation of Trie data structure to achieve this. [pygtrie documentation]

Algorithm:

• For each word in the given sentence


• Check if the word is a key, if yes add it to the list of user_ids


• check if the word has a subtrie i.e. that current word is the starting of a alert_word. So add it to another set alert_phrases
  


• for each word in alert_phrases we check if we can extent with the current word and do the same set of operations if it is a key/subtrie

Code

import pygtrie

from typing import Dict, List, Set



def build_trie(realm_alert_words : Dict[int, List[int]]) -> pygtrie.StringTrie:

    trie = pygtrie.StringTrie()

    for user_id, words in realm_alert_words.items():

        for word in words:

            alert_word = trie._separator.join(word.split())        

            if trie.has_key(alert_word):

                user_ids_for_word = trie.get(alert_word)

                user_ids_for_word.update([user_id])

            else:

                trie[alert_word] = set([user_id])

    return trie



def get_user_ids_with_alert_words(trie : pygtrie.StringTrie, content : str) -> Set[int]:

    """Returns the list of user_id's who have alert_words present in content"""

    content_words = content.split()

    alert_phrases = set()

    user_ids_in_messages = set()

    for possible_alert_word in content_words:

        #has_node returns 1(HAS_VALUE) if the exact key is found, 2(HAS_SUBTRIE) if the key is a sub trie, 

        # 3 if it's both 0 if it's none 

        #https://pygtrie.readthedocs.io/en/latest/#pygtrie.Trie.has_node



        alert_word_in_trie = trie.has_node(possible_alert_word)

        if alert_word_in_trie & pygtrie.Trie.HAS_VALUE:

            user_ids = trie.get(possible_alert_word)

            user_ids_in_messages.update(user_ids)



        deep_copy_alert_phrases = set(alert_phrases)



        # Check if extending the phrases with the current word in content is a subtrie or key. And

        # Remove the word if it is not a subtrie as we are interested only in continuos words in the content

        for alert_phrase in deep_copy_alert_phrases:

            alert_phrases.remove(alert_phrase)

            extended_alert_phrase = alert_phrase + trie._separator + possible_alert_word

            alert_phrase_in_trie = trie.has_node(extended_alert_phrase)



            if alert_phrase_in_trie & pygtrie.Trie.HAS_VALUE:

                user_ids = trie.get(extended_alert_phrase)

                user_ids_in_messages.update(user_ids)



            if alert_phrase_in_trie & pygtrie.Trie.HAS_SUBTRIE:

                alert_phrases.add(extended_alert_phrase)



        if alert_word_in_trie & pygtrie.Trie.HAS_SUBTRIE:

            alert_phrases.add(possible_alert_word)



    return user_ids_in_messages

Tests

input = {1 : ['hello'], 7 : ['this possible'], 2 : ['hello'], 3 : ['hello'], 5 : ['how are you'], 6 : ['hey']}

alert_word_trie = build_trie(input)

content = 'hello how is this possible how are you doing today'

result  = get_user_ids_with_alert_words(alert_word_trie, content)

assert(result == set([1, 2, 3, 5, 7]))



input = {1 : ['provisioning', 'Prod deployment'], 2 : ['test', 'Prod'], 3 : ['prod'], 4 : ['deployment'] }

alert_word_trie = build_trie(input)

content = 'Hello, everyone. Prod deployment has been completed'

result  = get_user_ids_with_alert_words(alert_word_trie, content)

assert(result == set([1, 2, 4]))



input = {1 : ['provisioning/log.txt'] }

alert_word_trie = build_trie(input)

content = 'Hello, everyone. Errors logged at provisioning/log.txt '

result  = get_user_ids_with_alert_words(alert_word_trie, content)

assert(result == set([1]))

The two methods are part of a larger classes which have some not so related code. You get a list of user_id's and their alert_words from the database and you process every message content based on the trie already build up.

This is for a chat application so frequency of running the get_user_id_with_alert_words is high when the build_trie is relatively less since it will be cached.