Python: 如何确定一个字符串中是否存在一组单词

Question

给定一个列表["one", "two", "three"]，如何确定每个单词是否存在于指定的字符串中？

这个单词列表相当短（在我的情况下少于20个单词），但要搜索的字符串非常庞大（每次运行有400,000个字符串）。

我目前使用 re 查找匹配，但我不确定这是否是最佳方法。

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)

我的解决方案存在的问题：

1. 即使单词可能出现在字符串的前半部分，它仍会搜索到字符串的末尾
2. 为了克服前瞻断言的限制（我不知道如何表达“当前匹配之前的字符应该是非单词字符或字符串的开头”），我在需要搜索的字符串前后添加了额外的空格。
3. 前瞻断言引入的其他性能问题？

可能更简单的实现方式：

1. 只需遍历单词列表并进行if word in string_to_be_searched判断。但它无法处理“threesome”，如果您正在寻找“three”
2. 对于每个单词使用一个正则表达式进行搜索。但我仍然不确定其性能和多次搜索字符串的潜力。

更新：

我接受了Aaron Hall的答案https://dev59.com/hmEi5IYBdhLWcg3wDoWV#21718896，因为根据Peter Gibson的基准测试结果 https://dev59.com/hmEi5IYBdhLWcg3wDoWV#21742190，这个简化版具有最佳性能。如果您对此问题感兴趣，可以阅读所有答案并获得更好的观点。

实际上，我忘记在原始问题中提到另一个约束条件。单词可以是短语，例如：word_list = ["one day", "second day"]。也许我应该问另一个问题。

- yegle

---

为什么不直接将要搜索的字符串中的单词拆分并放入字典中，然后迭代搜索列表中的单词来确定？ - michaeltang

@michaeltang 如果你需要频繁搜索该字符串，那么这将是很棒的。但是构建一个字典只为了进行一次O(1)查找并不是非常优秀的做法... - Adam Smith

我相信我的正则表达式解决方案（https://dev59.com/hmEi5IYBdhLWcg3wDoWV#21719831）可以适用于您的额外限制：即使它是第二快的，但速度慢了4倍，但最快的解决方案也无法解决这个问题。将您的问题与一个附加限制重新利用可能不是一个好主意，但我可能是错的。 - Russia Must Remove Putin

Answer 1

以下是由Peter Gibson发现的最高效的函数之一。 它适用于那些可以保存在内存中的数据集（因为它从要搜索的字符串创建一个单词列表，然后创建该列表的一个集合）：

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

用法：

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!')

这段代码会将 One or words found! 打印到标准输出。

它确实会返回找到的实际单词：

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

输出：

three
two
one

如果数据太大而无法在内存中保存，那么这个答案中提供的解决方案将非常高效。

- Russia Must Remove Putin

---

很流畅，但它需要指示在a_string中找到的a_list中的每个单词，而不仅仅是一个单词。 - user447688

@JohnPirie 我不确定请求者具体想要什么，但你所说的正是它所需要的！:D - Russia Must Remove Putin

我在测试中发现这是最快的解决方案（请参见我的新帖子），而且它的简单性确实很吸引人 - 干得好。 - Peter Gibson

是的，它比现在慢，但仍然是较快的解决方案之一。请查看结果https://dev59.com/hmEi5IYBdhLWcg3wDoWV#21742190 - Peter Gibson

同意，那是我的主要评论。我预计我的另一个解决方案不会因长度而降低质量，这也是我发布它的原因。 - Russia Must Remove Putin

Answer 2

为了满足我的好奇心，我对发布的解决方案进行了计时。以下是结果：

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>

有趣的是，@AaronHall提供的解决方案。

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

其中最快的方法也是最短的方法之一！但需要注意它不能处理单词后面的标点符号，但从问题中并不清楚这是否是一个要求。这个解决方案也由@MIE和@user3建议。

我没有详细查看为什么两个解决方案不起作用。如果这是我的错误，请谅解。这是测试的代码，欢迎提出评论和更正。

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)

- Peter Gibson

---

惊人的事实，感谢您的测试和比较。我得到了与您类似的结果。 - yegle

Answer 3

简单方法：

filter(lambda x:x in string,search_list)

如果您希望搜索忽略字符大小写，可以这样做：

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

如果你想忽略那些作为更大单词一部分的单词，比如在“threesome”中的“three”：

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]

---

如果需要提高性能：

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

编辑：在一个包含400,000个单词的字符串中搜索1,000个单词时，该方法是最快的，但如果我们将字符串增加到4,000,000，则之前的方法更快。

---

如果字符串太长，您应该进行低级别搜索，并避免将其转换为列表：

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(set(search_list)-set(not_found))

