加快re。在Python中搜索[重复]

Question

我有两个大字符串列表，我需要将第二个列表中的每个项目与第一个列表中的第一个项目进行比较。然后是第二项，第三项，依此类推。

我一直在使用下面的代码，这很好，但是当列表有大约20000个元素时，处理起来就太费时间了。

子字符串是第二个数组，list_elem是第一个数组

found = [
    elem
    for elem in list_elem
    for substring in substrings
    if re.search(r"\b" + substring + r"\b", elem, re.IGNORECASE)
]

我一直试图从这篇文章中实现答案，但它不能以这种方式工作，我真的不知道如何将其更改为搜索而不是替换。我说的是埃里克的答案。这是我的代码：

found_words = set(word.lower().strip() for word in substrings)
found = []
def find_words(matchobj):
    word = matchobj.group(0)
    if word.lower() in found_words:
        return ""
    else:
        return word

word_pattern = re.compile('\w+')

for sentence in list_elem:
    sentence = word_pattern.sub(find_words, sentence)
    found.append(sentence)

return found

我的意思是，没有模式搜索（）正则表达式函数。

我想在元素中找到子串，若有子串，我将元素添加到列表中。

Answer 1

正则表达式成本高昂...在你的情况下，为什么不依靠这样的东西：

found = [
    elem
    for elem in list_elem
    for substring in substrings
    if substring.lower() in elem.lower()
]

如果你真的想使用正则表达式，我建议你事先编译你的正则表达式：

regexes = [
    re.compile(r"\b" + substring + r"\b", re.IGNORECASE)
    for substring in substrings
]
found = [
    elem
    for elem in list_elem
    for regex in regexes
    if regex.search(elem)
]

这应该会加快你的执行速度，但不确定它是否足以处理很多元素。

最后，如果您想使用第二个代码片段中的集合，可以拆分语句并检查子字符串成员资格。

以下是比较三种解决方案的代码片段：

import re
import timeit


def main():
    sentences = [
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit.",
        "Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.",
        "Donec eget est sit amet eros pharetra fermentum.",
        "Proin volutpat dui eget lacinia lobortis.",
        "Pellentesque a ante eu ligula dictum lobortis.",
        "Phasellus et velit mattis, finibus velit ut, luctus purus.",
        "Integer et risus maximus, varius eros vel, venenatis libero.",
        "Proin blandit dui vel ante blandit, et aliquet orci placerat.",
        "Suspendisse eu lacus non nunc accumsan congue non id velit.",
        "Pellentesque condimentum dui ultricies justo dapibus imperdiet eget eget tortor.",
        "Suspendisse faucibus erat a dolor fringilla suscipit.",
        "Duis quis tortor convallis purus porttitor elementum.",
        "Proin rutrum lacus sed elit convallis porttitor.",
        "Nunc sit amet felis ullamcorper, pulvinar augue sed, ullamcorper leo.",
        "Ut a erat eu lectus semper pulvinar.",
        "Praesent congue velit at nulla finibus hendrerit.",
        "Nullam ac erat convallis, suscipit purus quis, dictum eros.",
        "Proin condimentum orci nec suscipit imperdiet.",
        "Aliquam mattis mauris et turpis sodales tincidunt.",
        "Vestibulum vel ante bibendum, interdum ipsum efficitur, porta massa.",
        "Duis finibus nisl et urna pharetra, non dignissim ante tempus.",
        "Morbi nec lorem eu odio interdum feugiat id sed ligula.",
        "Donec nec lorem vitae est consequat dictum.",
        "Quisque vehicula quam eu pretium viverra.",
        "Etiam luctus metus faucibus, vulputate augue et, luctus enim.",
        "Nullam quis elit vitae enim bibendum viverra.",
        "Donec consectetur nulla sit amet nulla blandit, sed auctor mi porttitor.",
        "Suspendisse vel urna vitae massa mollis dignissim quis eu nulla.",
        "Vestibulum id risus fringilla nisl consectetur fringilla.",
        "Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.",
        "Sed feugiat orci pulvinar, imperdiet massa sit amet, semper dui.",
        "Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.",
        "Cras vel urna fermentum, tempus magna ut, aliquet dolor.",
        "Fusce non urna molestie massa sagittis accumsan et eget lorem.",
        "Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.",
    ]
    substrings = [
        "a", "eu", "non", "ac", "at", "et"
    ]

    print("if_in:")
    print(if_in(sentences, substrings))
    print(timeit.timeit(lambda : if_in(sentences, substrings), number=100))
    print("re_compile:")
    print(re_compile(sentences, substrings))
    print(timeit.timeit(lambda : re_compile(sentences, substrings), number=100))
    print("in_set:")
    print(in_set(sentences, substrings))
    print(timeit.timeit(lambda : in_set(sentences, substrings), number=100))



