0 引言

随着计算技术日益提升, 全球教育信息化蓬勃发展.尤其是在线教育市场呈现出爆发式增长.题目测试一直是教育和学习的重要组成部分.在题目测试中, 题库一直处于在线教育的中心位置.借助于大数据存储、计算和分析等技术, 题库的规模日益扩大, 但也暴露出一些问题, 题目的质量良莠不齐, 重复或高度相似题目日益增多, 给教育行业的使用带来很大的困扰.因此, 为了保证题库及教学质量, 快速找出这些重复或高度相似题目就显得十分重要.

题目的主要表现形式是文本.现有的计算字符串相似度的方法按照计算所需的特征的不同, 可以划分为3种方法:基于字面相似的方法、基于统计关联的方法、基于语义相似的方法, 以及综合这3种方法的多层特征方法^[1-3].题目与普通短文本的主要区别在于, 题目表述的内容更趋向于字面化, 且文本长度较长.因此本文采用基于字面相似的计算方法来判断两个题目的相似度.基于字面相似的计算方法主要有基于编辑距离的计算方法^[4]和基于相同字或词的方法^[5].其中, 编辑距离法应用广泛, 计算方法相对成熟.本文将一个题目看作为一个字符串, 通过计算2个字符串的编辑距离来判断2个题目彼此是否相似^[6].文献[7]通过修改操作代价, 提高了算法的精准度, 文献[8]通过扩展交换操作, 提高了算法的精确度, 虽然文献[7]和文献[8]都提高了算法的精准度, 但同时也都增加了计算量.

本文分析Levenshtein距离矩阵中元素的内在关系, 提出一种提前终止的优化策略, 可预判编辑距离是否满足预设阈值, 并将该优化策略用于大规模题目匹配.本文的主要贡献在于提出并证明了定理1, 并根据定理1提出了提前终止的计算优化策略.该策略不仅可以提前判断两字符串是否不相似, 还可以提前判断两字符串是否相似, 并且实现了并行程序加速匹配过程.经过大量的实验, 测试结果表明:根据该优化算法得出的结果与原算法得出的结果相同, 且显著减少计算时间.

本文组织结构如下:第1节先介绍原Levenshtein算法的相关内容; 第2节提出对原Levenshtein算法的优化, 和优化策略的理论证明, 以及对应的时间复杂度的分析; 第3节介绍在实验过程中使用的两种优化策略, 以及对比优化前和优化后的编辑算法在处理相同数据集下的效率.第4节是总结.

1 Levenshtein算法简介 1.1 Levenshtein距离基本思想

Levenshtein距离又称编辑距离, 由俄国科学家Vladimir Levenshtein于1965年提出^[9], 指从源字符串$S$转成目标字符串$T$最少需要进行多少次字符的修改、添加和删除操作^[10].这3种操作次数的总和即定义为两个字符串的编辑距离.显然, 编辑距离越小, 表明两个字符串的相似程度越高.

1.2 Levenshtein距离算法

设有2个字符串$S$和$T$, 其中$S=s_1 s_2\cdots s_m, T=t_1 t_2\cdots t_n$ (不失一般性可设$n\geq m$).其中$s_i$, $t_j$是$S$和$T$经过分词的词项.建立一个字符串$S$与$T$的$(m+1)\times(n+1)$阶关系矩阵$LD$(默认$LD$矩阵的每一行对应$S$的一个下标, 每一列对应$T$的一个下标), 按式(1)填充矩阵$LD$(矩阵元素也称单元或单元格)^[11].

