本发明涉及中文字符串相似度领域， 尤其涉及一种基于编辑距离计 算中文字符串相似度的方法及装置。

背景技术

中文字符串相似度的比较是字符串匹配、 文本比较、 信息抽取等技 术领域中常见的技术。 在不同的应用场合会釆取不同的中文字符串相 似 度的技术手段， 常见的技术手段有基于编辑距离的匹配算法、 基于字形 和发音的匹配算法以及 smith-Waterman 巨离算法。

在编辑距离算法中， 求两个字符串相似度的步骤有以下几步： 第一， 应预先建构好编辑距离矩阵； 第二， 依次由左到右， 上到下计算矩阵单 元的值； 第三， 计算出的最右下的矩阵单元值即为两个字符串 的编辑距 离。 该算法适合于拼写错误， 且易于实现、 使用。

基于字形和发音的算法中， 求两个字符串相似度的步骤包括以下几 步： 首先，利用字形编码-五笔编码计算字符串之� �的字形相似度； 第二， 利用汉字声母、 韵母的发音规律来计算字符串的声母相似度和 韵母相似 度， 并结合方言或者普通话中常见的模糊音， 计算字符串之间的发音相 似度。 为了提高精确度， 很多应用场景下会同时釆取编辑距离算法和基 于汉字字形和发音的算法用以提高计算字符串 相似度的精度。 而 smith- Waterman算法是编辑距离算法的改进版， 其改进的地方在 于： 通过釆用对删除、 插入和替换三种操作分别进行补偿操作来计算 矩 阵单元值。 该算法目前是被广泛使用的序列相似性比较算 法， 其适用于 寻找局部相似序列对。

在面对中文语言环境下中文字符串匹配这一具 体问题时， 经典的基 于编辑距离进行字符串相似度匹配方法的实用 性有所下降。 基于汉字字 形的算法虽然考虑到了字形， 但是仅是根据汉字的五笔编码。

发明内容

为了解决上述缺陷之一。

因此， 本发明实施例提供一种基于编辑距离计算中文 字符串相似度 的方法及装置。 本发明釆用四角号码编码将字符串中的汉字转 换成四角 编码， 从而基于编辑距离计算汉字的相似度， 在此基础上用汉字的相似 度替代编辑距离的权重， 进而计算字符串的相似度。 本发明将汉字转换 成数字串进行比较提高了汉字匹配的精度， 利用该汉字的相似度替代编 辑距离的权重来计算字符串的相似度实现了编 辑距离算法在中文语言环 境下中文字符串匹配的实用性， 并提高了匹配结果的精确性。

所以， 本发明一个实施例提供一种基于编辑距离计算 中文字符串相 似度的方法， 该方法先计算待比较字符串中汉字的相似度， 再计算待比 较中文字符串的相似度。 所述方法包括： 所述汉字相似度的计算包括以 下步骤：

釆用四角号码将汉字转换成四角编码； 釆用编辑距离计算汉字的相似度；

所述待比较中文字符串相似度的计算包括以下 步骤：

釆用汉字的相似度代替编辑距离的权重；

基于改进的编辑距离计算待比较字符串的相似 度。

优选地， 所述将汉字转换成四角编码包括： 预先建立四角号码检字 法的规则表格； 根据上述规则表格将待比较字符串中的汉字转 换成对应 的四角编码。

本发明另一个实施例提供一种基于编辑距离计 算中文字符串相似度 的装置， 该装置包括： 汉字相似度计算装置， 用以获取根据编辑距离计 算汉字相似度； 中文字符串相似度计算装置， 用以获取待比较字符串的 相似度。

优选地， 所述汉字相似度计算装置包括四角号码规则装 置和四角编 码装置；

所述四角号码规则装置，用以预先建立四角号 码检字法的规则表格； 所述四角编码转换装置根据四角号码规则装置 中的规则信息将待比 较字符串中的汉字转换成四角编码；

