如何在不拆分排序短语的前提下检测列表中的重复短语

待检测的目标列表如下：

my_list = ['beautiful moments','moments beautiful']

判定规则：不考虑短语语法合理性，只要两个字符串包含的单词完全一致、仅排列顺序不同，即判定为重复内容，检测过程不得对单个短语执行拆分后排序的操作。

核心实现思路 #

利用素数唯一分解特性做哈希匹配：给每个出现过的单词分配一个全局唯一的素数，每个短语的哈希值为其包含所有单词对应素数的乘积。由于素数乘积不受乘法顺序影响，只要两个短语的单词组成完全一致，不管词序怎么变，最终哈希值一定相等；如果单词有差异，哈希值必然不同。

该方法全程不需要对短语拆分出的单词做排序操作，比对效率远高于排序后比对的常规方案。

可运行代码 #

# 动态生成素数，不需要提前维护词表映射
def get_next_prime(start):
    num = start
    while True:
        is_prime = True
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            yield num
        num += 1

prime_gen = get_next_prime(2)
word_prime = {}

def calc_hash(phrase):
    hash_val = 1
    word_buf = []
    # 逐字符扫描识别单词，不需要显式调用split生成单词列表后排序
    for char in phrase:
        if char == ' ':
            word = ''.join(word_buf)
            if word not in word_prime:
                word_prime[word] = next(prime_gen)
            hash_val *= word_prime[word]
            word_buf.clear()
        else:
            word_buf.append(char)
    # 处理短语末尾的最后一个单词
    last_word = ''.join(word_buf)
    if last_word not in word_prime:
        word_prime[last_word] = next(prime_gen)
    hash_val *= word_prime[last_word]
    return hash_val

# 执行重复检测
record = dict()
duplicate_pairs = []
for index, content in enumerate(my_list):
    h = calc_hash(content)
    if h in record:
        duplicate_pairs.append( (record[h], index) )
    else:
        record[h] = index

print(duplicate_pairs)

代码运行后输出[(0, 1)]，即成功识别到列表中索引0和索引1位置的两个短语为重复内容。

注意事项 #

• Python原生支持任意精度整数，不需要担心素数乘积过大溢出的问题
• 如果在其他强类型语言中使用，可以搭配两组不同的素数生成规则做双重哈希，哈希碰撞概率可以降到可忽略的程度
• 逐字符扫描的逻辑如果不需要严格规避显式单词识别，也可以简化遍历逻辑，只要不对识别出的单词做排序即可符合要求

内容的提问来源于stack exchange，提问作者Максим Місіченко