一种数据相似度分析方法[发明专利]

(12)发明专利申请

(10)申请公布号 CN 105183832 A (43)申请公布日 2015.12.23

(21)申请号 2015105966.8(22)申请日 2015.08.31

(71)申请人成都康赛信息技术有限公司

地址6100 四川省成都市一环路东一段

159号电子信息产业大厦410室(72)发明人唐雪飞 陈科

(74)专利代理机构成都宏顺专利代理事务所

(普通合伙) 51227

代理人周永宏(51)Int.Cl.

G06F 17/30(2006.01)

权利要求书1页 说明书6页 附图1页

()发明名称

一种数据相似度分析方法(57)摘要

本发明公开了一种数据相似度分析方法，包括以下步骤：S1、设置得分策略；S2、构建得分矩阵；S3、填充得分矩阵；S4、对得分矩阵进行回归，得到两组数据的比较结果。本发明引入了得分策略，并根据策略计算分值，用于定量判断数据之间的相似程度，能够针对非精确匹配的情况进行相似度比较。

C N 1 0 5 1 8 3 8 3 2 A CN 105183832 A

权 利 要 求 书

1/1页

1.一种数据相似度分析方法，其特征在于，包括以下步骤：

S1、设置得分策略；S2、构建得分矩阵；S3、填充得分矩阵；S4、对得分矩阵进行回归，得到两组数据的比较结果。2.根据权利要求1所述的数据相似度分析方法，其特征在于，所述步骤S1具体为：假设待比较的两组数据为S＝s1s2…sn和T＝t1t2…tm，长度分别为n和m，通过在S和T中适当位置插入空格“-”得到S′和T′，使得|S′|＝|T′|＝l；

比较S′和T′，如果在位置i上的值相等，则得1分，如果在位置i上的值不相等且都不为空格，则得0分，如果在位置i上的值有空格，则得-1分，即扣分，如公式(1)所示：

其中σ(S′[i],T′[i])是在位置i上的得分；

则数据S和T的最终得分为：

3.根据权利要求2所述的数据相似度分析方法，其特征在于，所述步骤S2具体为：构建(n+1)×(m+1)阶矩阵V，除V(0,0)外，第1列与数据序列S相对应，第1行与数据序列T相对应；

矩阵V初始条件如公式(3)所示：V(0,0)＝0

V(i,0)＝V(i-1,0)+σ(S[i],-),1≤i≤|S| (3)。V(0,j)＝V(0,j-1)+σ(-,T[i]),1≤j≤|T|4.根据权利要求3所述的数据相似度分析方法，其特征在于，所述步骤S3具体为：根据得分策略，利用公式(4)将矩阵V中剩余的空格与其已知的相邻位置的值进行求和比较，将最大的值填充到单元格中：

5.根据权利要求4所述的数据相似度分析方法，其特征在于，所述步骤S4具体为：

从V(|S|,|T|)出发，回归其来源，并以箭头标记，得到数据S和T的比较结果。

2

CN 105183832 A

说 明 书

一种数据相似度分析方法

1/6页

技术领域

[0001]

本发明属于计算机商业智能技术领域，具体涉及一种数据相似度分析方法的设

计。背景技术

随着信息技术的发展，许多IT领域每天都会产生大量的数据，而在许多业务环境中，存在着不同的数据库，这些数据库中都存储着大量的数据，而这些数据往往都存在着一定的相似性，比如在某高校的业务数据中，教务系统和学工系统中都保存着大量的与学生相关的数据。

[0003] 在这样的情况下，我们很多时候都非常关心这些不同数据源之间的相似程度，以便分析这些数据之间的冗余情况。这些不同的数据一般都是以不同的数据格式存储的，一般有数值型、字符型、日期型等，而众所周知，对计算机而言，这些数据都是以二进制数的形式存储的，进一步，这些不同数据格式都可以转化为字符串型，因此，数据相似度比较的相关技术，实际上可以转化为字符串比较的相关技术。字符串比较相关的技术主要包括：[0004] 1、朴素比较方法

