Page 383 - 《软件学报》2025年第9期

4294 软件学报 2025 年第 36 卷第 9 期

达到局部最优效果且具有较强的可解释性, 并且方法的参数较少. 为了确定最优的 k 值 (聚类数), 我们使用轮廓系
数 Silhouette Coefficient 以评估不同 k 值下的聚类性能. 轮廓系数综合考虑聚类的密集程度及分离程度, 为每个样
本提供一个度量, 其计算公式如下:

b(i)−a(i)
s(i) = (1)
max{a(i), b(i)}
其中, a(i) 代表第 i 个样本与同一聚类簇下其他样本的平均距离, b(i) 代表第 i 个样本与最近邻聚类簇中样本的平
均距离, 整个聚类结果的轮廓系数为所有样本轮廓系数的平均值. 度量的范围是−1 至 1, 数值越大说明样本点所在
簇与相邻簇之间的距离越远, 聚类的效果越好. 由于轮廓系数只有在标签数大于 1 且小于样本数时有效, 因此对
于 S 种结构, NCQT 设置 k 在范围 [2, S−1] 内依次进行 K-means 聚类, 并计算每次聚类的轮廓系数, 选取分数最高
的作为最终的聚类结果.

3.1.3 分 组
分组的主要目的是提高神经网络压缩的效果和效率. 在同等规模的数据上, 基于神经网络的压缩方法相较于
传统压缩方法带来了更大的时间开销. 通过分组将原本大文件分割为多个更小的文件, 可以实现并行数据压缩, 进
而提高压缩的效率. 此外, 为了平衡压缩时间和效果, 基于神经网络的压缩方法大多采用单层或少数几层的网络结
构, 当追踪的种类较多时, 神经网络难以充分学习不同追踪的数据特征, 导致预测准度下降. 基于前文聚类的结果,
将结构相似的追踪数据聚集在一个数据块中作为压缩和解压的最小单元, 有助于神经网络更好地学习和预测局部
数据特征.
分组的另一个目的是提高查询的效率. 现有的压缩方法在解压时通常需要按照编码时的顺序依次解码数据,
而将数据进行分组赋予了从不同位置开始解压数据的灵活性. 在搜索阶段, 只有包含满足查询条件的追踪数据的
分组需要被解压, 有效地降低了搜索过程中所需解压的数据量. 同时, 利用聚类结果进行分组可以将具有相似特征
的追踪数据聚集在一起, 提高了目标数据在相同或相邻分组的概率, 进而减少了需要解压的分组数量.
分组方法优先聚集拥有相同结构的追踪数据, 其次将根据聚类簇将结构相似的追踪数据分在同一组或相邻
组. 具体而言, NCQT 首先将分组大小设置为每组 L 条追踪, 然后按照聚类结果对所有结构进行排序, 最后按照排
序结果重新组织追踪数据, 每 L 条数据切分为一个分组. 分组完成后, NCQT 将每个分组所含追踪的 ID 列表、结
构列表以及开始时间列表记录为该分组的索引字典, 以便搜索时快速判断分组中是否存在满足查询条件的数据,
并定位其在分组中的位置.

3.2 编码器获取和数据压缩
NCQT 采用半自适应性神经网络压缩方法. 首先, 模型利用部分输入序列进行训练, 训练后的模型将作为压缩
阶段的初始模型. 在压缩过程中, 模型动态更新参数, 并利用所产生的概率估计作为算术编码的输入, 用于生成压
缩文件. 在前文的预处理阶段, 跨度数据已经从自然语言文本转换为由数字组成的列表, 我们使用特殊数字作为跨
度的分隔符, 将追踪数据编码为取值范围在 [0, 22] 之间的一维列表. 这种设计使得模型能够更加高效地处理追踪
数据, 并在压缩时提供更好的性能.

3.2.1 编码器
理论上, 所有可以处理序列数据的网络结构都可以作为用于文本压缩的模型. 在本文的实现中, 我们参考
TRACE [33] 和 DZip [27] 的工作, 选择了 Transformer 和 GRU 两种网络结构作为可选的编码器. 图 7(a) 显示了以
Transformer 作为编码器时的网络设计. 传统的 Transformer 通常由多层编码器和解码器组成, 用于提取自然语言
序列中的高级语义特征 [48] . 然而我们实践发现, 只需要单层编码器进行压缩就可以获得较高预测准确率, 而且并
没有引入更多的时间成本. NCQT-Transformer 的网络结构包括单层 Transformer, 一个全连接层, 以及最后用于输
出预测概率的 SoftMax 层. 其中, Transformer 层由多头注意力以及全连接的前馈神经网络组成. 图 7(b) 则展示了
以 GRU 作为编码器时的网络结构, 模型包括两个双向门控循环单元、多个线性层以及最后的 SoftMax 层. 模型的
输入序列经过双向门控循环单元后首先被堆叠并扁平化为一个向量, 然后分别输入到两个线性层中, 其中左侧带