$ \begin{align} d_{i, j}= \left\{ \begin{array}{l}i, \quad j=0, \\ j, \quad i=0, \\ \min\left\{ \begin{array}{l}d_{i-1, j-1}+a_{i, j}, \\ d_{i, j-1}+1, \quad \quad \quad i>0, j>0, \\ d_{i-1, j}+1, \\ \end{array} \right.\\ \end{array} \right. \end{align} $

(1)

其中

$ \begin{align*} a_{i, j}=\left\{ \begin{array}{l}0\quad s_i=t_j\\ 1\quad s_i\neq t_j \end{array} \right. (i=1, 2, \cdots, m;j=1, 2, \cdots, n). \end{align*} $

矩阵$LD_{(m+1)\times(n+1)}$最右下角的元素$d_{m, n}$即为字符串$S$和字符串$T$之间的Levenshtein距离, 简称编辑距离, 记为$ld$, 表示字符串$S$变化到字符串$T$所需的最少编辑操作次数.

根据编辑距离$ld$, 定义字符串$S$与字符串$T$的相似度^[12],

$ Sim=1-\frac{ld}{\max(n, m)} . $

(2)

式(2)中$m$, $n$分别为$S$和$T$的长度. $Sim$值越大, 表示两个字符串相似度越高.显然, $ld$越小, $Sim$值越大, 两个字符串越相似.

以$S$="$ABCD$", $T$="$EABC$"举例, 根据式(1)计算可得表 1.

从表 1可知, $d_{4, 4}=2$, 即$ld=2$.显然, 字符串$S$转换成字符串$T$需要进行2次修改操作.再根据式(2)得到$Sim=1-\frac{2}{4}=\frac{1}{2}, $最终得出字符串$S$与$T$的相似度约为50%.

2 Levenshtein算法优化及应用 2.1 编辑距离矩阵特征分析与证明

根据第1.2节可知, $d_{m, n}$表示为$S=s_1 s_2\cdots s_m$与$T=t_1 t_2\cdots t_n$的$LD$距离.

因此, $\forall i, j, {1\leq i\leq m, 1\leq j\leq n}, d_{i, j}$表示为$S_1=s_1 s_2\cdots s_i$与$T_1=t_1 t_2\cdots t_j$的编辑距离.如表 2左上角阴影部分所示.

根据表 1可知, $d_{1, 1}=1$表示字符串"$A$"与"$E$"的编辑距离为1, $d_{2, 2}=2$表示为字符串"$AB$"与"$EA$"的编辑距离为2, 通过观察发现如下规律，

$ \forall i, 0\leq i<m, d_{m, n}\geq d_{m-i, n-i}. $

根据如上的观察, 提出如下定理.

定理1    $\forall i, j, 0\leq i<m, 0\leq j<n, d_{i+1, j+1}\geq d_{i, j}, $恒成立.

证明    设

$ d_{i, j}=X;d_{i+1, j+1}=Y;d_{i+1, j}=Z.\\ S_1=s_1 s_2\cdots s_i; T_1=t_1 t_2\cdots t_j; S_2=s_1\cdots s_i s_{i+1}=S_1 s_{i+1}; T_2=t_1\cdots t_j t_{j+1}=T_1 t_{j+1}. $

根据式(1)可知, $d_{i+1, j+1}$的值与$d_{i, j}$, $d_{i+1, j}$, 和$d_{i, j+1}$相关, 故存在以下3种可能.

① 若$d_{i, j}$为最小值(若$d_{i, j}=d_{i+1, j}$或者$d_{i, j}=d_{i, j+1}$, 也认为$d_{i, j}$为最小值)

根据式(1)中的$a_{i, j}$取值可知, 若$s_{i+1}=t_{j+1}$, 则$d_{i+1, j+1}=X=d_{i, j}$, 反之$d_{i+1, j+1}=X+1$.故当$d_{i, j}$为最小值时, $d_{i+1, j+1}\geq d_{i, j}$.

② 若$d_{i+1, j}$为最小值$(d_{i+1, j}<d_{i, j})$

因为$d_{i+1, j}<d_{i, j}$, 则可推出以下结论:

$ \exists k, {0<k\leq i+1}, 使得S_k=s_k\cdots s_i s_{i+1}为 T_1 的子串; $

(3)

反之不一定成立.

若使用反证法证明这种情况:若不存在$S_k$是$T_1$的子串, 则$T_1$中肯定不存在$s_{i+1}$.因此当$S_1$添加$s_{i+1}$后, $T_1$只能插入$s_{i+1}$, 或将$t_j$修改成$s_{i+1}$才能转换成$S_2$, 故$d_{i+1, j}=d_{i, j}+1$, 与$d_{i, j}>d_{i+1, j}$产生矛盾, 故结论(3)成立.

需要指出的是, 若结论(3)能够成立, $d_{i+1, j}<d_{i, j}$不一定成立.例如表 2中$d_{1, 2}=2$, 即将$T_1=$"$E$"转换成$S_1=$"$AB$"最少需要两次编辑操作, 但是当$T_1$插入"$A$"之后虽然满足结论的要求, 但$d_{2, 2}=2=d_{1, 2}$, 故结论(3)成立并不能说明$d_{i+1, j}<d_{i, j}$也成立.

若想$d_{i+1, j}<d_{i, j}$成立, 新插入的$s_{i+1}$还必须满足如下条件,

$ s_{i+1}是 S_1 转换成 T_1 所需的编辑操作之一. $

(4)

例如在表 1中, $d_{2, 2}=2$, 若将$T_1=$"$EA$"转换成$S_1=$"$AB$"有两种转换方法, 两种方法都至少需要进行两次编辑操作.第一种是在$T_1$的最后插入"$B$"再将"$E$"删除, 第二种是将$T_1$两个字符逐个修改成$S_1$.

当$T_1$添加"$B$"之后, 发现新添加的"$B$"正是$T_1$转换成$S_1$所需的编辑操作之一.所以新添加的"$B$"反而相当于减少了一次转换所需的编辑操作, 故$d_{2, 2}=d_{3, 2}+1.$

因此, 只有当新插入的$s_{i+1}$满足条件(4)时, 才能使$d_{i+1, j}<d_{i, j}$.但由于$S_1$只插入一个字符, 所以$d_{i+1, j}$只会比$d_{i, j}$少一次编辑操作, 故$d_{i, j}=d_{i+1, j}+1$.

又根据式(1)可知, 若$d_{i, j+1}$为最小值, 则$d_{i+1, j+1}=d_{i, j+1}+1$, 所以$d_{i+1, j+1}=d_{i, j}$.因此, 当$d_{i+1, j}$为最小值时也能满足$d_{i+1, j+1}\geq d_{i, j}$.

③ 若$d_{i, j+1}$为最小值$(d_{i, j+1}<d_{i, j})$

$d_{i, j+1}$与$d_{i, j}$的关系, 与$d_{i+1, j}$和$d_{i, j}$的关系相似, 故证明同第二种可能.所以$d_{i+1, j+1}\geq d_{i, j}$也成立.

结合以上3种可能, 证明定理1是成立的.证毕.

令$(i=m, j=n)$, 对定理1进行递推展开可得:

$ d_{m, n}\geq d_{m-1, n-1}\geq \cdots \geq d_{1, n-m+1}. $

(5)

2.2 改进编辑距离算法与示例

根据式(5)递推关系式可以对应得到下表 3.

根据表 3, 可总结出如下结论,

$ \forall i, {0\leq i<m}, d_{m, n}\geq d_{m-i, n-i} 恒成立. $

(6)

因此, 在计算Levenshtein距离的过程中, $\exists_{0\leq i<m}$, 使得$d_{m-i, n-i}>\alpha$, 则$d_{m, n}>\alpha$恒成立.在理想的状态下式(6)等价于$\forall_{0\leq i<m}$, $d_{m, n}=d_{m-i, n-i}+1$.因此, 若$\exists i, {0\leq i<m}$, 使得$d_{m-i, n-i}\leq \alpha-(m-i)$, 则$d_{m, n}\leq \alpha $恒成立.

在题目匹配中, 判定两个字符串是否相似, 需要对两个字符串的相似度设定一个阈值$Sim$.因此若两个题目相似, 则必满足如下,

$ 1-\frac {ld}{\max(n, m)} \geq Sim. $

(7)

简化式(7)可得如下,

$ n(1-Sim)\geq ld=d_{m, n.} $

(8)

综合式(6)和式(8), 得出如下,

$ \exists i, {0\leq i<m}, 使得 d_{m-i, n-i}>n(1-Sim), 则 d_{m, n}>n(1-Sim) 恒成立. $

(9)

根据式(9)可知, 计算Levenshtein编辑距离时, 如$d_{m-i, n-i}>n(1-Sim)$时, 则可认为两个题目的编辑距离必大于设定的阈值, 两个题目必不相似.

$ 同理, \exists i, {0\leq i<m}, 使得d_{m-i, n-i}\leq n(1-Sim)-(m-i), 则d_{m, n}\leq n(1-Sim)恒成立. $

(10)

根据式(10)可知, 如$d_{m-i, n-i}\leq n(1-Sim)-(m-i)$时, 则可认为两个题目的编辑距离必小于等于设定的阈值, 两个题目必相似.

因此, 改进后的Levenshtein算法步骤如下, 改进编辑距离算法计算编辑距离流程图见图 1.

以表 1所示的$S$和$T$为例说明改进后的编辑距离算法.假设若$S$与$T$的相似度大于等于80%, 则认为$S$与$T$是相似的两个题目.

将$Sim=80\%$代入式(8), 得$ld\leq 0.2n$.则$S$与$T$的编辑距离阈值为$0.2n$.根据结论(9)可知, $\exists i, {0\leq i<m}$, 使得$d_{m-i, n-i}>0.2n$, 则认为$S$与$T$不相似.

由结论(9)可知, 只需关注表 1矩阵中$d_{1, 1}$, $d_{2, 2}$, $d_{3, 3}$以及$d_{4, 4}$ 4个矩阵元素.

由式(8)得出$ld$的阈值为$0.2n=0.8$, 当计算得出$d_{1, 1}$时, 发现$d_{1, 1}>ld$, 则认为两个字符串相似度必低于80%, 因此后续计算就可省略.

由于该改进算法并不修改原矩阵中的数值, 而是在计算过程中根据预设的阈值进行重复度提前判定, 减少不必要的计算过程.因此改进算法匹配出的重复记录与原算法匹配出的结果是相同的, 因此该改进算法的准确性得到保证.

在文献[13]中, 提前终止思想已经使用在了两个大字符串集合中找到了相似的字符串中.在文献[13]中, 设$\triangle=n-m$(两个字符串的长度差), 设$\tau$为两字符串相似度是阈值, 即为式(8)中的$n(1-Sim)$.在文献[13]中关注的是矩阵中$d_{i, j} (i=1, 2, 3\cdots;i-\lfloor\frac{\tau-\triangle}{2}\rfloor\leq j\leq i+\lfloor\frac{\tau+\triangle}{2}\rfloor)$的值, 若$\exists {i, j}$, 使得$d_{i, j}\geq \tau$, 则认为两个字符串不相似, 以此来实现提前终止.本文直接关注的是$d_{i, i+\triangle}$, 并证明$d_{i+1, i+\triangle+1}\geq d_{i, i+\triangle}$.本文的效率要比文献[13]高, 主要表现在式(10)的提前终止策略是文献[13]未涉及的.且本文每行只需要比较一次, 而文献[13]则需要比较$\tau\!-\!\triangle$次.只有当$\triangle=0$ (两个字符串的长度相同), 且两个字符串不相似的时候, 本文的效率和文献[13]的效率相同.

2.3 改进编辑算法分析

优化前算法的时间复杂度为$O(n^2)$, 优化后算法在最坏情况下需要计算的矩阵和原矩阵一样, 所以优化后算法的时间复杂度也为$O(n^2)$, 因此在时间复杂度上, 与优化前后的时间复杂度相同.

由于原算法本质上是一个矩阵计算, 本身就能够终止, 本文基于原算法提出了一种提前终止的策略, 所以该改进算法也具有终止性.

根据第2.1节的证明, 可保证该改进算法的正确性.

3 实验优化与结果分析 3.1 实验优化

在实验过程中增加了两个优化过程, 一个是根据题目长度来决定两个题目是否进行匹配, 还有一个是将进行匹配的题目按照字符出现的频率由低到高重新排列.

在实验过程中发现, 若两个题目相似, 其字符串长度也很相近.如: $S$="$AB$"与$T$="$AHNSUDIUS$".显然, 根据两个字符串的长度就可以认为字符串$S$与$T$是不可能相似的两个题目.

根据上述特点, 设定常数$\varepsilon(0<\varepsilon<1)$, 只有满足如下时, 才进行相似度匹配.

$ (1-\varepsilon)\leq \frac {S的长度}{T的长度}\leq(1+\varepsilon) . $

(11)

实验中, 假设$\varepsilon=0.25$, 经过分析, 减少了70%的无关计算.在理想状态下, 希望$LD$矩阵元素能尽量满足如下,

$ d_{m, n}>d_{m-1, n-1}>\cdots>d_{1, n-m+1}. $

(12)

这样就能在最少的计算内满足结论(9), 可以最大幅度的提升计算效率.但当$S$="$AAAB$", $T$="$AAAC$"时, 根据式(1)的计算结果见表 4.

由结论(10)可知, 关注$LD$距离矩阵中$d_{1, 1}, d_{2, 2}, d_{3, 3}$以及$d_{4, 4}$这4个$LD$矩阵元素, 但发现只有当程序计算到$d_{4, 4}$时才能得出结果, 与改进算法前的效率相同.算法优化效率提升不明显, 故需要对数据进行预处理.

在进行匹配前, 先将字符串$S$与$T$中的字符按照各自的出现频率进行重新组合, 按照频率由低到高排序, 组成新的字符串$S'$和$T'$.

在新的字符串$S'$与$T'$中.字符越靠前, 表明该字符出现的频率越低, 出现与该字符相同字符的概率也就越低.所以字符越靠前, 对式(12)的吻合度越高, 因此计算效率也就越高.

将上述的字符串$S$和$T$, 根据字符出现频率由低到高排序, 生成新的字符串$S'$="$BAAA$"和$T'$="$CAAA$", 详见表 5.

根据重新排完序之后的字符串$S'$与$T'$的$LD$矩阵.当计算得出$d_{1, 1}$时, 发现$d_{1, 1}>ld$, 表明两个字符串的相似程度不满足设定的阈值, 所以程序只需要计算第一行便可以结束.

3.2 实验结果及分析

为了验证本文改进算法的有效性, 选取一系列真实的K12题目进行测试.实验所用的计算机配置CPU: i7-7700 8核16线程3.6 GHz、内存: 16 G.判重程序中开启16个线程进行并行匹配计算.所有学科题目的重复度阈值设置为80%.首先, 选取了10万生物试题进行详细匹配, 匹配时根据题目长度进行, 长度差别过大的试题, 默认两个题目不相似, 所以记录了相应题目长度范围内的题目个数、算法改进前后的计算量以及计算时间, 并给出相应的计算量节省百分比和计算时间节省百分比.结果详见表 6.

根据表 6, 将计算量节省百分比和计算时间节省百分比绘制折线图, 结果详见图 2.

从图 2中, 发现计算量节省百分比是比较稳定的, 而计算时间节省百分比却有着上升的趋势.

出现这种趋势主要是因为在题目长度较短时, 每行计算量较小, 程序运行时间较短, 因此在程序运行中的题目分配、函数调用等程序执行过程导致的延迟不能忽略不计.因而才导致了题目长度在较短时, 节约耗时的百分比与实际减少的计算量差距较大.在折线图中也可以清楚地看出随着题目长度的增长, 节约计算量百分比与节约耗时百分比的差距在不断缩小, 由于程序执行过程而导致的延迟所占比例越小.

接着选取了生物的10万、20万、30万、40万和50万不同数量的试题进行匹配, 记录了改进前后的计算时间, 以及计算时间节省百分比, 结果详见表 7.

根据表 7的计算时间节省百分比, 绘制折线图, 结果详见图 3.

从图 3中发现在各数据量中, 计算时间节省百分比时区域稳定的, 在80%上下浮动.

最后选取语文、数学、物理、化学、地理、生物、历史和政治各50万数量的题目进行匹配, 记录了改进前后的计算时间, 以及计算时间节省百分比, 结果详见表 8.

根据表 8的计算时间节省百分比, 绘制折线图, 结果详见图 4.

分析以上结果发现, 使用改进编辑距离算法的平均计算时间节省百分比在80%左右.且两个算法所匹配出的相似题目在数量和匹配上完全相同.

由于各个学科的试题内容和知识点的不同, 所以各学科在匹配时间上各有不同, 比如在语文试题中长文本的个数居多, 所以匹配时间也是最长, 但各学科的平均计算时间节省百分比是比较稳定的, 所以本文提出的提前中止策略的效率是稳定的.

4 结论

本文分析了经典Levenshtein算法生成的矩阵中内在的联系, 提出一种提前终止策略的改进算法.该改进算法不仅不影响原算法的准确性, 而且能更快速地判断出两个题目是否相似.实验结果表明, 本文提出的改进算法, 能够显著减少计算时间, 适用于大规模题库重复判定.

致谢: 感谢精锐教育(www.onesmart.org)提供的各学科试题库.