Python: how to determine if a list of words exist in a string

Question

Given a list ["one", "two", "three"], how to determine if each word exist in a specified string?

The word list is pretty short (in my case less than 20 words), but the strings to be searched is pretty huge (400,000 strings for each run)

My current implementation uses re to look for matches but I'm not sure if it's the best way.

import re
word_list = ["one", "two", "three"]
regex_string = "(?<=\W)(%s)(?=\W)" % "|".join(word_list)

finder = re.compile(regex_string)
string_to_be_searched = "one two three"

results = finder.findall(" %s " % string_to_be_searched)
result_set = set(results)
for word in word_list:
    if word in result_set:
        print("%s in string" % word)

Problems in my solution:

1. It will search until the end of the string, although the words may appear in the first half of the string
2. In order to overcome the limitation of lookahead assertion (I don't know how to express "the character before current match should be non-word characters, or the start of the string"), I added extra space before and after the string I need to be searched.
3. Other performance issue introduced by the lookahead assertion?

Possible simpler implementation:

1. just loop through the word list and do a if word in string_to_be_searched. But it can not deal with "threesome" if you are looking for "three"
2. Use one regular expression search for one word. Still I'm not sure about the performance, and the potential of searching string multiple times.

UPDATE:

I've accepted Aaron Hall's answer https://stackoverflow.com/a/21718896/683321 because according to Peter Gibson's benchmark https://stackoverflow.com/a/21742190/683321 this simple version has the best performance. If you are interested in this problem, you can read all the answers and get a better view.

Actually I forgot to mention another constraint in my original problem. The word can be a phrase, for example: word_list = ["one day", "second day"]. Maybe I should ask another question.

Answer 1

This function was found by Peter Gibson (below) to be the most performant of the answers here. It is good for datasets one may hold in memory (because it creates a list of words from the string to be searched and then a set of those words):

def words_in_string(word_list, a_string):
    return set(word_list).intersection(a_string.split())

Usage:

my_word_list = ['one', 'two', 'three']
a_string = 'one two three'
if words_in_string(my_word_list, a_string):
    print('One or more words found!')

Which prints One or words found! to stdout.

It does return the actual words found:

for word in words_in_string(my_word_list, a_string):
    print(word)

Prints out:

three
two
one

---

For data so large you can't hold it in memory, the solution given in this answer would be very performant.

Answer 2

To satisfy my own curiosity, I've timed the posted solutions. Here are the results:

TESTING: words_in_str_peter_gibson          0.207071995735
TESTING: words_in_str_devnull               0.55300579071
TESTING: words_in_str_perreal               0.159866499901
TESTING: words_in_str_mie                   Test #1 invalid result: None
TESTING: words_in_str_adsmith               0.11831510067
TESTING: words_in_str_gnibbler              0.175446796417
TESTING: words_in_string_aaron_hall         0.0834425926208
TESTING: words_in_string_aaron_hall2        0.0266295194626
TESTING: words_in_str_john_pirie            <does not complete>

Interestingly @AaronHall's solution

def words_in_string(word_list, a_string):
    return set(a_list).intersection(a_string.split())

which is the fastest, is also one of the shortest! Note it doesn't handle punctuation next to words, but it's not clear from the question whether that is a requirement. This solution was also suggested by @MIE and @user3.

I didn't look very long at why two of the solutions did not work. Apologies if this is my mistake. Here is the code for the tests, comments & corrections are welcome

from __future__ import print_function
import re
import string
import random
words = ['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten']

def random_words(length):
    letters = ''.join(set(string.ascii_lowercase) - set(''.join(words))) + ' '
    return ''.join(random.choice(letters) for i in range(int(length)))

LENGTH = 400000
RANDOM_STR = random_words(LENGTH/100) * 100
TESTS = (
    (RANDOM_STR + ' one two three', (
        ['one', 'two', 'three'],
        set(['one', 'two', 'three']),
        False,
        [True] * 3 + [False] * 7,
        {'one': True, 'two': True, 'three': True, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    (RANDOM_STR + ' one two three four five six seven eight nine ten', (
        ['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten'],
        set(['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten']),
        True,
        [True] * 10,
        {'one': True, 'two': True, 'three': True, 'four': True, 'five': True, 'six': True,
            'seven': True, 'eight': True, 'nine': True, 'ten':True}
        )),

    ('one two three ' + RANDOM_STR, (
        ['one', 'two', 'three'],
        set(['one', 'two', 'three']),
        False,
        [True] * 3 + [False] * 7,
        {'one': True, 'two': True, 'three': True, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    (RANDOM_STR, (
        [],
        set(),
        False,
        [False] * 10,
        {'one': False, 'two': False, 'three': False, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    (RANDOM_STR + ' one two three ' + RANDOM_STR, (
        ['one', 'two', 'three'],
        set(['one', 'two', 'three']),
        False,
        [True] * 3 + [False] * 7,
        {'one': True, 'two': True, 'three': True, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    ('one ' + RANDOM_STR + ' two ' + RANDOM_STR + ' three', (
        ['one', 'two', 'three'],
        set(['one', 'two', 'three']),
        False,
        [True] * 3 + [False] * 7,
        {'one': True, 'two': True, 'three': True, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    ('one ' + RANDOM_STR + ' two ' + RANDOM_STR + ' threesome', (
        ['one', 'two'],
        set(['one', 'two']),
        False,
        [True] * 2 + [False] * 8,
        {'one': True, 'two': True, 'three': False, 'four': False, 'five': False, 'six': False,
            'seven': False, 'eight': False, 'nine': False, 'ten':False}
        )),

    )

def words_in_str_peter_gibson(words, s):
    words = words[:]
    found = []
    for match in re.finditer('\w+', s):
        word = match.group()
        if word in words:
            found.append(word)
            words.remove(word)
            if len(words) == 0: break
    return found

def words_in_str_devnull(word_list, inp_str1):
    return dict((word, bool(re.search(r'\b{}\b'.format(re.escape(word)), inp_str1))) for word in word_list)


def words_in_str_perreal(wl, s):
    i, swl, strwords = 0, sorted(wl), sorted(s.split())
    for w in swl:
        while strwords[i] < w:  
            i += 1
            if i >= len(strwords): return False
        if w != strwords[i]: return False
    return True

def words_in_str_mie(search_list, string):
    lower_string=string.lower()
    if ' ' in lower_string:
        result=filter(lambda x:' '+x.lower()+' ' in lower_string,search_list)
        substr=lower_string[:lower_string.find(' ')]
        if substr in search_list and substr not in result:
            result+=substr
        substr=lower_string[lower_string.rfind(' ')+1:]
        if substr in search_list and substr not in result:
            result+=substr
    else:
        if lower_string in search_list:
            result=[lower_string]

def words_in_str_john_pirie(word_list, to_be_searched):
    for word in word_list:
        found = False
        while not found:
            offset = 0
            # Regex is expensive; use find
            index = to_be_searched.find(word, offset)
            if index < 0:
                # Not found
                break
            if index > 0 and to_be_searched[index - 1] != " ":
                # Found, but substring of a larger word; search rest of string beyond
                offset = index + len(word)
                continue
            if index + len(word) < len(to_be_searched) \
                    and to_be_searched[index + len(word)] != " ":
                # Found, but substring of larger word; search rest of string beyond
                offset = index + len(word)
                continue
            # Found exact word match
            found = True    
    return found

def words_in_str_gnibbler(words, string_to_be_searched):
    word_set = set(words)
    found = []
    for match in re.finditer(r"\w+", string_to_be_searched):
        w = match.group()
        if w in word_set:
             word_set.remove(w)
             found.append(w)
    return found

def words_in_str_adsmith(search_list, big_long_string):
    counter = 0
    for word in big_long_string.split(" "):
        if word in search_list: counter += 1
        if counter == len(search_list): return True
    return False

def words_in_string_aaron_hall(word_list, a_string):
    def words_in_string(word_list, a_string):
        '''return iterator of words in string as they are found'''
        word_set = set(word_list)
        pattern = r'\b({0})\b'.format('|'.join(word_list))
        for found_word in re.finditer(pattern, a_string):
            word = found_word.group(0)
            if word in word_set:
                word_set.discard(word)
                yield word
                if not word_set:
                    raise StopIteration
    return list(words_in_string(word_list, a_string))

def words_in_string_aaron_hall2(word_list, a_string):
    return set(word_list).intersection(a_string.split())

ALGORITHMS = (
        words_in_str_peter_gibson,
        words_in_str_devnull,
        words_in_str_perreal,
        words_in_str_mie,
        words_in_str_adsmith,
        words_in_str_gnibbler,
        words_in_string_aaron_hall,
        words_in_string_aaron_hall2,
        words_in_str_john_pirie,
        )

def test(alg):
    for i, (s, possible_results) in enumerate(TESTS):
        result = alg(words, s)
        assert result in possible_results, \
            'Test #%d invalid result: %s ' % (i+1, repr(result))

COUNT = 10
if __name__ == '__main__':
    import timeit
    for alg in ALGORITHMS:
        print('TESTING:', alg.__name__, end='\t\t')
        try:
            print(timeit.timeit(lambda: test(alg), number=COUNT)/COUNT)
        except Exception as e:
            print(e)

Answer 3

Easy way:

filter(lambda x:x in string,search_list)

if you want the search to ignore character's case you can do this:

lower_string=string.lower()
filter(lambda x:x.lower() in lower_string,search_list)

if you want to ignore words that are part of bigger word such as three in threesome:

lower_string=string.lower()
result=[]
if ' ' in lower_string:
    result=filter(lambda x:' '+x.lower()+' ' in lower_string,search_list)
    substr=lower_string[:lower_string.find(' ')]
    if substr in search_list and substr not in result:
        result+=[substr]
    substr=lower_string[lower_string.rfind(' ')+1:]
    if substr in search_list and substr not in result:
        result+=[substr]
else:
    if lower_string in search_list:
        result=[lower_string]

---

If performance is needed:

arr=string.split(' ')
result=list(set(arr).intersection(set(search_list)))

EDIT: this method was the fastest in an example that searches for 1,000 words in a string containing 400,000 words but if we increased the string to be 4,000,000 the previous method is faster.

---

if string is too long you should do low level search and avoid converting it to list:

def safe_remove(arr,elem):
    try:
        arr.remove(elem)
    except:
        pass

not_found=search_list[:]
i=string.find(' ')
j=string.find(' ',i+1)
safe_remove(not_found,string[:i])
while j!=-1:
    safe_remove(not_found,string[i+1:j])
    i,j=j,string.find(' ',j+1)
safe_remove(not_found,string[i+1:])

not_found list contains words that are not found, you can get the found list easily, one way is list(set(search_list)-set(not_found))

EDIT: the last method appears to be the slowest.

Answer 4

def words_in_str(s, wl):
    i, swl, strwords = 0, sorted(wl), sorted(s.split())
    for w in swl:
        while strwords[i] < w:  
            i += 1
            if i >= len(strwords): return False
        if w != strwords[i]: return False
    return True

Answer 5

You can try this:

list(set(s.split()).intersection(set(w)))

It return only matched words from your word list. If no words matched, it would return empty list.

Answer 6

If your string is long and your search list is short, do this:

def search_string(big_long_string,search_list)
    counter = 0
    for word in big_long_string.split(" "):
        if word in search_list: counter += 1
        if counter == len(search_list): return True
    return False

Answer 7

You could make use of word boundaries:

>>> import re
>>> word_list = ["one", "two", "three"]
>>> inp_str = "This line not only contains one and two, but also three"
>>> if all(re.search(r'\b{}\b'.format(re.escape(word)), inp_str) for word in word_list):
...   print "Found all words in the list"
...
Found all words in the list
>>> inp_str = "This line not only contains one and two, but also threesome"
>>> if all(re.search(r'\b{}\b'.format(re.escape(word)), inp_str) for word in word_list):
...   print "Found all words in the list"
...
>>> inp_str = "This line not only contains one and two, but also four"
>>> if all(re.search(r'\b{}\b'.format(re.escape(word)), inp_str) for word in word_list):
...   print "Found all words in the list"
...
>>>

---

EDIT: As indicated in your comment, you seem to be looking for a dictionary instead:

>>> dict((word, bool(re.search(r'\b{}\b'.format(re.escape(word)), inp_str1))) for word in word_list)
{'three': True, 'two': True, 'one': True}
>>> dict((word, bool(re.search(r'\b{}\b'.format(re.escape(word)), inp_str2))) for word in word_list)
{'three': False, 'two': True, 'one': True}
>>> dict((word, bool(re.search(r'\b{}\b'.format(re.escape(word)), inp_str3))) for word in word_list)
{'three': False, 'two': True, 'one': True}

Answer 8

If the order isn't too important, you can use this approach

word_set = {"one", "two", "three"}
string_to_be_searched = "one two three"

for w in string_to_be_searched.split():
    if w in word_set:
         print("%s in string" % w)
         word_set.remove(w)

The .split() creates a list, which may be a problem for your 400k word string. But if you have enough RAM, you are done.

It's of course possible to modify the for loop to avoid creating the whole list. re.finditer or a generator using str.find are the obvious choices

import re
word_set = {"one", "two", "three"}
string_to_be_searched = "one two three"

for match in re.finditer(r"\w+", string_to_be_searched):
    w = match.group()
    if w in word_set:
         print("%s in string" % w)
         word_set.remove(w)

Answer 9

Given your comment

I'm not actually looking for a single bool value, instead I'm looking for a dict mapping word to bool. Besides, I may need to run some test and see the performance of running re.search multiple times and run re.findall once. – yegle

I would propose the following

import re
words = ['one', 'two', 'three']

def words_in_str(words, s):
    words = words[:]
    found = []
    for match in re.finditer('\w+', s):
        word = match.group()
        if word in words:
            found.append(word)
            words.remove(word)
            if len(words) == 0: break
    return found

assert words_in_str(words, 'three two one') == ['three', 'two', 'one']
assert words_in_str(words, 'one two. threesome') == ['one', 'two']
assert words_in_str(words, 'nothing of interest here one1') == []

This returns a list of words found in order, but you could easily modify it to return a dict{word:bool} as you desire.

Advantages:

• stops searching through input string when all words are found
• removes a word form candidates once it is found

Answer 10

Here's a simple generator that would be better for big strings, or a file, as I adapt it in the section below.

Note that this should be very fast, but it will continue for as long as the string continues without hitting all the words. This came in second on Peter Gibson's benchmarking: Python: how to determine if a list of words exist in a string

For a faster solution for shorter strings, see my other answer here: Python: how to determine if a list of words exist in a string

---

Original Answer

import re

def words_in_string(word_list, a_string):
    '''return iterator of words in string as they are found'''
    word_set = set(word_list)
    pattern = r'\b({0})\b'.format('|'.join(word_list))
    for found_word in re.finditer(pattern, a_string):
        word = found_word.group(0)
        if word in word_set:
            word_set.discard(word)
            yield word
            if not word_set: # then we've found all words
                # break out of generator, closing file
                raise StopIteration 

It goes through the string yielding the words as it finds them, abandoning the search after it finds all the words, or if it reaches the end of the string.

Usage:

word_list = ['word', 'foo', 'bar']
a_string = 'A very pleasant word to you.'
for word in words_in_string(word_list, a_string):
    print word

word

---

EDIT: adaptation to use with a large file:

Thanks to Peter Gibson for finding this the second fastest approach. I'm quite proud of the solution. Since the best use-case for this is to go through a huge text stream, let me adapt the above function here to handle a file. Do note that if words are broken on newlines this will not catch them, but neither would any of the other methods here.

import re

def words_in_file(word_list, a_file_path):
    '''
    return a memory friendly iterator of words as they are found
    in a file.
    '''
    word_set = set(word_list)
    pattern = r'\b({0})\b'.format('|'.join(word_list))
    with open(a_file_path, 'rU') as a_file:
        for line in a_file:
            for found_word in re.finditer(pattern, line):
                word = found_word.group(0)
                if word in word_set:
                    word_set.discard(word)
                    yield word
                    if not word_set: # then we've found all words
                        # break out of generator, closing file
                        raise StopIteration

To demonstrate, let's write some data:

file_path = '/temp/temp/foo.txt'
with open(file_path, 'w') as f:
    f.write('this\nis\nimportant\ndata')

and usage:

word_list = ['this', 'is', 'important']
iterator = words_in_file(word_list, file_path)

we now have an iterator, and if we consume it with a list:

list(iterator)

it returns:

['this', 'is', 'important']