如何检测长文本str2中是否包含模式串str1或相似内容？

你当前用滑动窗口+Levenshtein ratio的思路能实现需求，但存在效率瓶颈——每次计算窗口与模式串的编辑距离耗时较高，尤其当长文本str2规模较大时，整体时间复杂度会显著上升。以下是几个更优的替代方案：

1. 用Jaccard相似度（基于n-gram）替代编辑距离 #

Jaccard相似度通过字符n-gram的交集/并集比值计算相似度，计算速度远快于Levenshtein编辑距离，适合长文本场景。示例代码：

from sklearn.feature_extraction.text import CountVectorizer
import numpy as np

def jaccard_similarity(str_a, str_b, n=2):
    # 基于字符二元组构建特征
    vec = CountVectorizer(ngram_range=(n,n), analyzer='char')
    corpus = [str_a, str_b]
    X = vec.fit_transform(corpus)
    # 计算交集和并集的大小
    intersection = np.logical_and(X[0].toarray()[0], X[1].toarray()[0]).sum()
    union = np.logical_or(X[0].toarray()[0], X[1].toarray()[0]).sum()
    return intersection / union if union != 0 else 0

str1 = 'how to do this weird task'
str2 = 'once upon a time...and smth long'
window_len = len(str1)
max_sim = 0

for i in range(len(str2) - window_len + 1):
    window = str2[i:i+window_len]
    sim = jaccard_similarity(str1, window)
    if sim > max_sim:
        max_sim = sim

print(f"最高相似度: {max_sim}")

2. 用优化后的近似匹配库自动处理 #

fuzzywuzzy库的process.extractOne方法内置了子串匹配优化逻辑，无需手动维护滑动窗口，直接能找到str2中与str1最相似的片段，效率比手动实现更高：

from fuzzywuzzy import fuzz, process

str1 = 'how to do this weird task'
str2 = 'once upon a time...and smth long'

# 提取最相似的匹配结果，scorer指定用ratio算法
best_match = process.extractOne(str1, [str2], scorer=fuzz.ratio)
print(f"最高匹配度: {best_match[1]}, 匹配片段: {best_match[0]}")

3. 预过滤减少不必要的编辑距离计算 #

如果坚持使用Levenshtein ratio，可以先通过字符频率相似度过滤掉明显不匹配的窗口，只对有潜力的窗口计算编辑距离，降低整体计算量：

from Levenshtein import ratio
from collections import Counter

str1 = 'how to do this weird task'
str2 = 'once upon a time...and smth long'
window_len = len(str1)
str1_counter = Counter(str1)
max_ratio = 0
freq_threshold = 0.5  # 字符频率相似度阈值，可根据需求调整

def freq_similarity(counter_a, counter_b):
    all_chars = set(counter_a.keys()).union(set(counter_b.keys()))
    total_chars = sum(counter_a.get(c, 0) + counter_b.get(c, 0) for c in all_chars)
    if total_chars == 0:
        return 0
    # 计算字符频率的交集占比（Sørensen-Dice系数）
    intersection = sum(min(counter_a.get(c, 0), counter_b.get(c, 0)) for c in all_chars)
    return 2 * intersection / total_chars

for i in range(len(str2) - window_len + 1):
    window = str2[i:i+window_len]
    window_counter = Counter(window)
    # 频率相似度低于阈值则跳过
    if freq_similarity(str1_counter, window_counter) < freq_threshold:
        continue
    current_ratio = ratio(window, str1)
    if current_ratio > max_ratio:
        max_ratio = current_ratio

print(f"最高Levenshtein相似度: {max_ratio}")

内容的提问来源于stack exchange，提问作者anon.for