基于公共子串的文本相似度基于公共子串的文本相似度基于公共子串的文本相似度基于公共子串的文本相似度计算计算计算计算模型模型模型模型
苏振魁，田园
大连理工大学软件学院，大连(116620)
摘
摘摘
摘
要
要要
要：
：：
： 为了克服现有文本相似度计算模型过多关注词频，而较少关注词语在文本中出现顺
序的缺点，本文在基于向量空间模型的基础上，提出了一种基于公共子串的文本相似度计算
模型(Common Substring Model,CSM)。CSM 采用一种基于序差的方法求得两个文本中的所有
公共子串，然后利用由所有公共子串生成的公共子串矩阵，再结合向量空间模型（Vector
Space Model，VSM）中的 TFIDF 方法，最后使用一种多级选择(利用最长公共子串的长度)
的算法来得到相似度计算结果。在 TREC9 数据集上的实验表明 CSM 优于 VSM。
关键词
关键词关键词
关键词：
：：
：文本文档；相似度；公共子串；向量空间模型；
中图分类号
中图分类号中图分类号
中图分类号：
：：
：
1 1 1 1 引引引引 言言言言
文本相似度计算是文本聚类、文本分类、自然语言处理和信息检索研究中的一个基础课
题，一直受到研究人员的关注。但由于每个人受到的教育程度以及思想观念的不同，所以同
样的两个文本在人的主观世界中引起的反映也是不同的，甚至对于处于不同时期的同一个
人，它们所产生的印象也不同。这就给文本相似度计算带来了很大难度。但是在实际应用中，
用户往往根据经验和自己的需要来判断文本相似度。在历史上，已经有很多的相似度计算模
型被提出了，例如：向量空间模型（Vector Space Model,简称 VSM）
[1] [2]
，字符串相似度模
型
[3] [4]
，文档结构相似度模型
[5] [6]
。还有国内学者提出的一些方法：利用属性论来计算文本
相似度的方法
[7]
、基于汉明距离的文本相似度计算方法
[8]
、基于语境框架的文本相似度方法
[9]
以及基于压缩稀疏矩阵矢量相乘的文本相似度计算方法
[10]
等等。目前主流的是 VSM，它是
根据文本内容(词频)来进行计算的。但是，它无法利用词语在文本的一定范围内的先后顺序
信息来区分文本，举例如下：
A：某日，小王请小刘到小王家吃饭。
B：某日，小刘请小王到小刘家吃饭。
倘若，将 A和 B两个文本同时放到某一个文本集合中，那么传统的向量空间模型将会判
断 A和 B两个文本的相似度为 1，即相同。但，显然 A和 B所表达的意思是不同的。从这个
简单例子可以知道词语在文本中出现的先后顺序（在一定范围内）和词频一样可以用于文本
相似度计算。如果将一个文本当作一个由词语组成的串，那么在一种极为简单的情况下，可
以认为两个串的公共子串就是词语出现的先后顺序的最直接的表现特征。因此，我们提出基
于公共子串的文本相似度模型(Common Substring Model,CSM)。
.文本相似度计算文本相似度计算文本相似度计算文本相似度计算模型模型模型模型
下面我们先来介绍一下 VSM模型以及其中的 TFIDF方法，然后给出详细的 CSM计算
方法。
VSM 以及以及以及以及 TFIDFTFIDFTFIDFTFIDF 方法方法方法方法
VSM 以词语构造一个高维空间，每个词语为该空间的一个维，文本被看作这个空间中
的一个向量。
xd =< )1(xd , )2(xd ,…, )(nxd > T (1)
其中，n是文本集合中不同词语的个数。
1
TFIDF(Term Frequency inverse document Frequency)是向量空间模型中一种常用的文本
向量化方法，它综合考虑了词语在单个文本中出现的频度和该词语在文本集合中出现的频
度。
)(ixd =TF(w i ,doc x ) ·IDF(w i ) (2)
其中：TF(w i ,doc x )是词语 w i 在文本 doc x 中出现的次数，IDF(w i )=log(|D|/DF(w i )),|D|是
文本集合中文本总数，DF(w i )是包含词语 w i 的文本个数，IDF(w i )是词语 w i 的全局特性，
或者说是用 w i 来区分此文本集合的能力。
在 CSM中，主要利用公共子串矩阵 M、最长公共子串信息以及 VSM中得一些方法来
进行计算。我们假定：文本 A和文本 B中存在某一公共子串，形如：**ab*** （其中*号代
表若干个词语，a和 b是确定的两个词语），此公共子串在文本 A中重复次数为 numA,在文
档 B中重复次数为 numB。
那么：公共子串矩阵M定义如下：
X(i) = a，X(j) = b (4)
其中： X代表此文本集合中出现的不同词语所构成的数组，主要用来确定词语在矩阵M中
的行序号和列序号。公共子串的求取算法将会在下文给出。
CSM CSM CSM CSM 计算计算计算计算方法方法方法方法
在 VSM模型中，通常采用文本向量夹角的余弦值来度量文本间的相似性。
,
( xdocsim doc y )=cos(<d x ,d y >) = d x·d y = ∑
=
n
i
ixd
1
)( · )(iyd (5)
其中：
,
( xdocsim doc y )是两个文本的相似度计算结果；n 是文档集合中不同词语的个数；
d x ,d y是文档 doc x ,doc y经过单位化后的向量。满足如下公式(6)：
∑
=
n
i
ixd
1
2
)( = 1，∑
=
n
i
iyd
1
2
)( = 1 (6)
为了继承 VSM模型的优点，CSM采用如下的方法来计算两个文本之间的相似度：
(7)
其中：λ既是相似度计算结果的一部分，同时也是一个阀值，它由公式(8)得出。α是一个
最长公共子串因子，由公式(9)得出。
λ = ∑
=
n
i
ixd
1
'
)( · )(iyd (8)
M(i,j) =
M(i,j) + log ),max( numBnumA
numBnumA +
i ≠ j
1 i = j (3)
,
( xdocsim doc y ) =
α + (1 – α)λ λ>=
λ λ <
2
α= ( ))(),(max(
),.......,max( )()2()1(
yx
m
docLdocL
slslsl
)
κ
(9)
其中：公式(8)中的 d y需要满足公式(6)， 'xd 是 d x与公共子串矩阵 M(经过公式(10)进行了
列向量化 )相乘以后再经过单位化后的向量 (满足公式 (11))；公式(9)中的 )(msl 表示
ydoc 与xdoc 的第 m 个公共子串的长度，L(doc )x 表示 xdoc 的长度，κ 值的不同选择可以调
整α的大小。根据经验，我们选择了两个数值(公式(12))。
∑−
=
1
0
2),(
n
i
jiM =1 j∈(0,1,…,n-1) (10)
∑
=
n
i
ixd
1
2'
)( = 1 ,
'
xd = xd ·M (11)
(12)
以上这种多级选择的方法主要用来增大相似度计算结果的分离度，在没有发现公共子串
的情况下，它将蜕变为传统的 VSM 模型下的 TFIDF方法。
3. 3. 3. 3. 公共子串的求取算法公共子串的求取算法公共子串的求取算法公共子串的求取算法
CSM使用了公共子串信息，我们采用如下的方法来求取两个文本文档的所有公共子串。
原理原理原理原理
定义
定义定义
定义：
：：
：序差，一个元素在串 A中的一个位置序号与它在串 B中出现的全部序号的差值。
序差通常以序差集合的方式出现。使用 XC(x)来表示。举例说明：
A: d c a b c d e d e d b c d a
B: a b c d b a e d b c d e b a c b
在 A 中，第 0个位置上的元素是 d;在 B中，元素 d 出现在第 3、7、10的位置上，那么
此时 XC(d)={0-3,0-7,0-10}={-3,-7,-10}.
在 A 中，第 1 个位置上的元素是 c;在 B中，元素 c 出现在第 2、9、14的位置上，那么
此时 XC(c)={1-2,1-9,1-14}={-1,-8,-13}.
…………
在 A 中，第 5个位置上的元素是 d;在 B中，元素 d 出现在第 3、7、10的位置上，那么
此时 XC(d)= {5-3,5-7,5-10}={2,-2,-5}.
…………
如果同一个元素在 A串中的不同位置出现，那么它的序差集合也是会随时变化的。而且
我们可以观察到序差集合里面的元素是自然排好序的，这就为我们计算两个序差集合的交集
带来了极大的方便。
性质一
性质一性质一
性质一：如果两串中存在公共子串(其元素的个数大于等于 2)，那么构成此公共子串的
元素此时在两串中的序差集合必有非空的交集。
证 明 ： Q 串 A 和 串 B 中 存 在 公 共 子 串 1x 2x 3x 、、、 mx （ m>=2 ） ,
κ =
3/4 λ <
1/2 λ>=
3
∴ 1][)()(( xiAALii =∩<∃ ), 1][)()(( xjBBLjj =∩<∃ ),其中 L(A)表示子串 A的长度，
A[i]表示子串 A 的第 i 个元素的值，其他依次类推∴ (i-j) ∈ XC( 1x ).同理QA[i+1]=
2x ,B[j+1]= 2x ,∴（i+1-j-1）=(i-j) ∈XC( 2x ).依次类推，有(i-j) ∈XC( mx ),∴必有(i-j)
∈I
m
k
kxXC
1
)(
=
,命题得证。
性质二
性质二性质二
性质二：如果串 A的若干个相邻元素（大于等于 2个）此时在串 B中的序差集合的交集
非空，那么此若干个相邻元素必是两串的所有公共子串之一。
证 明： 假定串 A中存在 n个相邻元素，A形如：****** 1x 2x 3x 、、、 nx ********* 。 此
n 个相邻元素可以依次表示为 A[i]= 1x 、A[i+1]= 2x 、、、A[i+n]= nx ，此 n 个相邻元素此
时在串 B 的序差集合分别记作 XC( 1x )、XC( 2x )、、、、XC( nx )，且I
n
j
jxXC
1
)(
=
≠Ф。
QI
n
j
jxXC
1
)(
=
≠Ф，∴ ∈∃ )(c I
n
j
jxXC
1
)(
=
，即 c∈ XC(x j )，j∈(….n)。∴根据序差定义
可知 B[i-c]= 1x ，B[i-c+1]= 2x ，，，B[i-c+n]= nx ,说明此 n个元素此时在串 B中也是相邻的。
即 1x 2x 3x 、、、 nx 是串 A和串 B的公共子串。命题得证。
推论
推论推论
推论：如果在一定范围内若干个元素的序差集合的交集非空，则在两串中存在相似结
构（类似于“a***b ”，其中“*”可以为任何元素，但“a”与“b”之间的距离是固定的）。
在此不做证明。
为了更好说明定义和两性质，举例如下:
A: d c a b c d e d e d b c d a
B: a b c d b a e d b c d e b a c b
显而易见，“a b c d”是串 A和 B的所有公共子串中的一个,其元素序差集合如下：
XC(a) = {2-0，2-5，2-13} = {2，-3，-11}
XC(b) = {3-1，3-4，3-8，3-12，3-15} = {2，-1，-5，-9，-12}
XC(c) = {4-2，4-9，4-14} = {2，-5，-10}
XC(d) = {5-3，5-7，5-10} = {2，-2，-5}
发现一: XC(a) ∩ XC(b) ∩ XC(c) ∩ XC(d) = {2}，(性质一)
发现二：XC(b) ∩ XC(c) ∩ XC(d) = {2，-5} ，交集里面除了一个 2 之外，还有其他
元素-5，说明在 B的其他位置还存在“b c d”公共子串，此公共子串在 B中的起始位置应
该是：3-(-5)=8,（其中 3是此时“bcd”在 A 中的起始位置）.通过观察，我们发现的确如
此。有力的说明性质二的正确性。
下文的公共子串的求取算法依赖于以上的两性质，通过比较序差集合不仅会得到两串的
所有公共子串的重复次数和位置，事实上还可以求得一定范围内的子序列以及判断相似结
构。
4
公共子串求取算法及复杂度分析公共子串求取算法及复杂度分析公共子串求取算法及复杂度分析公共子串求取算法及复杂度分析
求取两个文本（仍然假定为文本 A 和文本 B）的所有公共子串的算法的理论依据是
中的性质二。这个算法既可以用于求取“a”与“b”之间距离固定的那种类似于公共子串的
相似结构，也可以用于求取“a”与“b”之间的距离不固定的相似结构，只要在比较序差集
合的时候将“=”扩展为“>=-r”且“<=r”,其中 r为相似结构的搜索半径.在此我们仅以求
取所有公共子串的问题来介绍这个算法，它需要如下相似的两个步骤：
1， 求取文档 A的子串在文档 B出现的次数和位置（可以称为:求取 A 到 B 的映射）。
2， 求取文档 A的子串在文档 A中重复的次数和位置(可以称为:求取 A 到 A的映射)。
这两个步骤是一个问题的两种输入，其算法是一样的。这两个步骤完成以后，再使用一
个简单的合并算法就可以求得 A和 B的所有的公共子串以及它们在A和B中各自出现的重复
次数和位置。
求取映射主要步骤如下：
一
一一
一，
，，
，
初始化一个 3行 L(A)列的数组 SA，将文档 A 的每一个词语按照原来的位置依次的
放入 SA[0]。
二
二二
二，
，，
，
将文档 B里的词语生成一棵二叉树 TreeB，其节点的域值是每一个不同的词语
在文档 B中的出现位置的集合 X(x,B).x 代表每一个不同的词语。
此步的最坏时间复杂度：L(B) ·log|B|，|B|代表文档 B中出现的不同词语的个数。
三
三三
三，
，，
，
使用 SA[0]中的每一个词语在 TreeB 中进行搜索，若能搜索到某个节点，则将这个
节点的 X(x,B),放入到 SA[1]的相应位置；若搜索不到则进行下一个词语，直到将 SA[0]搜
索一遍。
此步的最坏时间复杂度：L(A)·log|B|。也可以使用链表将此步的时间复杂度减少到
|A|·log|B|(一个巧妙的做法是：在 SA数组中再加一行，用来存储下一个 SA[0][i]的位置，
这样能避免 A 中频度较高的词语多次的搜索 TreeB)。
四
四四
四，
，，
，设定 i = 0 直到 i = L(A) – 1
若 SA[1][i]非空，则 SA[2][i] = i - SA[1][i]; //SA[2][i]即 XC(SA[0][i]).
此步时间复杂度： ∑−
=
1)(
0
|)],][0[(|
AL
i
BiSAX .第三、四步可以同时完成，为了更好的说明序
差的概念，在此分开表述。
五
五五
五，
，，
，初始化两个结构体组成的链，一个是计算过程中的过程链，设定为指针 Producer,
它指向当前公共子串长度为 2的结构体，指向当前公共子串长度为 3的结构
体，以此类推；另一个是存放结果的 Result链。Producer 和 Result使用相同的结构体：
CU: XC (序差值域)
Unlength(子串长度)
Start(此子串在文档 A中的起始位置)
Next（下一个结构体的地址）
六
六六
六，
，，
，1.设 i= 0，使用 SA[2][0]生成一个 CU结构体，设为 CU[0];
++，使用 SA[2][i]生成一个 CU结构体，设为 CU[i%2];
(CU[(i-1)%2].XC∩CU[i%2].XC≠Ф)
{
NewCU = New CU(CU[(i-1)%2].XC∩CU[i%2].XC);
//说明：=CU[0].Unlength+1
If(Producer == null)将 NewCU 插入到 Producer链;
否则 转至 4 执行 Producer = DiGui(Producer,NewCu);
5
}
Else 如果 Producer链非空，则将其插入到 Result链;
if(i<L(A)-1)则转至 2;
Else 如果 Producer链非空，则将其插入到 Result链;
DiGui(OldCU,NewCU)
//递归函数，输入为 OldCU 链和 NewCu 结构体，返回值为一个 CU结构体。
//下文有详细说明。
{
if(OldCU == null) return null;
if(∩ ==Ф){ 将 OldCU链插入到 Result链; OldCU = null;}；
else
{
NewNewCU = New CU(∩);
//说明： = +1
if(∩ XCNewCU . ≠Ф)
{将 New CU(∩ XCNewCU . )插入到 Result链;}
if( != null ) = DiGui (,NewNewCU);
else = NewNewCU;
}
return NewCU;
}
第六步是整个算法的核心，其中的语句序列 4是一个递归函数，所完成的工作是:当有
一个新的子串长度为 2的 NewCU产生以后，NewCU就要与当前的 Producer(OldCU)链进行相
交操作，若 ∩≠Ф，则说明由 SA[0][i-2]、SA[0][i-1]以及 SA[0][i]
所构成的长度为 3的子串结构体NewNewCU在B中出现,此时需要将 Producer指针指向 NewCU,
并且将 ∩ XCNewCU . （如果其不为空的话）产生的新结构体输出到 Result
链，这个新的结构体表示由 SA[0][i-2]和 SA[0][i-1]组成的子串在 B中的其他位置出现，
并且那些位置的下一个词语与SA[0][i]不同。然后再利用原来的与NewNewCU
进行相交操作看是否有子串长度为 4的公共子串产生………… 以此类推，直到
∩=Ф或者 Producer=null, 若 ∩=Ф 说明当前 Producer链
所有的结构体里面的子串在词语 SA[0][i]处截止，或者说是若干个长度较长的公共子串在
文档 A的第 i个词语处截止。此时需要将它们输出到 Result链。若 Producer=null说明一
个较长的公共子串已经延伸到文档 A的第 i个词语处。 第六步的时间复杂度取决于文档 A
与文档 B的公共子串的多少和每一个的长度，以及所选取的文档 A本身的重复子串的多少，
还有这些公共子串在文档 B中的复合程度（即较长公共子串平均包含较短公共子串的多少）。
其最坏的时间复杂度为:
∑
=
+−−
))(),(min(
1
)1)()()((3
BLAL
i
iBLiAL (13)
需要说明的是：因为两个序差集合里面的元素都是自然排好序的，所以两个结构体(CU0
和 CU1)相交生成一个新结构体的最坏时间复杂度：||+||.
6
七
七七
七．
．．
．检查 Result 链相邻的两个结构体，若它们的 Unlength 域值前后相差 1，并且 XC
相等，则去除 Unlength 值较小的那一个，然后再使用 Unlength 较大的那一个继续与下一个
进行比较，直到 Result链尾。
第七步主要是去除 Result 链的一些结构体，这些结构体所代表的串是相邻结构体所代
表的串的子串。其时间复杂度取决于 Result链的长度，以及串 A和串 B 的所有公共子串的
长度和多少。最坏时间复杂度为： L(B)(L(A)-2)
串 A 和串 B 经过以上七步的处理，就可以得到 Result链。我们暂且把使用串 A 和串 B
作为输入而得到的 Result链称作：ABResult;使用串 A和串 A 作为输入而得到的 Result链
称作：AAResult（去除链尾的那个结构体，因为那个结构体所表示的就是串 A）。可以使用
图 1 来形象地表示构成 ABResult链和 AAResult链的结构体存储的信息；
合并算法较为简单，在此不再详述，最终得到由如下的结构体组成的链：
LU： Name（公共子串的值）
StartLocationA(在串 A中的起始位置，是一个集合)
NumA(此公共子串在串 A中的重复次数)
StartLocationB(在串 B中的起始位置，是一个集合)
NumB（此公共子串在串 B中的重复次数）
Unlength(此公共子串的长度)
Next(下一个结构体的地址)
一个 LU结构体即可以记录图 1中所有“a b c”公共子串的信息。
算法总结
算法总结算法总结
算法总结：
：：
：此算法利用序差来求取两串的所有公共子串的长度、以及在两串中的重复次
数和起始位置。其总的时间复杂度主要由第六步来决定。算法还可以被用于抄袭检测系统以
及其他需要求取所有公共子串的系统。
4. 实验实验实验实验和结果分析和结果分析和结果分析和结果分析
数据集和数据集和数据集和数据集和实实实实验设计验设计验设计验设计
实验使用 Intel Core Duo T2600 CPU,2G内存的个人计算机，在Windows XP 操作
系统上，以 Java 作为开发环境。
选用英文 TREC9数据集中的部分数据进行实验。TREC9是一个通用的数据集，广泛被
用于分类、聚类以及文本相似度研究。在此数据集中，文档所涉及的领域(一共被分为 4904
图 1 结构体示例图
Fig 1 Examples of structures map
* * * * * * * * * a b c * * * * * * * * * * * a b c * * * * * *
串 A:
串 B：
AA结构体一
AA结构体二
* * * a b c * * * * * * * * * a b c * * * * * a b c * * * * **
A
B
结
构
体
一
A
B
结
构
体
二
7
个，涵盖了医学研究的各个方面)均被人工标注。因此我们采用如下的公式来作为人工标注
的文本相似度结果：
||||
||2
_ ),(
ji
ji
ji CC
CC
rsim
+
∩
= (14)
其中， iC 和 jC 分别是第 i个文本和第 j个文本所涉及到的领域集合。
我们选用了其中的 160篇摘要作为实验数据，最后采用如下两种实验评估算法对实验结
果进行评估：
第一种，KNN（K-nearest neighbors）相似搜索。这是一种间接的评价方式，评价结果
受数据集本身的影响较大。此方法的计算公式如下：
∑
=
∩
=
r
i
kiki
k
RQ
r
kp
1
),(),( ||1)( (15)
其中：k是指定搜索最接近的文本个数；r是集合中文本总数； ),( kiQ 是使用了文本相似
度计算方法所得到的最接近于第 i 个文本的 k 个文本的集合； ),( kiR 是人工标注的最接近于
第 i个文本的 k个文本的集合。
第二种，两个相似度计算结果直接进行比较的方法，它受数据集本身的影响较小。其公
式如下：
∑∑
= +=−
=
k
i
ji
k
ij
p
kk
kp
1
),(
'
1)1(
2)( (16)
(17)
其中，k是集合中的文本总数； ),( jiq 表示第 i个文本与第 j个文本使用指定模型计算出
的相似度。
在实验中，我们以 TFIDF来表示主流的向量空间模型的实验结果；以 CSM 来表示基于公
共子串的文本相似度模型的实验结果。
实验结果分析实验结果分析实验结果分析实验结果分析
我们使用以上两种实验评估算法对数据进行了实验，然后得到如下的表一和表二，它们
分别对应于第一种和第二种实验评估方法。
表 1 使用第一种评估方法(KNN)的实验结果
Result of method(KNN)
k 5 10 20 40 60 80
TFIDF/%
CSM/%
对比/% + + + + + +
),(' jip =
1- ),( jiq ),(_ jirsim =0
)_,max(
)_,min(
),(),(
),(),(
jiji
jiji
rsimq
rsimq
),(_ jirsim ≠0
8
表 2 使用第二种评估方法的实验结果
Result of method
k 20 40 80 160
TFIDF/%
CSM/%
对比/% + + + +
从表中数据可以看出：在使用KNN算法的情况下，CSM的准确度相对于VSM的 TFIDF
有了略微的提升（大约为 2%到 3%）,我们推测这可能是由于文章摘要所包含的公共子串较
少所造成的，此时公共子串矩阵 M 有明显的退化为单位矩阵的趋势。在使用第二种实验评
估算法的情况下，CSM相对于 TFIDF有较大的提高(大约为 10%)，这主要归功于多级选择
的算法设计。
5555 总结总结总结总结
本文利用传统VSM模型中的TFIDF方法与公共子串信息相结合的办法做了一次文本相
似度计算方面的尝试。首先采用一种基于序差的算法来求取公共子串，然后构造公共子串矩
阵并且使用最长公共子串对结果进行多级选择，最后使用两种实验评估算法对在 TREC9部
分数据集上的实验进行了评估，发现这种计算方法的准确度相对于传统的 TFIDF 方法有了
略微的提高。
参考文献
参考文献参考文献
参考文献
[1] and , Introduction to Modern Information Retrieval, New York: McGraw-Hill, 1983
[2] Gerard Salton and Chris Buckley. Term Weighting Approaches in Automatic Text. Retrieval Information
Processing and Management,1988,24(5):513～523
[3] V. I Levenshtein Binary codes capable of correcting spurious insertions and deletions of ones (original in
Russian) [A]. Russian Problemy Peredachi informatsii l[C], pp. 12-25,1965.
[4] P. Yianilos The Like It intelligent string comparison facility[R]. NEC Institute Tech Report 97-093,1997
[5] E Spertus ParaSite ; Mining structural information on the web[A].In: proceeding of The Sixth International
World Wide web Conference [C].1997
[6] K ,S Lawrence and C. Lee Giles CiteSeer. An Autonomous web Agent for Automatic Retrieval and
Identification of Interesting Publications [A].2nd International ACM Conference on Autonomous
Agents[C].-123,1998.
[7] 潘谦红、王炬、史忠植 基于属性论的文本相似度计算 计算机学报 1999 -655
[8] 张焕炯、王国胜、钟义信 基于汉明距离的文本相似度计算 计算机工程与应用 2001
-22
9
[9] 晋耀红 基于语境框架的文本相似度计算 计算机工程与应用 2004 -39
[10] 霍华 冯博琴 基于压缩稀疏矩阵矢量相乘的文本相似度计算 小型微型计算机系统 2005
-990
Document Similarity Model Based on Common Substring
Model
Su Zhen-kui,Tian Yuan
School of Software of Dalian University of Technology Dalian(116620)
Abstract
In order to overcome the problem of using word frequency excessively in document similarity
model, while paying less attention on the order of word in the document. The paper presents a
Common Substring Model, uses the difference between the serial numbers to get all
common substrings of two documents. Then it constructs a matrix by all common substrings.
Later it combines with the TFIDF method of VSM. At last, it uses a multi-level choice algorithm
(using length of the longest common substring) to get the result of the calculation of similarity. It
proves that CSM has better results than VSM in dataset TREC9.
Key words: Text; Similarity measure; Common Substring; Vector Space Model
作者简介
作者简介作者简介
作者简介：
：：
：苏振魁，男，1979年生，硕士研究生，主要研究方向是知识管理
田园，男，1966年生，副教授，主要研究方向是计算机密码学、计算机网络、
网络安全等等。
10
