Python序列匹配算法实现：长重复短语统计需求

给定以下句子列表：

errList = [ 
    'Ragu ate lunch but didnt have Water for drinks', 
    'Rams ate lunch but didnt have Gatorade for drinks', 
    'Saya ate lunch but didnt have :water for drinks', 
    'Raghu ate lunch but didnt have water for drinks', 
    'Hanu ate lunch but didnt have -water for drinks', 
    'Wayu ate lunch but didnt have water for drinks', 
    'Viru ate lunch but didnt have .water 4or drinks', 
    'kk ate lunch & icecream but did have Water for drinks', 
    'M ate lunch &and icecream but did have Gatorade for drinks', 
    'Parker ate lunch icecream but didnt have :water for drinks', 
    'Sassy ate lunch and icecream but didnt have water for drinks', 
    'John ate lunch and icecream but didnt have -water for drinks', 
    'Pokey ate lunch and icecream but didnt have Water for drinks', 
    'Laila ate lunch and icecream but did have water 4or drinks', 
]

需要统计列表中每个句子里长度超过2个单词的最长短语的出现次数（严格区分大小写），示例输出参考如下：

{ 
    'ate lunch but didnt have': 7, 
    'water for drinks': 7, 
    'ate lunch and icecream': 4, 
    'didnt have water': 3, 
    'didnt have Water': 2  # 区分大小写
}

要求：禁止使用re模块，属于序列匹配范畴，可基于nltk或scikit-learn实现。

结合你的NLP和scikit-learn基础，我给你梳理两种可行的实现思路：

方案一：使用NLTK生成Ngrams统计 #

NLTK的ngrams工具可以轻松生成连续的单词短语，步骤如下：

1. 准备工作 #

先确保安装并导入NLTK相关模块：

from nltk.util import ngrams
from collections import defaultdict

2. 遍历句子生成所有长短语 #

我们会遍历每个句子，按空格分割成单词序列，然后生成所有长度≥3的连续短语，同时统计每个短语的出现次数：

phrase_counts = defaultdict(int)

for sentence in errList:
    # 按空格分割句子为单词列表（保留原格式，包括特殊字符）
    words = sentence.split()
    sentence_length = len(words)
    # 生成所有长度从3到句子总长度的连续短语
    for phrase_length in range(3, sentence_length + 1):
        # 生成当前长度的所有连续短语
        for gram in ngrams(words, phrase_length):
            phrase = ' '.join(gram)
            phrase_counts[phrase] += 1

3. 整理输出结果 #

按出现次数降序排序后，即可得到类似示例的结果：

# 按次数从高到低排序
sorted_results = sorted(phrase_counts.items(), key=lambda x: x[1], reverse=True)
# 转换为字典格式
final_result = dict(sorted_results)
print(final_result)

方案二：使用Scikit-learn的CountVectorizer统计 #

如果你更熟悉scikit-learn，CountVectorizer可以高效处理短语统计，而且不需要手动遍历生成ngrams：

1. 导入模块并配置参数 #

我们需要自定义分词规则，确保保留原大小写和特殊字符，同时指定ngram的长度范围：

from sklearn.feature_extraction.text import CountVectorizer
from collections import defaultdict

2. 拟合数据并统计短语 #

# 配置CountVectorizer：ngram范围3到任意长度，不转小写，按非空白字符分词（即保留原单词格式）
vectorizer = CountVectorizer(
    ngram_range=(3, None),
    lowercase=False,
    token_pattern=r'\S+'  # 确保特殊字符和连字符的单词被完整保留
)

# 拟合句子列表，生成词频矩阵
phrase_matrix = vectorizer.fit_transform(errList)

# 提取短语和对应的出现次数
phrase_counts = dict(
    zip(
        vectorizer.get_feature_names_out(),
        phrase_matrix.sum(axis=0).tolist()[0]
    )
)

3. 排序输出 #

同样按次数降序整理结果：

sorted_results = sorted(phrase_counts.items(), key=lambda x: x[1], reverse=True)
final_result = dict(sorted_results)
print(final_result)

补充说明 #

• 两种方案都严格遵循了“禁止使用re模块”的要求，完全基于序列匹配实现
• 结果会区分大小写和特殊字符（比如:water和water会被视为不同单词，对应的短语也会分开统计）
• 如果你需要只保留每个句子的最长短语（而不是所有长短语），可以在遍历句子时先找到当前句子的最长短语长度，只统计该长度的短语，修改起来也很简单：

  # 以NLTK方案为例，修改遍历逻辑
  phrase_counts = defaultdict(int)
  for sentence in errList:
      words = sentence.split()
      n = len(words)
      # 从最长可能的短语长度开始找（最小3）
      max_phrase_len = n
      while max_phrase_len >=3:
          # 生成当前长度的所有短语
          current_phrases = [' '.join(words[i:i+max_phrase_len]) for i in range(n - max_phrase_len +1)]
          if current_phrases:
              # 统计这些最长短语
              for p in current_phrases:
                  phrase_counts[p] +=1
              break  # 找到最长长度后停止，不再处理更短的短语
          max_phrase_len -=1
  

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