python - 检查另一个字符串中存在的匹配字符串的有效方法

Question

我有一个关键字列表和另一个更长的字符串(2 或 3 页)。我想找出关键字列表中存在的关键字。例如

Keywords = [k1, k2, k3 k4, k5, k6 k7 k8]
paragraphs = "This will be 2 to4 page article"

一个简单的方法是

present_keywords = [x for x in keywords if x in paragraphs]

上述算法的时间复杂度为O(m*n) =~ O(n^2)

另一种方式我可以创建关键字列表堆，时间复杂度:O(n log n)然后在 Heap 中搜索段落中的每个单词，时间复杂度为 O(n)。

Note: The keywords are bi-grams, tri-grams as well so second approach will not work.

实现这一目标的有效方法是什么？

一些关键词是n-gram

许多人在没有考虑这个约束的情况下给出了解决方案。例如，New York 是一个关键字。拆分段落会将 New 和 York 拆分为不同的词。在上面的注释中也提到了这一点。

Answer 1

为了降低时间复杂度，我们可以增加空间复杂度。通过keywords并将它们散列到一个 set() 中，假设每个关键字都是唯一的(如果不是，重复项将被删除)。

然后你可以通过paragraph并创建一个、两个或三个单词短语，检查它们的存在并在任何这些短语出现在 hashedKeywords 中时增加它们的计数。 .时间复杂度为 O(m+n) =~ O(n)，但空间复杂度为 O(1) 到 O(n)。

import string # for removing punctuation

# Sample input with bigrams and trigrams in keywords
paragraphs = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."
keywords = ['magna', 'lorem ipsum', 'sed do eiusmod', 'aliqua']

# Hash keywords into set for faster look up
hashedKeywords = set()
for keyword in keywords:
    hashedKeywords.add(keyword)

# Strip punctuation from paragraph phrases using translate() and make it case insensitive using lower()
table = str.maketrans({key: None for key in string.punctuation})
wordsInParagraphs = [w.translate(table).lower() for w in paragraphs.split()]

# Initialize for loop
maxGram = 3
wordFrequency = {}

# Loop through words in paragraphs but also create a small list of one, two, or three word phrases. 

for i in range(len(wordsInParagraphs)):
    # List slicing ensures the last word and second to last word will produce a one and two string list, respectively (since slicing past the length of the list will simply return a list up to the last element in Python)
    phrases = wordsInParagraphs[i:i+maxGram] # e.g. ['lorem', 'ipsum', 'dolor']

    # Loop through the one, two, and three word phrases and check if phrase is in keywords
    for j in range(len(phrases)):
        phrase = ' '.join(phrases[0:j+1]) # Join list of strings into a complete string e.g. 'lorem', 'lorem ipsum', and 'lorem ipsum dolor'
        if phrase in hashedKeywords:
            wordFrequency.setdefault(phrase , 0)
            wordFrequency[phrase] += 1
print(wordFrequency)

输出:

{'lorem ipsum': 1, 'sed do eiusmod': 1, 'magna': 1, 'aliqua': 1}

注意:这是在 Python 3 中。如果在 Python 2 中并希望删除标点符号，请参阅 this answer .