编辑：最后一种方法似乎是最慢的。

- MIE

---

如果你要查找“三个”，它无法处理“三人行”。 - michaeltang

我已经测试了所有发布的解决方案的时间，但是我无法让你的解决方案完成所有测试 - 它在其中一个测试中返回 None。如果您愿意查看并修复它（或告诉我我的问题在哪里），我会更新结果。谢谢。stackoverflow.com/a/21742190/66349 - Peter Gibson

@PeterGibson 第一种方法已经被编辑过了，而且如果字符串超过四百万个单词，第一种方法更快。 - MIE

Answer 4

你可以尝试这个：

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

它只会从您的单词列表中返回匹配的单词。如果没有匹配的单词，它将返回空列表。

- venpa

Answer 5

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

- perreal

---

这看起来很有希望...也许将string.split替换为其中一个生成器版本，可以在https://dev59.com/Wm865IYBdhLWcg3wWtKz找到。 - yegle

@yegle，但是这样做一个排序的生成器版本会很困难吗？ - perreal

Answer 6

根据您的评论

我实际上不是在寻找单个布尔值，而是在寻找将单词映射到布尔值的字典。此外，我可能需要运行一些测试，看看运行多次re.search和运行re.findall一次的性能如何。- yegle

我建议采用以下方法

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') == []

这将返回按顺序找到的单词列表，但您可以轻松修改它以根据需要返回dict{word:bool}。

优点：

• 当找到所有单词时，停止搜索输入字符串
• 一旦找到一个单词，就从候选中删除它

- Peter Gibson

Answer 7

这里有一个简单的生成器，适用于大字符串或文件，在下面的部分中我会对其进行调整。

请注意，这应该非常快，但只要字符串继续而没有命中所有单词，它就会继续运行。 这在Peter Gibson的基准测试中排名第二：Python：如何确定字符串中是否存在一组单词 对于较短字符串的更快解决方案，请参见我的另一个答案：Python：如何确定字符串中是否存在一组单词

---

原始答案

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 

它遍历字符串并在找到单词时产生它们，如果找到所有单词或到达字符串的末尾，则放弃搜索。

用法：

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

---

编辑：适用于大文件的改编：

感谢Peter Gibson找到了第二快的方法。我对这个解决方案感到非常自豪。由于这个函数最好的使用情况是处理一个巨大的文本流，让我在这里改编上面的函数来处理一个文件。请注意，如果单词在换行符上被打断，这个函数将无法捕捉到它们，但其他方法也不会。

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

为了演示，让我们写一些数据：

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

以及使用方法：

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

现在我们有一个迭代器，如果我们使用列表消耗它：

list(iterator)

它返回：

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

- Russia Must Remove Putin

---

在使用 re 之前，您可能希望对 word_list 应用 re.escape。因为一些包含正则表达式元字符的单词可能无法按预期匹配。 - John Strood

@JohnStrood，听起来是个好主意。我会尽快去试一下的。谢谢！ - Russia Must Remove Putin

Answer 8

如果你的字符串很长，而搜索列表很短，请这样做：

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

- Adam Smith

---

for word in big_long_string 这会遍历字符，而不是单词，对吗？ - Peter Gibson

使用 split 的问题可能在于它创建了一个新列表来保存所有的字符串。 - Peter Gibson

Answer 9

您可以利用单词边界:

>>> 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"
...
>>>

---

编辑：根据您的评论，您似乎正在寻找一个字典：

>>> 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}

- devnull

---

将此与使用“|”将搜索术语“OR”在一起的单个正则表达式进行比较会很有趣。 - Peter Gibson

@PeterGibson 即使只匹配一个单词，它也会返回匹配结果，但不会匹配所有单词。 - thefourtheye

我实际上不仅寻找单个 bool 值，还要寻找将 word 映射到 bool 的字典。另外，我可能需要运行一些测试来查看多次运行 re.search 和一次运行 re.findall 的性能。 - yegle

@thefourtheye 是的，但可能要在找到匹配之前多次完全搜索输入字符串 - 我怀疑只有一次迭代输入字符串更有效（不过这只是我的猜测） - Peter Gibson

@PeterGibson 嗯，我怀疑。 RE 引擎可能已被实现为状态机。因此，它不必进行多次迭代。 - thefourtheye

Answer 10

如果顺序不太重要，您可以使用这种方法。

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)

.split() 方法会创建一个列表，对于包含 400k 字符的字符串来说可能会成为问题。但如果你有足够的 RAM，那么就没问题了。

当然，可以修改 for 循环以避免创建整个列表。使用 re.finditer 或者使用 str.find 创建生成器是明显的选择。

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)

- John La Rooy