检查其他字符串中存在的加工字符串的有效方法

Question

我有一个关键字列表和另一个较长的字符串（2或3页）。我想找出关键字列表中的关键字。 e、 克

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) 然后从堆中的段落中搜索每个单词，时间复杂度将是O(n)。你知道吗

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

实现这一目标的有效方法是什么？你知道吗

一些关键字是n-grams

许多人没有考虑到这个限制就给出了解决方案。e、 纽约是一个关键词。拆分段落会将纽约和纽约拆分为不同的单词。在上面的注释中也提到了这一点。你知道吗

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}

注意：这是在python3中。如果在python2中希望删除标点符号，请参见this answer。你知道吗