Python密码破解爬山算法：按消息去重后按ngram count排序

需求概述 #

我用Python实现爬山算法破解简单替换密码，算法生成的输出列表结构如下，每个子列表包含ngram计数、解密消息和映射字母表：

output = [[10, 'HELLO', 'ABCD'], [10, 'HELLO', 'ABDC'], [18, 'HLELO', 'BCDA']]

需要对输出做以下处理：

• 按解密消息去重：不同字母表可能生成相同消息，每个消息仅保留一份（字母表可保留任意一个，因为仅前N个有效，N为密文中的唯一字母数量）
• 按ngram计数排序：按计数数值排序，取最接近英语频率分布的前200个结果（计数越小代表匹配度越高）
• 保留完整字母表：即使字母表后段是未使用的补全字母，也要完整保留（仅前N个用于密钥恢复）

补充背景 #

• 针对简单替换密码（单字母映射，如a→h、b→x）
• 短明文的密文不会包含全部26个字母，处理时会将密文中的唯一字母放在字母表前端，剩余字母补全；算法仅使用字母表的前N个字母（N为密文唯一字母数）生成映射，因此后段字母不同但前段相同的字母表会生成完全一致的明文和ngram计数

实现代码 #

以下是处理输出列表的Python代码：

def process_crack_results(output_list, top_n=200):
    # 1. 按消息去重：用字典存储，键为消息，值为对应的[ngram计数, 字母表]
    unique_messages = {}
    for count, msg, alphabet in output_list:
        # 优先保留计数更小（更优）的结果，若消息未记录则直接存入
        if msg not in unique_messages or count < unique_messages[msg][0]:
            unique_messages[msg] = [count, alphabet]
    
    # 2. 按ngram计数升序排序，计数越小越接近英语频率分布
    sorted_results = sorted(unique_messages.items(), key=lambda x: x[1][0])
    
    # 3. 转换为原输出格式，截取前top_n个结果
    processed_output = [[item[1][0], item[0], item[1][1]] for item in sorted_results[:top_n]]
    
    return processed_output

# 示例使用
output = [[10, 'HELLO', 'ABCD'], [10, 'HELLO', 'ABDC'], [18, 'HLELO', 'BCDA']]
result = process_crack_results(output)
print(result)
# 输出: [[10, 'HELLO', 'ABCD'], [18, 'HLELO', 'BCDA']]

代码说明 #

• 去重逻辑：用字典确保每个消息仅存最优条目，若不需要优先保留更优结果，也可直接覆盖或保留首次出现的条目
• 排序逻辑：按ngram计数升序排列，计数越小说明解密结果的ngram分布越贴近标准英语
• 结果截取：最终返回前200个最优结果，格式与原输出列表完全一致

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