[0005] 直接比较字符在相应位置是否相同来确定二者的相似程度。由于需要全部遍历，因此比较过程需要消耗更多的时间。朴素比较方法的优点在于实现简单，可用于数据量较少的情况，但对于大数据量的场景，一般不使用这种原始的数据比较方法。[0006] 2、BM方法

[0007] BM方法是精确字符串匹配的Boyer-Moore的简称。这种方法的时间复杂度较低，是现在用的比较多的一种方法。

[0008] 所谓精确字符串匹配问题，是在文本T中找到所有与查询P精确匹配的子串。BM算法主要用了三种巧妙而有效的方法，即从右到左扫描，坏字符规则和好后缀规则。[0009] 从右到左扫描的意思是从最后一个字符开始向前匹配，而不是习惯上的从开头向后匹配。

[0010] 坏字符规则是，从右到左的扫描过程中，发现Ti与Pj不同，如果P中存在一个字符Pk与Ti相同，且k[0012] (1)如果t与t'的前一个字母不相同，就将P向右移，使t'与T中的t对齐。[0013] (2)如果t'没有出现，则找到与t的后缀相同的P的最长前缀x，向右移动P，使x与T中t的后缀相对应。

[0002]

3、KMP方法

[0015] KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt

[0014]

3

CN 105183832 A

说 明 书

2/6页

同时发现。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

[0016] KMP方法在执行字符串T和W比较时，对T[i]和W[j]的匹配检查。若T[i]＝W[j]，则继续检查T[i+1]和W[j+1]是否匹配。若T[i]≠W[j]，则分成两种情况：若j＝1，则模式串右移一位，检查T[i+1]和W[1]是否匹配；若1本发明的目的是为了解决现有技术中字符串比较方法只能进行精确的比较，对于非精确匹配不能得到相似性的结果的问题，提出了一种数据相似度分析方法。[0019] 本发明的技术方案为：一种数据相似度分析方法，包括以下步骤：[0020] S1、设置得分策略；[0021] S2、构建得分矩阵；[0022] S3、填充得分矩阵；[0023] S4、对得分矩阵进行回归，得到两组数据的比较结果。[0024] 进一步地，步骤S1具体为：假设待比较的两组数据为S＝s1s2…sn和T＝t1t2…tm，长度分别为n和m，通过在S和T中适当位置插入空格“-”得到S′和T′，使得|S′|＝|T′|＝l；

[0025] 比较S′和T′，如果在位置i上的值相等，则得1分，如果在位置i上的值不相等且都不为空格，则得0分，如果在位置i上的值有空格，则得-1分，即扣分，如公式(1)所示：

[0018] [0026]

其中σ(S′[i],T′[i])是在位置i上的得分；

[0028] 则数据S和T的最终得分为：

[0027] [0029]

进一步地，步骤S2具体为：构建(n+1)×(m+1)阶矩阵V，除V(0,0)外，第1列与

数据序列S相对应，第1行与数据序列T相对应；[0031] 矩阵V初始条件如公式(3)所示：[0032] V(0,0)＝0

[0030]

4

CN 105183832 A[0033]

说 明 书

3/6页

V(i,0)＝V(i-1,0)+σ(S[i],-),1≤i≤|S| (3)。[0034] V(0,j)＝V(0,j-1)+σ(-,T[i]),1≤j≤|T|[0035] 进一步地，步骤S3具体为：根据得分策略，利用公式(4)将矩阵V中剩余的空格与其已知的相邻位置的值进行求和比较，将最大的值填充到单元格中：

[0036]

进一步地，步骤S4具体为：从V(|S|,|T|)出发，回归其来源，并以箭头标记，得到数据S和T的比较结果。

[0038] 本发明的有益效果是：本发明引入了得分策略，并根据策略计算分值，用于定量判断数据之间的相似程度，能够针对非精确匹配的情况进行相似度比较。

[0037]

附图说明

[0039]

图1为本发明提供的一种数据相似度分析方法流程图。

具体实施方式

下面结合附图对本发明的实施例作进一步的说明。[0041] 本发明提供了一种数据相似度分析方法，如图1所示，包括以下步骤：[0042] S1、设置得分策略。

