给定一个列表["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)
我的解决方案存在问题
可能更简单的实施:
if word in string_to_be_searched.但如果你正在寻找"三个"它不能处理"三人组"更新:
我接受了Aaron Hall的回答/sf/answers/1520322751/,因为根据Peter Gibson的基准测试/sf/answers/1521953331/这个简单的版本具有最佳性能.如果您对此问题感兴趣,可以阅读所有答案并获得更好的视图.
实际上我忘记在我原来的问题中提到另一个约束.这个词可以是一个短语,例如:word_list = ["one day", "second day"].也许我应该问另一个问题.
Aar*_*all 12
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!到stdout.
它确实返回找到的实际单词:
for word in words_in_string(my_word_list, a_string):
print(word)
打印出来:
three
two
one
对于如此大的数据,您无法将其保存在内存中,此答案中给出的解决方案将非常高效.
为了满足自己的好奇心,我定时发布了解决方案.结果如下:
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)
| 归档时间： |
|
| 查看次数： |
15722 次 |
| 最近记录： |