# Looking for words from a list of words in a sentence

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 word in words:
user_ids_for_word.update([user_id])
else:
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()
user_ids_in_messages = set()
#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

user_ids_in_messages.update(user_ids)

# 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

user_ids_in_messages.update(user_ids)

return user_ids_in_messages


Tests

input = {1 : ['hello'], 7 : ['this possible'], 2 : ['hello'], 3 : ['hello'], 5 : ['how are you'], 6 : ['hey']}
content = 'hello how is this possible how are you doing today'
assert(result == set([1, 2, 3, 5, 7]))

input = {1 : ['provisioning', 'Prod deployment'], 2 : ['test', 'Prod'], 3 : ['prod'], 4 : ['deployment'] }
content = 'Hello, everyone. Prod deployment has been completed'
assert(result == set([1, 2, 4]))

input = {1 : ['provisioning/log.txt'] }
content = 'Hello, everyone. Errors logged at provisioning/log.txt '

The two methods are part of a larger classes which have some not so related code. You get a list of user_ids 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.
• If content is Hello, how [some words] are [more words] you, what the result should be? – vnp Jan 12 at 22:16
• @Carcigenicate you solution iterates the entire alert_words which grows in size as users increase. Also i don't think the in a list is of linear time complexity. – thebenman Jan 13 at 5:23
• @thebenman: in is O(n) for lists (and strings): wiki.python.org/moin/TimeComplexity – Graipher Jan 13 at 9:13
• @Graipher Finding a word in a trie is O(m) where m is the length of the word and finding it in a list would be O(n) where n is the total number of elements in the list which can grow as opposed to the number of words in the message. – thebenman Jan 13 at 11:56