[0043] 假设待比较的两组数据为S＝s1s2…sn和T＝t1t2…tm，长度分别为n和m，为了可以定量地表示二者的相似程度，引入得分策略，并根据策略计算分值，用于最终表示二者的相似度。

[0044] 在进行S和T的比较过程中，由于二者的长度不同，需要对S和T进行扩展，也就是需要在S和T中的适当位置插入一些空格(用符号“-”表示)，保证二者的长度一致，且在得分策略的条件下分值最高，则该分值就是最终的相似度。因此，如何找到这些合适的空格位置，是本发明的关键。设通过在S和T中合适的位置插入空格得到S′和T′，且|S′|＝|T′|＝l。

[0045] 比较S′和T′，如果在位置i上的值相等，则得1分，如果在位置i上的值不相等且都不为空格，则得0分，如果在位置i上的值有空格，则得-1分，即扣分，如公式(1)所示：

[0040] [0046]

其中σ(S′[i],T′[i])是在位置i上的得分。

[0048] 值得注意的是，S′和T′位置i上不可能同时为空格，因为空格是人为引入的，在同一位置都引入空格没有意义。

[0049] 则数据S和T的最终得分为：

[0047]

5

CN 105183832 A[0050]

说 明 书

4/6页

S2、构建得分矩阵。

[0052] 构建(n+1)×(m+1)阶矩阵V，除V(0,0)外，第1列与数据序列S相对应，第1行与数据序列T相对应；

[0053] 矩阵V初始条件如公式(3)所示：[00] V(0,0)＝0

[0055] V(i,0)＝V(i-1,0)+σ(S[i],-),1≤i≤|S| (3)。[0056] V(0,j)＝V(0,j-1)+σ(-,T[i]),1≤j≤|T|[0057] 本发明实施例中，S＝MNMXYMX，T＝MNYNX，则矩阵V如下：

[0051] [0058]

S3、填充得分矩阵。[0060] 根据得分策略，利用公式(4)将矩阵V中剩余的空格与其已知的相邻位置(即上、下、左、右和斜线相邻位置)的值进行求和比较，将最大的值填充到单元格中：

[0059]

[0061]

例如，当i＝1,j＝1时，V(i,j)＝V(1,1)，S[i]＝S[1]＝T[j]＝T[1]＝M,则σ(S[i],T[j])＝1，而V(i-1,j-1)＝V(0,0)＝0，V(i-1,j)＝V(0,1)＝-1,V(i,j-1)＝V(1,0)＝-1，因此根据公式(4)，最大值V(i,j)＝0+1＝1。后续单元格的值按公式(4)递推可得。

[0063] 则上述实施例的得分矩阵填充结果为：

[0062] [00]

6

CN 105183832 A

说 明 书

5/6页

S4、对得分矩阵进行回归，得到两组数据的比较结果。[0066] 本发明实施例中，V(|S|,|T|)的值2即为最终比较的分值，回归过程即是倒推打分顺序的过程：从V(|S|,|T|)出发，回归其来源，并以箭头标记，得到数据S和T的比较结果。则回归结果为：

[0065] [0067]

回溯规则为：从最后一格V(|S|,|T|)出发，查看每一个单元格的值是根据公式

(4)的哪一个分项计算得到的，如果是第一个，即V(i,j)＝V(i-1,j-1)+σ(S[i],T[j])，则表明来源单元格上一斜对角线单元格；如果是第二个，即V(i,j)＝V(i-1,j)+σ(S[i],-)，则表明来源单元格为正上方单元格，表示将在S中插入一个空格；如果是第三个，即V(i,j)＝V(i,j-1)+σ(-,T[j])，则表明来源单元为左方单元格，表示将在T中插入一个空格。[0069] 根据以上规则，该路径对应的比较结果为：[0070] MN--YNX[0071] MNMXYMX

[0072] 即在S的第3、4号位插入两个空格，得到的数据与T的相似度最高，具体相似度为2。

[0068]

7

CN 105183832 A[0073]

说 明 书

6/6页

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。

8

CN 105183832 A

说 明 书 附 图

1/1页

图1

9