所述汉字相似度计算装置获取四角编码转发装 置中的数字串， 并基 于编辑距离计算汉字的相似度。

优选地， 所述中文字符串相似度计算装置包括编辑距离 权重装置； 所述编辑距离权重装置获取汉字相似度计算装 置中汉字的相似度信 息， 并设置为编辑距离的权重；

所述汉字相似度计算装置获取编辑距离装置中 权重信息， 基于改进 的编辑距离计算字符串的相似度。

附图说明

图 1是本发明实施例实现的一种基于编辑距离计� �中文字符串相似 度的方法的流程示意图。

图 2是本发明实施例釆用编辑距离计算汉字相似� �的流程示意图。 具体实施方式

为了使本发明的目的、 技术方案及优点更加清楚明白， 以下结合附 图及实施例， 对本发明进行进一步的详细说明。 应当理解， 此处所描述 的具体实施例仅仅用于解释本发明， 并不用于限定本发明。

本发明实施例提供一种基于编辑距离计算中文 字符串相似度的方法 及装置。 本发明釆用四角号码编码将字符串中的汉字转 换成四角编码， 从而基于编辑距离计算汉字的相似度， 在此基础上用汉字的相似度替代 编辑距离的权重， 进而计算字符串的相似度。 本发明将汉字转换成数字 串进行比较提高了汉字匹配的精度， 利用该汉字的相似度替代编辑距离 的权重来计算字符串的相似度实现了编辑距离 算法在中文语言环境下中 文字符串匹配的实用性， 并提高了匹配结果的精确性。

如图 1所示， 是本发明一个实施例实现的一种基于编辑距离 计算中 文字符串相似度的方法的流程示意图， 该方法先计算待比较字符串中汉 字的相似度， 再计算待比较中文字符串的相似度。 具体包括以下详细步 骤：

步骤 S110: 釆用四角号码将汉字转换成四角编码。

为了本发明的实施， 本发明实施例需要釆用四角号码和编辑距离算 法。 所谓四角号码是指： 汉语词典常用检字方法之一， 用最多 5个阿拉 伯数字来对汉字进行归类。 四角号码检字法用数字 0到 9表示一个汉字 四角的十种笔形， 有时在最后增加一位补码。 所谓编辑距离算法是指： 又称 （Edit Distance ), 是指两个字串之间， 由一个转成另一个所需的最 少编辑操作次数。 许可的编辑操作包括将一个字符替换成另一个 字符， 插入一个字符， 删除一个字符。

在本步骤中， 需预先建立四角号码检字法的规则表格， 根据其编码 口诀为： 横一垂二三点捺， 叉四插五方块六， 七角八八九是小， 点下有 横变零头。

根据上述规则获取待比较字符串中的汉字， 如例 1中待比较中文字 符串 si中汉字为 "华傲数据" 和中文字符串 s2中汉字为 "中华骄傲"。

借助四角号码编码，可将汉字转换为以四角号 码表示的形式。 比如: 华， 四角号码为 24401 ; 花， 四角号码为 44214 , 具体如下表 1所示： 傲 28240 华 24401 数 98440 骄 72128 据 57064 傲 28240 表 1 汉字对应的四角号码

步骤 S120: 釆用编辑距离计算汉字的相似度。

若要计算字符串 si和字符串 s2的编辑距离， 首先定义这样一个函 数—— edit(i,j),它表示第一个字符串 si的长度为 i的子串到第二个字符 串 s2的长度为 j的子串的编辑距离。 显然可以有如下动态规划公式：

( 1 ) if i==0 JL j ==0, edit(i,j) = 0;

(2) if i==0 JL j >0, edit(i, j)=j;

(3 ) if i>0 JLj == 0, edit(i, j) = I;

(4)if0< i< 1 JL 0 <j < 1 , edit(i, j) == min{ edit(i-l, j) + 1, edit(i, j-1) + 1, edit(i-l,j-l) + f(i, j) }, 当第一个字符串的第 i个字符不等于第二 个字符串的第 j个字符时， f(i,j)= l; 否则， f(i,j) = 0。

