优化名词短语列表内Token分数求和代码的时间复杂度

需求 #

• 现有代码时间复杂度较高，需优化；同时原代码未正确处理名词短语需连续出现的要求，需一并修正。

代码目标 #

当token属于nounphrase_list中的名词短语（需满足短语内词汇按顺序连续出现），且未被处理过时，将该短语内所有token的分数更新为短语内各token原始分数的总和。

原始代码 #

full_string = ["Mitchell is using machine learning and software engineering on his mobile phone to generate songs . On top of machine learning he is also using deep learning"]

# 该token列表来自上述full_string
all_tokens = ["Mitchell", "is", "using", "machine", "learning", 
              "and", "software", "engineering", "on", "his", 
              "mobile", "phone", "to", "generate", "songs", 
              "On", "top", "of", "machine", "learning", 
              "he", "is", "also", "using", "deep", "learning"]

all_scores = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]

# 这些名词短语从full_string中提取
nounphrase_list = ["Mitchell", "machine learning", "software engineering", "machine learning", "deep learning"]

updated_scores = all_scores.copy()

seen_indices = set()
for np_item in nounphrase_list:
    np_words = np_item.split()
    indices = []
    for word in np_words:
        for idx, token in enumerate(all_tokens):
            if word == token:
                if idx not in seen_indices:
                    indices.append(idx)
                    seen_indices.add(idx)
                    break
    sum_score = sum(all_scores[idx] for idx in indices)
    for idx in indices:
        updated_scores[idx] = sum_score

预期逻辑说明 #

• Mitchell是单个词短语，对应分数1，更新后仍为1
• 首次出现的machine learning（对应索引3、4），原始分数为4+5=9，因此这两个位置的分数均更新为9
• 首次出现的software engineering（对应索引6、7），原始分数7+8=15，两个位置分数均更新为15
• 下一个machine learning（对应索引18、19），原始分数19+20=39，两个位置分数均更新为39
• 最后一个deep learning（对应索引24、25），原始分数25+26=51，两个位置分数均更新为51

原始代码问题分析 #

1. 时间复杂度高：嵌套循环导致时间复杂度为O(MKN)，其中M是名词短语数量，K是短语平均长度，N是token总数，数据量大时效率极低。
2. 逻辑错误：未检查短语内词汇是否连续出现，仅匹配单个词的第一个未使用索引，不符合需求中“短语需连续”的要求。

优化方案 #

思路 #

1. 预构建token位置映射：用字典记录每个token的所有未被处理的索引，方便快速查找。
2. 连续短语匹配：对于多词短语，从第一个词的候选索引出发，检查后续位置是否匹配短语的下一个词，确保连续性。
3. 标记已处理索引：找到符合条件的短语索引后，立即从映射中移除这些索引，避免重复处理。

优化后代码 #

full_string = ["Mitchell is using machine learning and software engineering on his mobile phone to generate songs . On top of machine learning he is also using deep learning"]

all_tokens = ["Mitchell", "is", "using", "machine", "learning", 
              "and", "software", "engineering", "on", "his", 
              "mobile", "phone", "to", "generate", "songs", 
              "On", "top", "of", "machine", "learning", 
              "he", "is", "also", "using", "deep", "learning"]

all_scores = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]

nounphrase_list = ["Mitchell", "machine learning", "software engineering", "machine learning", "deep learning"]

updated_scores = all_scores.copy()

# 预构建每个token的未处理索引队列
from collections import defaultdict
token_indices = defaultdict(list)
for idx, token in enumerate(all_tokens):
    token_indices[token].append(idx)

for np_item in nounphrase_list:
    np_words = np_item.split()
    phrase_length = len(np_words)
    if phrase_length == 0:
        continue
    
    first_word = np_words[0]
    if first_word not in token_indices or not token_indices[first_word]:
        continue
    
    # 寻找连续匹配的短语索引
    found_indices = None
    # 遍历第一个词的候选索引
    for candidate_idx in list(token_indices[first_word]):
        current_indices = []
        match = True
        for i in range(phrase_length):
            current_pos = candidate_idx + i
            if current_pos >= len(all_tokens) or all_tokens[current_pos] != np_words[i]:
                match = False
                break
            current_indices.append(current_pos)
        if match:
            found_indices = current_indices
            break
    
    if found_indices is None:
        continue
    
    # 计算并更新分数
    sum_score = sum(all_scores[idx] for idx in found_indices)
    for idx in found_indices:
        updated_scores[idx] = sum_score
    
    # 移除已处理的索引
    for idx, word in zip(found_indices, np_words):
        if idx in token_indices[word]:
            token_indices[word].remove(idx)
            if not token_indices[word]:
                del token_indices[word]

print(updated_scores)

优化效果 #

• 时间复杂度降低：预构建映射为O(N)，处理每个短语的时间为O(K)（K为短语长度），整体时间复杂度为O(N + MK)，远低于原始的O(MK*N)。
• 逻辑修正：严格检查短语内词汇的连续性，完全符合需求要求。
• 效率提升：避免重复遍历整个token列表，通过字典快速定位候选索引，减少不必要的计算。

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