如何高效检查大规模关键词子列表的所有元素是否存在于目标字符串

Let's start by breaking down why your initial code hits performance walls with 100k+ keyword sublists: right now, for every single sublist, you're scanning the entire target string multiple times (once per keyword in the sublist). That's a ton of redundant work—like rereading a book 100k times just to check if different sets of words are in it. We can fix this by shifting the heavy lifting to a single preprocessing step.

The Core Idea: Preprocess Once, Query Fast #

Instead of rechecking the target string for every keyword, we'll extract all relevant information from the string once, then use fast lookups to validate each sublist. The exact approach depends on whether you need exact word matches or substring matches (your original code uses substring checks, so we'll cover both scenarios).

Option 1: Exact Word Matching (Best for Whole-Word Checks)

If you're looking for exact word matches (e.g., "andrew" should match "Andrew" but not "Andrews"), first we'll clean the target string into a set of lowercase words (stripping punctuation). Set lookups are O(1), so checking each sublist becomes lightning fast.

import re

my_string = 'My name is Andrew, I am pretty awesome'
# Extract all lowercase words, removing punctuation
target_words = set(re.findall(r'\b\w+\b', my_string.lower()))

keywords = [['andrew', 'name', 'awesome'], ['andrew', 'designation', 'awesome']]
results = []

for sublist in keywords:
    # Check if every keyword in the sublist exists in our preprocessed set
    if all(keyword in target_words for keyword in sublist):
        results.append(sublist)

print(results)  # Output: [['andrew', 'name', 'awesome']]

This cuts the per-sublist check from O(M * L) (where L is the string length) down to O(M) (M = average sublist length). For 100k sublists, this is a night-and-day difference in speed.

Option 2: Substring Matching (For Partial Matches)

If you need to allow partial matches (like "drew" matching "Andrew"), the Aho-Corasick algorithm is perfect—it lets you find all your keywords in the target string in a single pass. We can use the pyahocorasick library to implement this easily:

First install the library:

pip install pyahocorasick

Then the code:

import ahocorasick

my_string = 'My name is Andrew, I am pretty awesome'
lower_string = my_string.lower()

# Collect all unique keywords from all sublists to avoid redundant work
all_unique_keywords = set()
keywords = [['andrew', 'name', 'awesome'], ['andrew', 'designation', 'awesome']]
for sublist in keywords:
    all_unique_keywords.update(sublist)

# Build the Aho-Corasick automaton
automaton = ahocorasick.Automaton()
for idx, keyword in enumerate(all_unique_keywords):
    automaton.add_word(keyword, (idx, keyword))
automaton.make_automaton()

# Find all keywords present in the target string (single pass!)
present_keywords = set()
for _, (_, keyword) in automaton.iter(lower_string):
    present_keywords.add(keyword)

# Now filter the sublists using our precomputed set
results = [sublist for sublist in keywords if all(key in present_keywords for key in sublist)]
print(results)  # Output: [['andrew', 'name', 'awesome']]

This approach processes the target string once, then validates each sublist with O(M) checks. The total time complexity is O(L + K + N*M), where L is the string length, K is the number of unique keywords, and N is the number of sublists—way more scalable for large datasets.

Extra Tips for Even More Speed #

• Deduplicate Sublists: If you have duplicate sublists, convert them to tuples (since lists can't be hashed) and deduplicate first:

  keywords = list(set(tuple(sublist) for sublist in keywords))
  

  This avoids checking the same sublist multiple times.
• Parallel Processing: For extremely large N (millions of sublists), you can use multiprocessing to split the sublist filtering across CPU cores—just be aware that this adds some overhead, so it's only worth it for very big datasets.

内容的提问来源于stack exchange，提问作者suzee