本步骤釆用编辑距离计算汉字相似度的流程如 图 2所示。

首先获取例 1 中文字符串 si 和 s2 的各中文汉字长度 m和 n, 即 m=n=4。 根据上述编辑距离算法动态规划公式 （ 1)、 （2) 和 （3 ), 可得 初始化结果， 如下表 2所示: 中 华 骄 傲

0 1 2 3 4 华 1

傲 2

数 3 据 4

表 2 初始化结果

计算 Edit(i,j)的值， 即 si中长度为 i的字符串与 s2中长度为 j的字 符串的编辑距离。

首先计算 Edit(l,l)的值， 即串 "华" 与串 "中" 的编辑距离。 根据 动态规划公式 ( 4 ): Edit(i,j)= min{edit(i-l, j) + 1, edit(i, j-1) + 1, edit(i-l, j-l) + f(i,j) }, 其中， f(i, j)为 "华" 与 "中" 的编辑距离。

用编辑距离算法计算四角编码的编辑距离， 即对应中文字符的编辑 距离。

计算 edit(l, l), 如下表 3所示， edit(0, 1) + 1 ==2, edit(l, 0) + 1 == 2, edit(0, 0) + f(l, 1)==0+ 1 == 1, min(edit(0, 1), edit(l, 0), edit(0, 0) + f(l, 1))==1, 因此 edit(l, 1)== 1。

表 3: 汉字 "华" (24404) 与 "中" (50006)的编辑距离计算 (一）。 依次类推： edit(2, 1)+ 1 ==3, edit(l,2)+ 1 ==2, edit(l, l) + f(2, 2) == 1 + 1 ==2, 其中 sl[2]=='4， 而 s2[2]=='5，， 两者不同， 所以交换相 邻字符的操作不计入比较最小数中计算， 如下表 4和表 5所示。 5 0 0 0 6

0 1 2 3 4 5

2 1 1

4 2 2

4 3

0 4

1 5

表 4: 汉字 "华" ( 24404 ) 与 "中" (50006)的编辑距离计

表 5: 汉字 "华" ( 24404 ) 与 "中" (50006)的编辑距离计

所以， "华" ( 24401 ) 和 "中" ( 50006 ) 编辑距离为 4 , 4/5=0.8„ 在本步骤中将汉字转换成数字串进行相似度比 较， 可以避免根据汉 字的字形和声音进行相似度匹配存在的模糊性 ，提高了汉字匹配的精度。

步骤 S130: 釆用汉字的相似度代替编辑距离的权重。

利用上述汉字的相似度替代编辑距离的权重来 计算待比较字符串的 相似度实现了编辑距离算法在中文语言环境下 中文字符串匹配的实用 性， 并提高了匹配结果的精确性。

步骤 S140: 基于改进的编辑距离计算待比较字符串的相似 度。

所以， 在步骤 S 120 中， f(i, j)的值为 0.8 , 即 "华" 与 "中" 的编 辑距离为 0.8。 Edit(i,j)= min{edit(i-l, j) + 1, edit(i, j-1) + 1, edit(i-l, j-1) + f(i, j) }={ 1+1, 1+1,0+0.8} = 0.8。 依次类推， 计算 Edit(i,j)的值， 其中 0<i<=m;0<j<=n。 结果 ^下表 6所示：

表 5: 中文字符串 "华傲数据" 与 "中华骄傲" 编辑距离计算 故本发明实施例中例 1中文字符串 "华傲数据" 与 "中华骄傲" 编 辑距离为 3.2 , 相似度为 1-3.2/4 = 0.2。

本发明另一个实施例提供一种基于编辑距离计 算中文字符串相似度 的装置， 该装置包括： 汉字相似度计算装置， 用以获取根据编辑距离计 算汉字相似度； 中文字符串相似度计算装置， 用以获取待比较字符串的 相似度。

所述汉字相似度计算装置包括四角号码规则装 置和四角编码装置； 所述四角号码规则装置，用以预先建立四角号 码检字法的规则表格， 根据其编码口诀为： 横一垂二三点捺， 叉四插五方块六， 七角八八九是 小， 点下有横变零头。

根据上述规则获取待比较字符串中的汉字， 如上例 1中待比较中文 字符串 sl中汉字为 "华傲数据"和中文字符串 s2中汉字为 "中华骄傲"。 所述四角编码转换装置根据四角号码规则装置 中的规则信息将待比 较字符串中的汉字转换成四角编码， 如上例 1所示待比较中文字符串 sl 中汉字为 "华傲数据" 和中文字符串 s2中汉字为 "中华骄傲"， 华， 四 角号码为 24401 ; 花， 四角号码为 44214。

汉字相似度计算装置获取四角编码转发装置中 的数字串， 并基于编 辑距离计算汉字的相似度。 获取例 1 中文字符串 sl和 s2的各中文汉字 长度 m和 n, 即 m=n=4。 根据上述编辑距离算法动态规划公式（ 1 )、 ( 2 ) 和 （3 ), 可得初始化结果， 计算 Edit(i,j)的值， 即 sl 中长度为 i的字符 串与 s2中长度为 j的字符串的编辑距离。