def if_in(sentences, substrings):
    return [
        s
        for s in sentences
        for substring in substrings
        if substring.lower() in s.lower()
    ]

def re_compile(sentences, substrings):
    regexes = [
        re.compile(r"\b" + substring + r"\b", re.IGNORECASE)
        for substring in substrings
    ]
    return [
        s
        for s in sentences
        for regex in regexes
        if regex.search(s)
    ]

def in_set(sentences, substrings):
    # Split your sentences on word boundaries (see https://stackoverflow.com/questions/37237594/how-can-i-split-at-word-boundaries-with-regexes)
    splitter = re.compile(r'\w+|\W+')
    sentence_sets = [set(splitter.findall(s)) for s in sentences]

    return [
        s
        for s, s_set in zip(sentences, sentence_sets)
        for sub in substrings
        if sub in s_set
    ]

if __name__ == '__main__':
    main()

if_in:
['Lorem ipsum dolor sit amet, consectetur adipiscing elit.', 'Lorem ipsum dolor sit amet, consectetur adipiscing elit.', 'Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.', 'Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.', 'Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.', 'Donec eget est sit amet eros pharetra fermentum.', 'Donec eget est sit amet eros pharetra fermentum.', 'Proin volutpat dui eget lacinia lobortis.', 'Proin volutpat dui eget lacinia lobortis.', 'Proin volutpat dui eget lacinia lobortis.', 'Proin volutpat dui eget lacinia lobortis.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Phasellus et velit mattis, finibus velit ut, luctus purus.', 'Phasellus et velit mattis, finibus velit ut, luctus purus.', 'Phasellus et velit mattis, finibus velit ut, luctus purus.', 'Integer et risus maximus, varius eros vel, venenatis libero.', 'Integer et risus maximus, varius eros vel, venenatis libero.', 'Integer et risus maximus, varius eros vel, venenatis libero.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Pellentesque condimentum dui ultricies justo dapibus imperdiet eget eget tortor.', 'Pellentesque condimentum dui ultricies justo dapibus imperdiet eget eget tortor.', 'Suspendisse faucibus erat a dolor fringilla suscipit.', 'Suspendisse faucibus erat a dolor fringilla suscipit.', 'Duis quis tortor convallis purus porttitor elementum.', 'Proin rutrum lacus sed elit convallis porttitor.', 'Proin rutrum lacus sed elit convallis porttitor.', 'Nunc sit amet felis ullamcorper, pulvinar augue sed, ullamcorper leo.', 'Nunc sit amet felis ullamcorper, pulvinar augue sed, ullamcorper leo.', 'Ut a erat eu lectus semper pulvinar.', 'Ut a erat eu lectus semper pulvinar.', 'Ut a erat eu lectus semper pulvinar.', 'Praesent congue velit at nulla finibus hendrerit.', 'Praesent congue velit at nulla finibus hendrerit.', 'Nullam ac erat convallis, suscipit purus quis, dictum eros.', 'Nullam ac erat convallis, suscipit purus quis, dictum eros.', 'Nullam ac erat convallis, suscipit purus quis, dictum eros.', 'Proin condimentum orci nec suscipit imperdiet.', 'Aliquam mattis mauris et turpis sodales tincidunt.', 'Aliquam mattis mauris et turpis sodales tincidunt.', 'Aliquam mattis mauris et turpis sodales tincidunt.', 'Vestibulum vel ante bibendum, interdum ipsum efficitur, porta massa.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Morbi nec lorem eu odio interdum feugiat id sed ligula.', 'Morbi nec lorem eu odio interdum feugiat id sed ligula.', 'Morbi nec lorem eu odio interdum feugiat id sed ligula.', 'Donec nec lorem vitae est consequat dictum.', 'Donec nec lorem vitae est consequat dictum.', 'Quisque vehicula quam eu pretium viverra.', 'Quisque vehicula quam eu pretium viverra.', 'Quisque vehicula quam eu pretium viverra.', 'Etiam luctus metus faucibus, vulputate augue et, luctus enim.', 'Etiam luctus metus faucibus, vulputate augue et, luctus enim.', 'Etiam luctus metus faucibus, vulputate augue et, luctus enim.', 'Nullam quis elit vitae enim bibendum viverra.', 'Donec consectetur nulla sit amet nulla blandit, sed auctor mi porttitor.', 'Donec consectetur nulla sit amet nulla blandit, sed auctor mi porttitor.', 'Suspendisse vel urna vitae massa mollis dignissim quis eu nulla.', 'Suspendisse vel urna vitae massa mollis dignissim quis eu nulla.', 'Vestibulum id risus fringilla nisl consectetur fringilla.', 'Vestibulum id risus fringilla nisl consectetur fringilla.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Sed feugiat orci pulvinar, imperdiet massa sit amet, semper dui.', 'Sed feugiat orci pulvinar, imperdiet massa sit amet, semper dui.', 'Sed feugiat orci pulvinar, imperdiet massa sit amet, semper dui.', 'Sed feugiat orci pulvinar, imperdiet massa sit amet, semper dui.', 'Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.', 'Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.', 'Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.', 'Cras vel urna fermentum, tempus magna ut, aliquet dolor.', 'Cras vel urna fermentum, tempus magna ut, aliquet dolor.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.']
0.029533967001043493
re_compile:
['Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Phasellus et velit mattis, finibus velit ut, luctus purus.', 'Integer et risus maximus, varius eros vel, venenatis libero.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse faucibus erat a dolor fringilla suscipit.', 'Ut a erat eu lectus semper pulvinar.', 'Ut a erat eu lectus semper pulvinar.', 'Praesent congue velit at nulla finibus hendrerit.', 'Nullam ac erat convallis, suscipit purus quis, dictum eros.', 'Aliquam mattis mauris et turpis sodales tincidunt.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Morbi nec lorem eu odio interdum feugiat id sed ligula.', 'Quisque vehicula quam eu pretium viverra.', 'Etiam luctus metus faucibus, vulputate augue et, luctus enim.', 'Suspendisse vel urna vitae massa mollis dignissim quis eu nulla.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.']
0.13305247199969017
in_set:
['Morbi congue lacus vitae dolor tempus, eu auctor elit interdum.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Pellentesque a ante eu ligula dictum lobortis.', 'Phasellus et velit mattis, finibus velit ut, luctus purus.', 'Integer et risus maximus, varius eros vel, venenatis libero.', 'Proin blandit dui vel ante blandit, et aliquet orci placerat.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse eu lacus non nunc accumsan congue non id velit.', 'Suspendisse faucibus erat a dolor fringilla suscipit.', 'Ut a erat eu lectus semper pulvinar.', 'Ut a erat eu lectus semper pulvinar.', 'Praesent congue velit at nulla finibus hendrerit.', 'Nullam ac erat convallis, suscipit purus quis, dictum eros.', 'Aliquam mattis mauris et turpis sodales tincidunt.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Duis finibus nisl et urna pharetra, non dignissim ante tempus.', 'Morbi nec lorem eu odio interdum feugiat id sed ligula.', 'Quisque vehicula quam eu pretium viverra.', 'Etiam luctus metus faucibus, vulputate augue et, luctus enim.', 'Suspendisse vel urna vitae massa mollis dignissim quis eu nulla.', 'Etiam ut risus ultrices, consequat sapien eu, rhoncus justo.', 'Donec nec metus quis nulla sagittis ullamcorper vitae eu ante.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Fusce non urna molestie massa sagittis accumsan et eget lorem.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.', 'Curabitur ac nisl at mauris pellentesque tincidunt nec sed magna.']
0.11130324300029315

如您所见，第一个解决方案非常快，但返回的结果太多，因为它忽略了子字符串上的“字边界”约束。其他解决方案是等效的（多次运行有时一个比另一个快，有时相反）<如果要测试的子字符串较少，则code>re_compile应该更快，否则如果要测试句子较少，则＜code>in_set

不知道karnesJ提出的Trie数据结构。但是如果你真的有很多元素，重新考虑你的算法是个好主意。