常见的字符串相似度算法包括编辑距离算法（EditDistance）、n-gram算法、JaroWinkler算法和Soundex算法。 本文将简要介绍这些算法。 有兴趣的读者可以在网上找到一些更详细的信息。
最常见的相似度算法是编辑距离算法，它将两个字符串的相似度归结为将一个字符串转换为另一个字符串的成本。 转换成本越高，两个字符串之间的相似度越低。 可选择的常见转换方法包括插入、替换和删除。
N-Gram 算法基于这样的假设：字符串中第 n 个单词的出现仅与前面的 n-1 个单词相关，与任何其他单词无关。 整个字符串出现的概率是单词出现概率的乘积。 N-gram 本身也表示目标字符串中长度为 n 的子字符串。 例如，“ARMY”中的“ARM”是一个 3 元语法。 当两个字符串具有更多相同的 n-gram 时，这两个字符串将被认为更相似。
Jaro Winkler 将 n 元语法算法又向前推进了一步。 转置时也会考虑n-gram中不匹配的部分，从而能够得到更准确的相似度。 JaroWinkler 在比较两个较短的字符串时能够取得良好的结果。
Soundex 算法与之前的算法不一样。 该算法的特点是它关注的问题不是两个字符串文本的相似度，而是发音的近似。 首先，该算法将两个字符串通过一定的哈希算法转换为哈希值。 该值由四个字符组成。 第一个字符是英文字母，后三个字符是数字。 转换的哈希算法不是随机选择的，而是使用拉丁字符串的近似发音。
获得两个字符串的发音哈希值后，算法再计算两个哈希的相似度，从而获得输入字符串的发音相似度。
Soundex算法的另一个应用场景是，用户在进行模糊查询时，可以通过Soundex值进行过滤，以提高查询性能。
问题描述
这些常见的字符串相似度算法在处理拉丁文本文本匹配时可以取得非常好的效果。 它们本身最初是为了解决拉丁语写作中遇到的问题而发明的。 然而，对于象形文字的相似度计算，比如中文，这些算法就捉襟见肘了。
为了显示：
南通市 – 南通市 – 北通市
对于编辑距离算法来说，南通市与南通市之间的相似度与南通市与北通市之间的相似度完全相同，因为两者都需要付出相同的成本来转换为对方。 使用N-Gram算法，得到相同的结果。 不过，对于熟悉汉字的人来说，南通市和南通市的相似度应该更接近一些。 因为两者的发音完全一样。
既然是发音问题，那么是否可以使用Soundex算法来解决呢？ 目前看来还是做不到，因为Soundex算法更注重拉丁字符的发音。 对于中文来说，Soundex算法是无能为力的。
如果这个例子只是说明发音相同，拉丁字符也有类似的问题，那么下面的例子描述了只存在于象形文字中的相似问题：
有礼貌有礼貌——杉杉有礼貌
如果从解决拉丁字符相似度的角度来看，那么这两个字符串的相似度只有50%左右，因为四个字符中有两个是完全不同的。 这两个角色不仅长相不同，连发音也完全不同。
然而，对于熟悉汉字的人来说，这两个输入应该非常相似。 因为第一个和第二个字符虽然不同，但字形非常相似。
这种情况在手写输入时经常发生。 例如，客户填写快递单：
江苏省南通市紫狼路100号
快递员在签收快递时，可能需要将地址输入到系统中，或者快递公司使用先进的扫描设备，可以将地址扫描到系统中。 假设顾客的字迹很潦草、快递员的粗心或者扫描仪不够智能，都可能导致以下文字输入错误：
江苏省南通市紫娘路100号
如何识别此类相似的中文短语是现有算法难以解决的问题。
中文字符串相似度有其独特的特点，这是有别于任何其他语言的。 然而，在现实世界中，我们经常面临这样的问题。 正如我们刚才看到的例子，最常见的场景是中文纠正。
我们迫切需要找到一种新的算法来解决这个问题。
问题分析
想要解决中文字符串的相似度匹配问题，量化中文相似度的结果，首先必须对单个汉字的特征有一定的了解。 比较一下“狼”和“狼”的相似度和“狼”和“娘”的相似度，哪个更高？ 量化的依据是什么？ “篮子”和“南”呢？ 他们之间有相似之处吗？ 只有弄清楚这些问题，我们才能设计出优秀的算法来计算中文字符串之间的相似度。
经过长时间的研究和准备，并不断思考和总结我们在工作中遇到的中文相似问题，我们做出了以下总结。 中文的相似问题主要归结为三个方面。
同音字
汉字的同音字可以说是外国人学习汉语的一大难题。 两个完全不同的汉字可能有相同的读音。
当我们对两个汉字进行相似度匹配时，要考虑读音是否相同或相似。
对于同音词，如果只考虑其发音的相似度，很容易提供这样的相似度算法。 只需要将汉字转换成对应的拼音，然后使用传统的相似度匹配算法，例如编辑距离。 算法可以达到很好的效果。
方言很容易混淆单词的发音
在中国各个省市、不同地区都有不同的方言。 这也导致在一些口音较重的地区无法识别某些拼音之间的差异。
最常见的例子是，很多南方人很难区分“L”和“N”。 他们经常混淆两种声音，将“篮球”读成“南球”，将“刘德华”读成“南球”。 “牛德华”。
解决方言中读音混乱的方法与解决同音字的方法非常相似。 你只需要将汉字转换成拼音，然后再转换一些容易混淆的音标unity c# 查询列表 字符串相似度排序，然后识别它们的相似之处。
当然，也可以通过在计算近似度时对容易混淆的音标设置较高的比例来解决这个问题。
一些常见的、容易混淆的音标包括：
“AN”-“ANG”
“Z”-“ZH”
“C”-“CH”
“EN” – “ENG”
类似的字形
最后一个相似问题，也是最难解决的问题，是汉字形状的相似。
汉字作为世界上仅存的少数象形文字之一unity c# 查询列表 字符串相似度排序，其表现形式与世界主流使用的拉丁语言体系完全不同。 作为拼音文字，拉丁文字是表音的，即文字的形状代表其发音。 象形文字是表意文字。 汉字本身就表达了其隐藏的含义。
文章开头我们提到的所有相似度匹配算法都无法正确区分两个不同汉字之间字形的异同2d游戏素材，更不用说计算它们的相似度了。
关于这个问题，一个简单的想法是，首先将汉字转换为字母和数字的序列，并且这个转换中使用的哈希算法必须能够保留汉字的字形特征。 利用这种变换，我们将汉字字形的相似性问题转化为两组字母数字序列的相似性问题。 这是传统相似匹配算法的优势。
该方案的核心在于找到一种合适的哈希算法，能够正确地转换汉字，并在转换结果中保留汉字的字形特征。
在另一篇论文中，作者提到使用一种称为四角编码的汉字检测方法来实现这样的算法。 四角算法是王允武于1925年发明的，这种编码方法根据汉字所包含的单笔画或多笔画对汉字进行编号，并取左上角、右上角、左下角、右下角的笔画形状。汉字的一角。 ，将汉字转换为最多五位的阿拉伯数字。 通过将汉字转换为四角码，然后计算四角码的相似度，就可以得到两个汉字的字形相似度。
四角数的编码方法不是本文的重点。 有兴趣的读者可以访问该网站：了解更多信息。
利用四角编码来计算汉字的相似度可以在一定程度上解决相似字的问题。
然而，四角编码也有其自身的问题。 由于只取汉字的四角笔画，一些形状完全不同的汉字也因为四角结构相同而具有相同的四角编码。
例如：
卷 - 6010
第6010天
即使是没学过中文的人，一眼就能看出这两个字形的区别。 如果我们只使用四角编码，我们就会得出两个汉字相似度为100%的可笑结论。
结合上述三个有关汉字相似度的问题，我们发现每个解决方案都旨在解决整个问题集的一个子集。 这种划分不同场景的方式往往会给用户带来麻烦。 因此，我们想是否有一种方法可以将这三种解决方案合而为一，取其优点，消除其缺点，一次性彻底解决中文相似问题？
这个问题引起了我的思考。
声型代码 (SSC)
为了解决上面文章中描述的问题，我在工作中积累了相关经验，开发了音形码这种汉字编码方法，来解决中文相似度算法的问题。
首先，什么是音码？ 拼音码是将汉字转换为十位字母数字序列并在一定程度上保留汉字的读音和字形特征的汉字编码方法。
下图说明了音音码序列中各个bit的含义：
整个拼音码分为两部分。 第一部分为音码部分，主要涵盖韵母、声母、补语和声调的内容。
第一个是最终位置。 通过简单的替换规则，将汉字的最后部分映射到字符位置。 汉字的拼音共有24个韵母，为了以后的计算，将其中一些韵母替换为相同的字符。 以下是完整的匹配表：
您会发现我们对 an 和 ang 使用相同的转换。 目的是在后面计算相似度时削弱这种差异。 对于没有此需求的应用程序，您可以自行生成映射表。
第二位是声母位。 类似地，使用替换表将声母转换为字符：
正如您所看到的，z 和 zh 也使用相同的转换。
第三位是补码，通常在声母和尾声母之间有辅音时使用，使用与尾声母相同的替换规则。
第四个位置是声调位置，用1、2、3、4来代替汉字的四声。
第二部分是字形代码。
第一个位称为结构位。 根据汉字的结构不同，用一个字来表示汉字的结构。
接下来的四位数字仍然借用四角码来描述汉字的形状。 由于四角编码表太长，这里就不一一列举了。
最后一位数字是汉字的笔画数，从一到九，代表汉字从一到九的笔画，后面的A代表第10位数字，B代表第11位数字，以此类推。 Z 代表 35 位数字，超过 35 位数字则使用 z。
例如：汉字“郎”，其音形码为：
这样，首先将汉字转换成一系列的字符序列，这样我们就可以用一定的方法来计算它们的相似度。
单词相似度计算
对于单词相似度匹配，我们使用更复杂的计算公式，以获得更好的计算结果。
P表示语音编码的相似度，S表示图形编码的相似度。 两者占整个单词相似度的50%。
分别拆解音码相似度和形码相似度：
这里我重新定义了sum的含义以适应算法，用于表示字符比较操作。 意思是如果两个字符相同则返回1，不同则返回0。 表示如果两个字符相同，则返回1。 两个字符 如果不同，则返回-1。
结合两个公式，我们得到最终的单词相似度计算算法：
我们先看P部分。 声母部分占整个音码相似度的60%，补码占30%3D交通工具，声调部分占10%。 同时，最后的部分对最终的相似度起到了调节作用。
形状代码部分的算法非常相似。 四位四角码在形码部分算法中所占比例相同，而整个四角码占形码部分的70%，笔画数占30%。 最后字形结构部分与最终部分保持一致，起到调整作用。
我们以“狼”、“狼”、“妈妈”这三个词为例。
“郎”字的拼音代码是：F70211313B
“狼”字的声音模式代码为：F70214323A
“妈”字的拼音代码是：F74214343A
根据我们刚才描述的算法，可以得出“狼”和“狼”的相似度为88.75%。 “郎”与“娘”相似度83.75%
应用场景
单词相似度的计算并不是很有用。 毕竟，当两个非常大的字符串进行比较时，两个词的差异程度的微小差异并不会对整体的相似度结果产生很大的影响。
然而，在某些场景下，例如比较较短的字符串或纠正中文错误，单词相似度算法可以发挥非常重要的作用。
例如，用户通过搜索引擎搜索短语：“紫娘路”。 然而，在搜索引擎的词汇表中找不到匹配的字符串。 相应地，找到了两个相似的字符。 细绳：
《紫郎路》
《紫薇路》
此时，当前的搜索引擎系统无法区分这两个字符串中哪一个更接近用户输入，因此无法向用户做出更好的推荐。 相应地，使用本文描述的中文相似度算法，可以计算出“狼”和“狼”之间的相似度为88.75%（上面已经计算过）。 “娘”与“未”（音音码：8K0114424G）的相似度为14.3%。 可以得出“紫郎路”与输入数据比较接近。
另一个常见的应用场景是服务提供商拥有庞大的词汇库。 用户输入错误的数据后，如何尽快找到所有与其非常接近的单词。
在绝对匹配的情况下，通常的做法是为词汇表中的每个单词计算哈希值，然后将哈希字符串对插入哈希表。 当用户输入一个字符串时，会计算该字符串的哈希值，然后在表中进行匹配。
这种方法对于绝对匹配来说非常有效，但是对于模糊查询来说就没用了。 用户只能逐串执行相似度比较算法来选择最佳结果。 该算法的时间复杂度达到O(n)。
为了解决这个问题，我们可以设计一种哈希值计算方法，使得相似的字符串具有相同的哈希值。 这样，当用户输入一个字符串时，他们可以很容易地找到一组非常相似的字符串。 对此进行一一比较以最大限度地提高性能。 只要算法选择得当，性能甚至可以达到O(1)。
而这样的方法就隐藏在音音码的编码中。
对于任意字符串，取每个字符的拼音码的第一位（最后）和第五位（结构），拼成一个字符串，作为该字符串的哈希值。 这样，我们就可以对以下字符串进行转换：
《紫郎路》：41GE5E
《紫娘路》：41GE5E
《紫微路》：41815E
当用户输入“紫郎路”时，会转换为：41GE5E，与“紫郎路”和“紫娘路”的哈希值一致。 通过更详细的比较，可以得出“紫郎路”是最优结果。
当然，不同的应用程序可以选择不同位数的拼音码和图形码，以获得最适合应用程序的哈希值。 这可以完全根据要求定制。
字符串相似度计算
字符串相似度的计算可以通过直接将字符串中的每个汉字转换为音图码，然后将所有音图码组合起来与EditDistance算法进行比较来获得。
由于采用了中文大字符串比较算法，即使是EditDistance也能得到更好的结果。 这里不再详细描述。 有兴趣的读者可以自行研究。
跟进
整个算法源于我开发公司实体解析产品的经验。 当时因为遇到这样的问题，所以没有很好的解决办法。 后来在公司组织的黑客马拉松比赛中，我选择了这样的课题进行研究，并取得了很好的成绩。
这个算法仍然存在各种缺陷，例如音标和图形代码太长的问题，如何计算未对齐字符串的相似度等。但我认为我们不能总是等到所有问题解决后再做这项工作，但我们应该一步一步解决一个问题，不断前进。 因此，我希望借这篇文章给大家一个启发，为中文相似度算法做出自己的贡献，那么它的目的就达到了。
文章来源:https://blog.csdn.net/aizou2014/article/details/101886677