首先计算 Edit(l,l)的值， 即串 "华" 与串 "中" 的编辑距离。 根据 动态规划公式 ( 4 ): Edit(i,j)= min{edit(i-l, j) + 1, edit(i, j-1) + 1, edit(i-l, j-l) + f(i, j) }其中, f(i, j)为 "华" 与 "中" 的编辑距离。

用编辑距离算法计算四角编码的编辑距离， 即对应中文字符的编辑 距离。计算 edit(l, 1) ,如下表 3所示， edit(0, 1) + 1 == 2 , edit(l, 0) + 1 == 2 , edit(0, 0) + f(l, 1) == 0 + 1 == 1 , min(edit(0, 1) , edit(l, 0) , edit(0, 0) + f(l, 1))==1 , 因此 edit(l, 1) == 1。

所述中文字符串相似度计算装置包括编辑距离 权重装置； 所述编辑 距离权重装置获取汉字相似度计算装置中汉字 的相似度信息， 并设置为 编辑距离的权重； 所述汉字相似度计算装置获取编辑距离装置中 权重信 息，基于改进的编辑距离计算字符串的相似度 。 f(i, j)的值为 0.8 ,即 "华" 与 "中" 的编辑距离为 0.8。 Edit(i,j)= min{edit(i-l, j) + 1, edit(i, j-1) + 1, edit(i-l, j-1) + f(i, j) }={1 + 1, 1+1,0+0.8} = 0.8。 依次类推， 计算 Edit(iJ) 的值， 其中 0<i<=m;0<j<=n。 故本发明实施例中例 1 中文字符串 "华傲 数据" 与 "中华骄傲" 编辑距离为 3.2 , 相似度为 1-3.2/4 = 0.2。 本发明实施例提供一种基于编辑距离计算中文 字符串相似度的方法 及装置。 本发明釆用四角号码编码将字符串中的汉字转 换成四角编码， 从而基于编辑距离计算汉字的相似度， 在此基础上用汉字的相似度替代 编辑距离的权重， 进而计算字符串的相似度。 本发明将汉字转换成数字 串进行比较提高了汉字匹配的精度， 利用该汉字的相似度替代编辑距离 的权重来计算字符串的相似度实现了编辑距离 算法在中文语言环境下中 文字符串匹配的实用性， 并提高了匹配结果的精确性。

以上内容是结合具体的优选实施方式对本发明 所作的进一步详细说 明， 不能认定本发明的具体实施只局限于这些说明 。 对于本发明所属技 术领域的普通技术人员来说， 在不脱离本发明构思的前提下， 还可以做 出若干简单推演或替换。