字符串序列相似度计算与高频序列提取最佳实现方案

原有代码问题说明 #

• 未对>分隔的字符串做拆分处理，直接将整串转为数组比对，实际是判断两条序列是否完全一致，而非逐位置匹配元素
• 仅统计了匹配元素的计数，未做归一化换算为百分比值
• 缺失高频序列统计的逻辑

完整实现步骤 #

• 第一步：预处理序列数据
  首先将每条字符串按分隔符拆分为元素列表，统一序列长度基准：

import numpy as np
from collections import Counter

# 按>拆分每条序列，若不需要统计固定相同的末尾元素，可在split后加[:-1]剔除最后一位
seq_processed = [s.split(">") for s in transition]
single_seq_length = len(seq_processed[0])
total_seq_num = len(seq_processed)

• 第二步：计算相似度百分比矩阵
  提供两种实现，小数据集用循环版本易读，大数据集用向量化版本性能更好：

相似度百分比规则：两条序列对应位置相等的元素数 / 单条序列总长度 * 100

# 版本1：易读循环版
sim_matrix = np.zeros((total_seq_num, total_seq_num))
for i in range(total_seq_num):
    s1 = seq_processed[i]
    for j in range(i, total_seq_num):
        s2 = seq_processed[j]
        match_cnt = sum(e1 == e2 for e1, e2 in zip(s1, s2))
        sim_val = (match_cnt / single_seq_length) * 100
        sim_matrix[i, j] = sim_matrix[j, i] = sim_val

# 版本2：大数据量向量化提速版
seq_array = np.array(seq_processed)
sim_matrix = (seq_array[:, None] == seq_array[None, :]).mean(axis=-1) * 100

需要获取第k条序列和其他所有序列的相似度百分比，直接取sim_matrix[k]即可，返回数组的第m位就是第k条和第m条的相似度值。

• 第三步：提取最高频序列
  直接统计原始序列的出现频次即可：

seq_counter = Counter(transition)
# 返回值为(最高频序列内容, 出现次数)
top_seq, top_count = seq_counter.most_common(1)[0]

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