如何高效检测长文本中包含的n-gram类关键词？

Great question—this is a common pain point when dealing with multi-word keywords, since the naive substring check gets slow fast, and single-word-focused structures like heaps don’t work for phrases. Let’s break down the best approaches here:

1. Aho-Corasick Automaton (Best for Large Keyword Lists) #

The Aho-Corasick algorithm is built exactly for this scenario: matching multiple patterns (including multi-word phrases) against a text in linear time relative to the total length of all patterns plus the text length. It’s way more efficient than the O(m*n) list comprehension approach, especially as your keyword list grows.

Implementation with pyahocorasick #

First, install the optimized library:

pip install pyahocorasick

Then here’s how to use it:

import ahocorasick

def find_multiword_keywords(keywords, text):
    # Initialize the automaton
    A = ahocorasick.Automaton()
    
    # Add all keywords to the automaton, storing the keyword itself as a value
    for idx, keyword in enumerate(keywords):
        A.add_word(keyword, (idx, keyword))
    
    # Prepare the automaton for fast searching
    A.make_automaton()
    
    # Collect all unique matches (avoid duplicates if a keyword appears multiple times)
    matches = set()
    for end_index, (idx, keyword) in A.iter(text):
        matches.add(keyword)
    
    return list(matches)

# Example usage
keywords = ["New York", "machine learning", "data science", "Big Apple"]
paragraphs = """New York, often called the Big Apple, is a hub for machine learning and data science initiatives. Many tech companies in New York focus on applying machine learning to real-world problems."""

present_keywords = find_multiword_keywords(keywords, paragraphs)
print(present_keywords)
# Output: ['New York', 'Big Apple', 'machine learning', 'data science']

Key Notes: #

• Case Insensitivity: If you need matches regardless of case, convert both keywords and text to lowercase before processing (e.g., keyword.lower() and text.lower()).
• Punctuation Handling: If punctuation breaks matches (like "New York," vs "New York"), preprocess the text to strip or normalize punctuation first (use string.punctuation to remove non-alphanumeric characters).
• Overlapping Matches: The algorithm will catch all overlapping phrases (e.g., both "New York" and "New York City" will be matched if present in the text).

2. N-Gram Generation + Set Lookup (Simpler for Smaller Keyword Lists) #

If your keyword list isn’t massive, another approach is to generate all possible n-grams from the text (where n matches the word count of your multi-word keywords) and check against a set of keywords. This avoids the O(m*n) loop by leveraging O(1) set lookups.

Implementation: #

import string
from nltk.tokenize import word_tokenize # Install first: pip install nltk

def preprocess_text(text):
    # Remove punctuation and convert to lowercase for consistent matching
    text = text.translate(str.maketrans('', '', string.punctuation)).lower()
    return word_tokenize(text)

def find_keywords_via_ngrams(keywords, text):
    tokenized_text = preprocess_text(text)
    keyword_set = {k.lower() for k in keywords}
    # Get all unique word counts from your keywords (e.g., 2 for "New York", 3 for "machine learning model")
    keyword_lengths = {len(k.split()) for k in keywords}
    
    matches = set()
    for n in keyword_lengths:
        # Generate every possible n-gram from the tokenized text
        for i in range(len(tokenized_text) - n + 1):
            ngram = ' '.join(tokenized_text[i:i+n])
            if ngram in keyword_set:
                matches.add(ngram.title()) # Adjust casing to match original keywords if needed
    
    return list(matches)

# Example usage (same keywords and text as before)
present_keywords = find_keywords_via_ngrams(keywords, paragraphs)
print(present_keywords)
# Output: ['New York', 'Big Apple', 'Machine Learning', 'Data Science']

Pros & Cons: #

• Pros: Simpler to customize preprocessing logic, no need for specialized automaton libraries if you handle tokenization yourself.
• Cons: Less efficient for large keyword lists or very long texts, since you’re generating all possible n-grams upfront.

Why Your Initial Approaches Fall Short #

• List Comprehension: The [x for x in keywords if x in paragraphs] approach checks every keyword against the entire text, leading to O(m*n) time complexity—this gets painfully slow as your keyword list grows beyond a few hundred entries.
• Heap-Based Search: Heaps are great for single-word lookups, but they can’t handle multi-word phrases because they rely on sorting individual tokens, not preserving the order and sequence of words in a phrase.

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