基于替换错误的相似片段查找

Similar Fragment Queries Based on Substitution Errors

摘要: 破译未知语言的关键是寻找相似的字母片段序列。本文针对相似片段的查找，编写了一种新的算法。首先建立索引结构，多次间隔划分得到片段。然后基于海明距离建立相似公式和相似矩阵用于表示两个片段之间的相似度。结合实际，在大量文本记录时发生替换错误的基础下建立相似阈值公式，并通过该公式判断是否为要求查找的相似片段。最后获得了多段文本的相似片段以及其对应的位置。此外使用平均准确率评价算法，经分析和实验表明，该算法有较高的准确率和查找效率。

Abstract: The key to deciphering an unknown language is to look for similar sequences of letter fragments. In this paper, a new algorithm for finding similar fragments is developed. First, the index structure is built and the fragments are divided at intervals. Then the similarity formula and the similarity matrix are established based on the hamming distance to represent the similarity between the two fragments. In combination with practice, the similarity threshold formula is established on the basis of substitution errors in a large number of text records, and the formula is used to judge whether it is the similar fragment to be searched. Finally, the similar fragments of multiple text and their corresponding positions are obtained. In addition, the average accuracy evaluation algorithm is used, and the analysis and experiments show that the algorithm has good accuracy and search efficiency.

1. 引言

破译某种未知语言的关键是寻找一段相似的字母序列片段，因为这些片段很可能具备某种固定含义，类似词汇或词根。对照查找相似片段序列的算法，通常采用的方法是先引入特定的索引结构，如后缀树、后继数组等 [1] [2]。基于这些索引结构的算法不仅计算量大，而且要求索引结构模式的首字母必须相同，效率有待提高且局限性较大。因此本文提出一种新的索引结构，优先考虑计算的复杂度，计算海明距离并根据阈值划分，在此基础上编写一种新的算法。该算法适用于查找首字母不同的未知语言字母序列的相似片段，经分析和实验表明，该算法可以得到较好的查找结果且有较优的查找效率。

2. 数据来源和模型假设

下载英文版《双城记》，将里面的字母装换成大写，删去标点符号以及字母U到Z，造出研究未知语言的基础文本数据。为了简化，作以下假设：1) 未知语言由A到T这20个大写字母组成；2) 文本在获取过程中，有一些位置发生了替换错误，即某个字母被篡改成了其他字母；3) 文本在获取过程中只将替换错误纳入考虑范围，不考虑丢失了某个字母或增加了原本不存在的字母；4) 文本中各种字母出现的可能性符合一般规律。

3. 相似片段的获得以及位置的记录

3.1. 建立索引结构

对于某段长度为m的文本，用 $Z_i=z_1,z_2,\cdots ,z_d\left(1\le i\le n\right)$ 的字符串表示其中的相似片段， $Z_i$ 称为一个模式。根据模式长度d进行d次划分，每次划分从文本的第i个位置间隔d取字符，组成的字符串即为 $Z_i$。按照这样的规则划分得到片段，构造出元胞划分矩阵和划分行向量。其中元胞划分矩阵T的维度为 $d\times \left(m-i+1\right)/d$，T的每一个元素为一个长度是d的模式片段；划分行向量H的维度为 1 × n ，T的非空元素按行依次存放到H中。

本文获得了30段长度在5000~8000个字母范围的文本，片段的模式长度为15。元胞划分矩阵如表1所示。

3.2. 基于海明距离建立相似矩阵

建立相似公式和相似矩阵：

Table 1. The cellular partition matrix of a text

表1. 一段文本的元胞划分矩阵

海明距离是两个等长字母片段之间对应位置的不同字符个数。对于长度d的两个片段x和y，它们的海明距离为l，那么相似公式 [3] 为

${\gamma }_{xy}=\frac{d-l}{d}$ (1)

相似公式可以求出任意两个片段的相似度，将结果用相似矩阵表示。任意一个片段与它本身的相似度为1，在这里的目的是找到达到相似阈值的片段，则相似矩阵R是主对角线为0的对称矩阵。相似矩阵构造过程示意图如图1所示。

$R=\left(\begin{array}{ccc}0& \cdots & {\gamma }_{1n}\\ ⋮& \ddots & ⋮\\ {\gamma }_{1n}& \cdots & 0\end{array}\right)$ (2)

Figure 1. Schematic diagram of similar matrix construction process

图1. 相似矩阵构造过程示意图

本文获得了30段文本的相似矩阵，如表2所示。

Table 2. A matrix of similarity for a piece of text

表2. 一段文本的相似矩阵

3.3. 基于替换错误建立相似阈值公式

对于任意一个片段，最多出现的替换错误的字母个数为e，那么相似阈值公式为

${\gamma }_{阈}=\frac{d-e}{d}$ (3)

基于相似阈值对相似矩阵进行逻辑判断

$\{\begin{array}{c}{\gamma }_{xy}\ge {\gamma }_{阈},赋值为1\\ {\gamma }_{xy}<{\gamma }_{阈},赋值为0\end{array}$ (4)

从而得到对应的0-1矩阵，按列相加该矩阵中的元素得到一个行向量，该行向量的第x个元素表示在最多只会出现e个字母的替换错误的情况下，与片段x相似的片段个数。由此可以得到一段文本中的相似片段以及在划分行向量对应的位置。算法设计流程图如图2所示。

本文获得了最多出现4个字母的替换错误的30段文本的相似片段及其对应位置，如表3所示。

Table 3. Similar segments and their locations

表3. 相似片段以及对应位置

Figure 2. Flow chart of algorithm design

图2. 算法设计流程图

4. 用平均准确率评价算法

利用MATLAB软件随机生成相同模式长度的片段，作为原始片段。对原始片段随机位置进行字母替换，得到的新片段插入一段空文本中，并记录插入的片段与原始片段相似的片段个数。

重复上述操作直到文本长度达到预先给定的范围，用这样的方法生成多段文本并将它们作为测试文本。

选定一个原始片段和一个测试文本，使用本文算法查找测试文本中与原始片段相似的片段个数，与之前记录的数目对比，计算出此次对比的相似片段查找准确率。准确率的计算公式为

(5)

重新选择原始片段和测试文本，计算准确率，直到所有文本中的纪录数目对应的准确率全部计算出来。平均准确率的计算公式为

${\rho }_{avg}=\frac{{\displaystyle \sum \rho }}{P}$ (6)

根据上文，在这里同样取P为30，如表4所示获得了30段文本的准确率。则求得算法的相似查找片段平均准确率为0.9757。因此该算法具有较高的准确率，是查找相似片段的有效算法 [4]。其中算法分析流程图如图3所示。

Table 4. Accuracy of algorithm

表4. 算法的准确率

Figure 3. Flow chart of algorithm analysis

图3. 算法分析流程图

5. 结语

本文编写了一种针对相似片段查找的算法，该算法以海明矩阵为基础，构建了相似度表达公式，迭代运算直到满足相似度阈值的片段，同时考虑了语言文本记录时的替换错误，为破译未知语言提供了很好的出发点。