c++ - 如何确定普通话字符的 Levenshtein 距离？

Question

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

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

Answer 1

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

但是，由于您的问题专门针对 单个字符之间的编辑距离 ，我相信需要一种不同的方法，这可能确实非常困难。

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

一些组件本身包含更小的 组件 ，因此如何将字符分解为“原子”组件并不是唯一定义的。如果你做到个人层面笔画 ，您需要对每个笔画进行表征(字符内的位置、形状、方向等)。我不认为每个人都这样做(如果有人告诉我，我会最感兴趣)。

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

不过，您可以尝试的最后一件事是渲染角色 字形 并根据需要更改多少像素(或 vector )以将一个字符转换为另一个字符来计算编辑距离。我曾经在 OCR 后更正的上下文中对拉丁字符和字符组合(以像素为基础)进行了此操作，结果非常令人鼓舞。

对 larsmans 评论的快速回答如下:Unicode 标准定义了两个相关概念(在下面我指的是 6.0 version, chapter 12):

基于部首和笔画计数的索引。每个汉字由几个部分组成，其中之一是部首。部首/笔画计数索引是按部首排序的字符列表(即，共享相同部首的所有字符组合在一起)，并且每个部首特定组在内部按字符其余部分使用的笔画数排序。不幸的是，即使这也不是唯一定义的——有些字符的部首由不同的传统词汇定义，并且笔画计数也可能很困难。这是Unicode标准所说的:

To expedite locating specific Han ideographic characters in the code charts, radical-stroke indices are provided on the Unicode web site. [...] The most influential authority for radical-stroke information is the eighteenth-century KangXi dictionary, which contains 214 radicals. The main problem in using KangXi radicals today is that many simplified characters are difficult to classify under any of the 214 KangXi radicals. As a result, various modern radical sets have been introduced. None, however, is in general use, and the 214 KangXi radicals remain the best known. [...] The Unicode radical-stroke charts are based on the KangXi radicals. The Unicode Standard follows a number of different sources for radical-stroke classification. Where two sources are at odds as to radical or stroke count for a given character, the character is shown in both positions in the radical-stroke charts.

请注意，即使我们假设部首/笔画索引是明确且正确的，也不足以作为将字符转换为组件序列的信息源，因为由此完全描述的字符的唯一组件是激进的。

表意描述序列(第 12.2 节):Unicode 为字符的基本组成部分定义了代码点(它们中的大多数本身无论如何都可以用作独立字符)，并且有代码点用于将它们粘合在一起以形成描述字符的组成部分的序列组成一个更复杂的字符。因此，这与组合字符的工作方式类似，但存在重要区别:

组件的顺序不是唯一定义的

对于此类序列，没有定义渲染机制

没有从普通字符到相应的表意描述序列的映射(尽管标准提到这种映射在某种程度上存在于它们用于编译汉字符集的源中)。

该标准建议使用表意描述序列来描述没有由任何现有代码点表示的复杂或稀有字符；但它明确不鼓励使用描述序列代替普通字符:

In particular, Ideographic Description Sequences should not be used to provide alternative graphic representations of encoded ideographs in data interchange. Searching, collation, and other content-based text operations would then fail.