如何确定普通话的Levenshtein距离？

Question

我们正在开发一个系统,使用UTF-8,UTF-16和UTF-32 Unicode字符标准对50多种国际语言进行模糊匹配.到目前为止,我们已经能够使用Levenshtein距离来检测德语Unicode扩展字符单词的拼写错误.

我们希望扩展这个系统来处理用Unicode表示的普通话中文表意文字.我们如何在相似的汉字之间进行Levenshtein距离计算？

Answer 1

首先,只是为了澄清:汉字并不等同于德语或英语单词.大多数你认为是单词的东西(使用"单词"的语义或句法定义)由1-3个字符组成.通过将Levenshtein距离表示为UCS-2或UCS-4代码点的序列,可以直接将Levenshtein距离应用于这些字符序列.由于大多数单词很短(特别是长度为1或2个字符的单词),但它的用途可能有限.

但是,由于您的问题是关于单个字符之间的编辑距离,我认为需要采用不同的方法,而且确实可能​​非常困难.

首先,您必须将每个字符表示为它所包含的组件/笔划的序列.有两个问题:

• 有些组件本身由更小的组件组成,因此如何将字符分解为"原子"组件并不是唯一定义的.如果按照单个笔划的水平进行操作,则需要对每个笔划(角色,形状,方向等内的位置)进行表征.我不认为每个人都这样做(如果有人告诉我,我会感兴趣).

• 您需要将笔划或组件放入订单中.明显的候选者是角色的规范笔画顺序,在lexica中有描述,甚至还有带有动画笔画顺序图的字典网站.但是,我所知道的数据源(日语)会将这些动画生成为位图图形序列; 我从未见过以适合编辑距离计算的形式表示笔画序列(甚至是单个笔画名称)的人或机器可读代码.

但是,您可以尝试的最后一件事是渲染字符字形并根据需要更改多少像素(或矢量)以将一个字符转换为另一个字符来计算编辑距离.我曾经在OCR后期校正的背景下对拉丁字符和字符组合(以像素为基础)做了这个,结果非常令人鼓舞.

快速回答larsmans评论如下:Unicode标准定义了两个相关概念(下面我将参考6.0版本,第12章):

1. 基于激进和中风计数的指数.每个汉字都由几个组成部分组成,其中一个是激进分子.基础/笔划计数索引是按部首排序的字符列表(即,所有共享相同基团的字符组合在一起),并且每个基础特定组内部按字符其余部分中使用的笔划数排序.不幸的是,即使这不是唯一的定义 - 有些字符的根本由不同的传统词汇定义不同,并且笔画计数也很困难.以下是Unicode标准所说的内容:

   为了加快在代码表中定位特定的汉字表意字符,Unicode网站上提供了基本笔画索引.[...]最具影响力的激进笔画信息权威是十八世纪的康熙字典,其中包含214个激进派.今天使用康熙激进派的主要问题是,许多简化字符很难在214个康熙激进派中任何一个进行分类.结果,引入了各种现代激进集.然而,没有一个是普遍使用的,214康熙的激进分子仍然是最知名的.[...] Unicode激进笔画图基于康熙激进派.Unicode标准遵循许多不同的激进笔划分类来源.如果两个来源对于给定角色的激进或笔画计数存在争议,则在激进笔画图表中的两个位置都会显示该角色.

   请注意,即使我们假设激进/笔划索引是明确和正确的,它也不足以作为将字符转换为组件序列的信息源,因为完全描述的字符的唯一组成部分是基.

2. 表意描述序列(第12.2节):Unicode定义了字符基本组件的代码点(大多数字符本身可以用作独立字符),并且有一些代码点用于将这些代码点粘合在一起形成一系列描述构成一个更复杂的角色.所以这种方式类似于组合字符,但有一些重要的区别:

   1. 组件的顺序不是唯一定义的
   2. 对于这样的序列没有定义渲染机制
   3. 没有从普通字符到相应的表意描述序列的映射(尽管标准提到这种映射在某种程度上存在于它们用于编译汉字符集的源中).

   标准建议使用表意描述序列来描述任何现有代码点都没有表示的复杂或罕见的特征; 但它明确地不鼓励使用描述序列代替普通字符:

   特别是,表意描述序列不应用于在数据交换中提供编码的表意文字的替代图形表示.搜索,整理和其他基于内容的文本操作将失败.