轉(zhuǎn)自淘菩，強(qiáng)烈建議大家看原文哲鸳，我最近在做數(shù)字編碼， 我發(fā)現(xiàn)相近的數(shù)據(jù)很難得到相近的編碼季春。

基于音形碼的中文字符串相似度算法

背景介紹

字符串相似度算法是指通過一定的方法，來計(jì)算兩個(gè)不同字符串之間的相似程度消返。通常會用一個(gè)百分比來衡量字符串之間的相似程度载弄。字符串相似度算法被應(yīng)用于許多計(jì)算場景，在諸如數(shù)據(jù)清洗撵颊，用戶輸入糾錯(cuò)宇攻，推薦系統(tǒng)， 剽竊檢測系統(tǒng)倡勇，自動(dòng)評分系統(tǒng)逞刷，以及網(wǎng)頁搜索和DNA序列匹配這些方向都有著十分廣泛的應(yīng)用。

常見的字符串相似度算法包括編輯距離算法（EditDistance）译隘，n-gram算法亲桥，JaroWinkler算法以及Soundex算法。本文接下來大略的介紹一下這幾種算法固耘，有興趣的讀者可以在互聯(lián)網(wǎng)找到一些更詳細(xì)的資料。

最常見的相似度算法為編輯距離算法（EditDistance）词身，該算法將兩個(gè)字符串的相似度問題厅目，歸結(jié)為將其中一個(gè)字符串轉(zhuǎn)化成另一個(gè)字符串所要付出的代價(jià)。轉(zhuǎn)化的代價(jià)越高法严，說明兩個(gè)字符串的相似度越低损敷。通常可以選擇的轉(zhuǎn)化方式包含插入深啤，替換以及刪除拗馒。

N-Gram算法則是基于這樣的一個(gè)假設(shè)： 即在字符串中第n個(gè)詞的出現(xiàn)只與前面n-1個(gè)詞相關(guān)，而與其他任何詞都不相關(guān)溯街，整個(gè)字符串出現(xiàn)的概率就是各個(gè)詞出現(xiàn)的概率的乘積诱桂。 N-gram本身也代表目標(biāo)字符串中長度為n的子串，舉例呈昔，“ARM”在“ARMY”中挥等，便是一個(gè)3-gram月劈。當(dāng)兩個(gè)字符串中橡卤，相同的n-gram越多時(shí)，兩個(gè)字串就會被認(rèn)為更加相似担敌。

Jaro Winkler則是將n-gram算法更進(jìn)了一步。將n-gram中的不匹配的部分同時(shí)進(jìn)行了換位的考慮辞槐，使得能獲得更準(zhǔn)確的相似程度掷漱。JaroWinkler在比較兩個(gè)較短字符串的情況下，能夠取得很好的結(jié)果榄檬。

Soundex算法與前面幾種都不太相同切威。該算法的特點(diǎn)是，它所關(guān)注的問題并非兩個(gè)字符串文本上的相似程度丙号，而是發(fā)音的近似先朦。首先，該算法會將兩個(gè)字符串分別通過一定的hash算法轉(zhuǎn)換成一個(gè)hash值犬缨，該值由四個(gè)字符構(gòu)成喳魏，第一個(gè)字符為英文字母，后面三個(gè)為數(shù)字怀薛。進(jìn)行轉(zhuǎn)化的hash算法并非隨機(jī)選取刺彩，而是利用了該拉丁文字符串的讀音近似值。

當(dāng)獲得了兩個(gè)字符串的讀音上的hash值之后枝恋，該算法再對兩個(gè)hash的相似度進(jìn)行計(jì)算创倔，便可以得出輸入字符串的讀音相似度。

Soundex算法的另一個(gè)應(yīng)用場景在于焚碌，用戶進(jìn)行模糊查詢時(shí)畦攘，可以通過Soundex值進(jìn)行過濾，以提高查詢性能十电。

問題描述

這些常見的字符串相似度算法在處理拉丁文字的文本匹配時(shí)知押，都能起到非常好的效果。它們本身最初的發(fā)明者也是為了解決拉丁文字中遇到的問題鹃骂。然而台盯，對于象形文字相似度計(jì)算，比如說中文畏线，這些算法就顯得捉襟見肘了静盅。

舉例來說明：

南通市 – 難通市 – 北通市

對于編輯距離算法而言，南通市和難通市之間的相似度寝殴，與南通市和北通市的相似度蒿叠，是一模一樣的，因?yàn)閮烧叨夹枰冻鱿嗤拇鷥r(jià)來轉(zhuǎn)換成另一個(gè)杯矩。 使用N-Gram算法栈虚，得出的也是相同的結(jié)果。然而史隆，對于熟悉漢字的人來講魂务，南通市和難通市理應(yīng)有著更加接近的相似度。因?yàn)閮烧叩陌l(fā)音完全相同。

既然是發(fā)音的問題粘姜，那么有沒有可能利用Soundex算法來解決呢鬓照？ 目前看來，還是無法做到孤紧，因?yàn)镾oundex算法更多的是針對拉丁文字的發(fā)音豺裆，對于中文而言，Soundex算法無能為力号显。

如果說這個(gè)例子僅僅說明是發(fā)音上的相同臭猜，拉丁文字也有相似的問題，那么下面這個(gè)例子則描述了只存在于象形文字中的相似度問題：

彬彬有禮 – 杉杉有禮

如果站在解決拉丁文字的相似度的角度來看押蚤，那么這兩個(gè)字符串大約只有50%的相似度蔑歌，因?yàn)樵谒膫€(gè)字符中，就有兩個(gè)字符是完全不同的揽碘。這兩個(gè)字符不僅外形不同次屠，即使是發(fā)音，也是完全不同雳刺。

然而對于熟悉漢字的人來說劫灶，這兩個(gè)輸入應(yīng)該有著相當(dāng)高的相似度。因?yàn)榈谝粋€(gè)和第二個(gè)字符掖桦，雖然不同本昏，卻有著十分接近的字形。

這樣的案例常常出現(xiàn)在錄入手寫輸入時(shí)滞详，舉例來說凛俱，某個(gè)顧客填寫了一張快遞單：

江蘇省 南通市 紫瑯路 100號

當(dāng)快遞員簽收快遞時(shí)，可能需要在系統(tǒng)中錄入該地址料饥，又或者，這家快遞公司采用的是先進(jìn)的掃描儀器朱监，可以將地址通過掃描儀掃入岸啡。假設(shè)顧客的字寫的十分潦草，那么快遞員粗心大意或者不夠智能的掃描儀赫编，都有可能導(dǎo)致下面的文字被錯(cuò)誤的錄入：

江蘇省 南通市 紫娘路 100號

如何識別這樣的相似中文詞組巡蘸，在現(xiàn)有的算法中，很難解決該問題擂送。

中文的字符串相似度有著其獨(dú)特的特征悦荒，不同于其他任何語言，而在現(xiàn)實(shí)世界中嘹吨，我們又卻是時(shí)常面臨這樣的問題搬味，正如我們剛才看到的例子，其中最常見的場景便是中文糾錯(cuò)。

我們急需要需找一種新型的算法來解決該問題碰纬。

問題分析

想要解決中文字符串的相似度匹配問題萍聊，并且量化中文相似度的結(jié)果，必須首先對單個(gè)漢字的特性有一定的了解悦析∈俳埃“瑯“和“狼”的相似度，跟“瑯”和“娘”之間的相似度比較强戴，究竟哪個(gè)更高一些亭螟，量化的依據(jù)是什么？“籃”和“南”呢骑歹？他們之間有相似之處么预烙？只有把這些問題都搞清楚了，我們才能設(shè)計(jì)出優(yōu)秀的算法陵刹，來計(jì)算中文字符串之間的相似度默伍。

經(jīng)過長時(shí)間的調(diào)研和準(zhǔn)備，在工作中不斷的思考總結(jié)遇到的中文相似度的問題衰琐，我們做出如下的總結(jié)也糊，中文的相似度問題，主要?dú)w結(jié)在三個(gè)方面羡宙。

同音字

漢字中的同音字可謂是外國人學(xué)習(xí)中文的一大難題狸剃，兩個(gè)截然不同的漢字，可能有著相同的發(fā)音狗热。

當(dāng)我們對兩個(gè)漢字進(jìn)行相似度匹配時(shí)钞馁，發(fā)音的相同或是相近，應(yīng)當(dāng)在考慮之列匿刮。

對于同音字僧凰，如果僅僅考慮其發(fā)音的相似程度，那么提供這樣的一個(gè)相似度算法還是十分容易的熟丸，只需要現(xiàn)將漢字轉(zhuǎn)化成其對應(yīng)的拼音训措，再進(jìn)行傳統(tǒng)的相似度匹配算法，譬如編輯距離算法光羞，即可達(dá)到很好的效果绩鸣。

方言易混淆發(fā)音字

在中國的各個(gè)省市中，不同地區(qū)有著各自截然不同的方言纱兑。這也導(dǎo)致了一些口音很重的地區(qū)無法識別一些拼音之間的區(qū)別呀闻。

最常見的例子便是，許多南方人很難分別“L”和“N”潜慎，他們常常會將這兩個(gè)音弄混捡多，將“籃球”讀作“南球”蓖康，而“劉德華”就變成了“牛德華”。

解決方言易混淆發(fā)音字的辦法和同音字的方法很相似局服，只需要在將漢字轉(zhuǎn)化成拼音之后钓瞭，再對一些易混淆的音標(biāo)再進(jìn)行一次轉(zhuǎn)化，然后再去識別他們的相似度即可淫奔。

當(dāng)然山涡，也可以在計(jì)算近似度的時(shí)候，給易混淆音標(biāo)設(shè)置一個(gè)相對較高的比值唆迁，也可以解決該問題鸭丛。

還有些常見的易混淆音標(biāo)包括：

“AN” – “ANG”

“Z” – “ZH”

“C” – “CH”

“EN” – “ENG”

字形相似

最后一種相似度問題，同時(shí)也是最難解決的問題唐责，便是漢字字形上的相似鳞溉。

漢字，作為世界上僅存的幾種象形文字之一鼠哥，有著和世界主流使用的拉丁語系截然不同的表現(xiàn)形式熟菲。拉丁文字作為一種拼音文字，在于表音朴恳，即文字形態(tài)表示了它的發(fā)音抄罕。而象形文字，則是表意文字于颖，一個(gè)漢字本身呆贿，便表達(dá)了它所隱含的意思。

在文章開篇中森渐，我們所提到的所有相似度匹配算法做入，都無法恰當(dāng)?shù)膮^(qū)分兩個(gè)不同漢字之間字形上的異同，更罔論計(jì)算他們的相似度了同衣。

對于這個(gè)問題竟块，一種樸素的思想，便是首先將漢字轉(zhuǎn)化成一組的字母數(shù)字的序列耐齐，而這個(gè)轉(zhuǎn)化所用到的hash算法必須能夠?qū)⒃摑h字的字形特征保留下來彩郊。利用這樣的轉(zhuǎn)化，我們便將漢字字形的相似度問題蚪缀，變成了兩組字母數(shù)字序列的相似度問題。而這正是傳統(tǒng)相似度匹配算法的強(qiáng)項(xiàng)恕出。

這種解決方案的核心询枚，就在于找到一個(gè)恰當(dāng)?shù)膆ash算法，能夠?qū)h字進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化浙巫，并在轉(zhuǎn)化結(jié)果中金蜀，保留住漢字的字形特征刷后。

在另一篇論文中，作者提到了使用一種名為四角編碼的漢字檢字法來實(shí)現(xiàn)這樣的算法渊抄。四角算法是由王云五于1925年發(fā)明尝胆，這種編碼方式根據(jù)漢字所含的單筆或復(fù)筆對漢字進(jìn)行編號，取漢字的左上角护桦，右上角含衔，左下角以及右下角四個(gè)角的筆形，將漢字轉(zhuǎn)化成最多五位的阿拉伯?dāng)?shù)字二庵。 通過將漢字轉(zhuǎn)化成四角編碼贪染，再對四角編碼的相似度進(jìn)行計(jì)算，便可以得出兩個(gè)漢字在字形上的相似程度催享。

關(guān)于四角號碼的編碼方式杭隙，并非本文的重點(diǎn)，感興趣的讀者因妙，可以訪問站點(diǎn)：http://baike.baidu.com/view/67253.htm?fr=aladdin以了解更多信息痰憎。

利用四角編碼計(jì)算漢字相似度，可以在一定程度上解決形近字的問題攀涵。

然而四角編碼也有其自身的問題铣耘，由于只取漢字的四角筆形，有些外形截然不同的漢字汁果，因?yàn)樗慕墙Y(jié)構(gòu)相同涡拘，也擁有同樣的四角編碼。

舉例說明：

量 -? 6010

日 -? 6010

即使是從未學(xué)過中文的人据德，也能一眼看出這兩個(gè)字形上的差異鳄乏，如果我們僅僅使用四角編碼，則會得出這兩個(gè)漢字相似度為100%的可笑結(jié)論棘利。

綜合以上關(guān)于漢字相似度的三種問題橱野，我們發(fā)現(xiàn)，每種解決方案都旨在解決整個(gè)問題集的的一個(gè)子集善玫。這種分不同場景的做法水援，常常會造成使用者的困擾，因此茅郎，我們在想蜗元，是否存在一種方法，能夠?qū)⑦@三種解決方案合而為一系冗，取其優(yōu)點(diǎn)而去其缺點(diǎn)奕扣，一次性徹底解決中文的相似度問題？

這個(gè)問題引發(fā)了我的思考掌敬。

音形碼（SoundShape Code惯豆，SSC）

為了解決文章上面描述的問題池磁，我在工作中積累相關(guān)經(jīng)驗(yàn)，并開發(fā)出了音形碼這一漢字編碼方式楷兽，來解決中文的相似度算法問題地熄。

首先，什么是音形碼芯杀？音形碼是一種漢字的編碼方式端考，該編碼將一個(gè)漢字轉(zhuǎn)化成一個(gè)十位字母數(shù)字序列，并在一定程度上保留了該漢字的發(fā)音及字形的特征瘪匿。

下圖闡述了音形碼的序列中每一位的含義：

整個(gè)音形碼共分兩部分跛梗，第一部分是音碼部分，主要覆蓋了韻母棋弥，聲母核偿，補(bǔ)碼以及聲調(diào)的內(nèi)容。

整個(gè)音形碼共分兩部分顽染，第一部分是音碼部分漾岳，主要覆蓋了韻母，聲母粉寞，補(bǔ)碼以及聲調(diào)的內(nèi)容尼荆。

第一位，是韻母位唧垦，通過簡單的替代規(guī)則捅儒，將漢字的韻母部分映射到一個(gè)字符位。漢字的拼音中一共有24種韻母振亮，其中部分為了后期計(jì)算目的巧还，采用相同的字符來替代，以下是一張完整的匹配表：

你會發(fā)現(xiàn)我們對于an和ang坊秸，所使用的是同一種轉(zhuǎn)化麸祷，目的便是為了再后期計(jì)算相似度的時(shí)候，將這種差異弱化褒搔。對于沒有這種需求的應(yīng)用來說阶牍，完全可以自行生成映射表。

第二位是聲母位星瘾，同樣的走孽，也是利用一張?zhí)鎿Q表來將聲母轉(zhuǎn)換成字符：

可以看到，z和zh用的也是相同的轉(zhuǎn)化琳状。

第三位則是補(bǔ)碼融求，通常用于當(dāng)聲母和韻母之間還有一個(gè)輔音的時(shí)候，采用的是韻母表相同的替代規(guī)則算撮。

第四位是聲調(diào)位生宛，分別用1，2肮柜，3陷舅，4來替代漢字中的四聲。

第二部分是字形碼审洞。

第一位被稱為結(jié)構(gòu)位莱睁，根據(jù)漢字的不同結(jié)構(gòu)，用一個(gè)字符來表示該漢字的結(jié)構(gòu)芒澜。

接下來的四位仰剿，則依然是借用了四角編碼，來描述該漢字的形態(tài)痴晦。由于四角編碼表過長南吮，在這里就不一一列舉了。

最后一位誊酌，是漢字的筆畫數(shù)位部凑， 從一到九，分別代表該漢字的筆畫為一到九碧浊，接下來是A代表10位涂邀，B代表11位，并依次類推箱锐。 Z代表35位比勉，以及任何超過35位的都用z。

舉例說明：漢字 “瑯”驹止，它的音形碼編碼是：

通過這樣的方式浩聋，將漢字首先轉(zhuǎn)換成了一系列的字符序列，這樣我們就可以采用一定的辦法幢哨，來計(jì)算他們的相似度赡勘。

單字相似度計(jì)算

對于單字的相似度匹配，我們采用了比較復(fù)雜的計(jì)算公式捞镰，以期獲得一個(gè)比較好的計(jì)算結(jié)果闸与。

P代表音碼的相似度，S代表形碼的相似度岸售，兩者各占整個(gè)單字相似度的50%践樱。

單獨(dú)拆解音碼相似度和形碼相似度：

這里我重新定義了 和 的含義已適應(yīng)該算法，用于代表字符比較操作凸丸， 表示拷邢，若兩字符相同，則返回1屎慢，不同瞭稼，則返回0. 表示忽洛，若倆字符相同，則返回1环肘， 兩字符不同欲虚，則返回-1.

將兩個(gè)公式進(jìn)行合并，便得到最終的計(jì)算單字相似度的算法：

先看P部分悔雹，聲母部分占據(jù)了整個(gè)音碼相似度的60%复哆，補(bǔ)碼為30%， 而聲調(diào)部分為10%腌零。于此同時(shí)梯找，韻母部分對最終的相似度起到 的調(diào)整作用。

形碼部分的算法很類似益涧，四位四角編碼在形碼部分算法中占據(jù)相同的比重锈锤，而整個(gè)四角編碼在形碼部分中則占據(jù)70%的比重，而筆畫數(shù)則占據(jù)了30%的比重饰躲。最終牙咏，字形結(jié)構(gòu)部分與韻母部分一致，起到了 的調(diào)整作用嘹裂。

我們以“瑯”妄壶，“狼”和“娘”三字舉例。

“瑯”字的音形碼為：F70211313B

“狼”字的音型碼為：F70214323A

“娘”字的音型碼為：F74214343A

根據(jù)我們剛才所描述的算法寄狼，可以得出丁寄，“瑯”和“狼”的相似度為88.75%。 而“瑯”和“娘”的相似度為83.75%

應(yīng)用場景

單字相似度的計(jì)算并非十分有用泊愧，畢竟當(dāng)兩個(gè)非常大的字符串進(jìn)行比較時(shí)伊磺，兩個(gè)字之間差異程度的細(xì)微差別，整體的相似度結(jié)果影響不是很大删咱。

然而在某些場景下屑埋，諸如較短字符串的比較，或者是中文糾錯(cuò)的時(shí)候痰滋，單字相似度的算法則可以起到非常大的作用摘能。

舉例來說，用戶通過搜索引擎來檢索一個(gè)短語：“紫娘路”敲街， 而在搜索引擎的詞庫中团搞，并沒有能夠發(fā)現(xiàn)任何匹配的字符串，相應(yīng)的多艇，找出了兩個(gè)與其類似的字符串：

“紫瑯路”

“紫薇路”

此時(shí)逻恐，目前的搜索引擎系統(tǒng)無法區(qū)別出這兩個(gè)字符串與用戶輸入哪個(gè)更加接近，因而無法向用戶做出更好的推薦。 相應(yīng)的复隆，使用本文描述的中文相似度算法拨匆，便可以算出，“瑯”和“狼”的相似度為88.75%（前文已得出）昏名。 “娘”和“薇”（音形碼： 8K0114424G）的相似度為14.3%涮雷。由此可以得出，“紫瑯路”與輸入數(shù)據(jù)較為接近轻局。

另一種常見應(yīng)用場景為，服務(wù)提供者擁有巨大的詞庫样刷，用戶輸入一個(gè)錯(cuò)誤數(shù)據(jù)之后仑扑，如何盡快的找出所有與其十分接近的詞。

在絕對匹配的情況下置鼻，做法通常為镇饮，為詞庫中的每一個(gè)詞，計(jì)算出一個(gè)hash值箕母，再將hash-字串對插入到一張hash表中储藐。當(dāng)用戶輸入一個(gè)字串時(shí)，現(xiàn)將該字串的hash值計(jì)算出嘶是，再去表中進(jìn)行匹配钙勃。

這種做法對于絕對匹配而言，效率很高聂喇，然而對于模糊查詢來說辖源，則毫無用武之地。用戶只能一個(gè)字符串一個(gè)字符串的做相似度比較算法希太，來選出最佳的結(jié)果克饶。該算法的時(shí)間復(fù)雜度則達(dá)到了O(n)。

為了解決這個(gè)問題誊辉，我們可以設(shè)計(jì)一種hash值的計(jì)算方法矾湃，使得相似的字符串擁有相同的hash值，這樣當(dāng)用戶的字符串輸入時(shí)堕澄，就可以輕易的找到一群與之十分相似的字符串邀跃，再對此進(jìn)行一一比較，可以將性能提升到最大奈偏。只要算法選取合適坞嘀，性能甚至可以達(dá)到O(1)。

而這樣的方法就隱藏在音形碼的編碼當(dāng)中惊来。

對任意字符串丽涩，取每一位字符的音形碼的第一位（韻母）和第五位（結(jié)構(gòu)），拼成一個(gè)字符串，作為該字符串的hash值矢渊，通過這樣的方式继准，我們可以以下字符串進(jìn)行轉(zhuǎn)化：

“紫瑯路”： 41GE5E

“紫娘路”： 41GE5E

“紫薇路”： 41815E

當(dāng)用戶輸入“紫狼路”時(shí)，將會被轉(zhuǎn)化成：41GE5E矮男，從而與“紫瑯路”以及“紫娘路”的hash值一致移必。再通過更細(xì)節(jié)的比較，可以得出“紫瑯路”為最優(yōu)結(jié)果毡鉴。

當(dāng)然崔泵，不同的應(yīng)用可以選取不同的音形碼的位數(shù)，來得到對應(yīng)用最合適的hash值猪瞬。這完全可以根據(jù)需求來定制化憎瘸。

字符串相似度計(jì)算

字串相似度的計(jì)算可以通過直接將字符串中的每個(gè)漢字轉(zhuǎn)化為音形碼，再將所有音形碼合并起來進(jìn)行EditDistance算法比較陈瘦，即可獲得幌甘。

因?yàn)橹形牡拇笞址谋容^算法，即使是EditDistance也可以得到較好的結(jié)果痊项，在這里就不詳細(xì)描述了锅风，有興趣的讀者可以自行研究。

后續(xù)

整個(gè)算法源于我在開發(fā)公司的某個(gè)實(shí)體解析的產(chǎn)品中總結(jié)的經(jīng)驗(yàn)鞍泉，當(dāng)時(shí)因?yàn)橛龅竭@樣的問題皱埠，卻沒有很好的解決辦法。后來塞弊，在公司組織的編程馬拉松競賽中漱逸，我便選擇了這樣的課題來研究，并獲得了很好的結(jié)果游沿。

該算法還有著這樣那樣的缺陷饰抒，比如音形碼過長問題，字串錯(cuò)位如何計(jì)算相似度等诀黍。但是我想袋坑，不能總等一切問題都解決再來做這些工作，而是一步解決一個(gè)問題的來不斷前進(jìn)眯勾。因此也希望借用這篇文章枣宫，給大家一個(gè)啟發(fā)，為中文的相似度算法做出自己的貢獻(xiàn)吃环，那它的目的也就達(dá)到了也颤。

---------------------

作者：數(shù)據(jù)中國

來源：CSDN

原文：https://blog.csdn.net/chndata/article/details/41114771

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接郁轻！

---------------------

作者：數(shù)據(jù)中國

來源：CSDN

原文：https://blog.csdn.net/chndata/article/details/41114771

版權(quán)聲明：本文為博主原創(chuàng)文章翅娶，轉(zhuǎn)載請附上博文鏈接文留！

---------------------

作者：數(shù)據(jù)中國

來源：CSDN

原文：https://blog.csdn.net/chndata/article/details/41114771

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接竭沫！

---------------------

作者：數(shù)據(jù)中國

來源：CSDN

原文：https://blog.csdn.net/chndata/article/details/41114771

版權(quán)聲明：本文為博主原創(chuàng)文章燥翅，轉(zhuǎn)載請附上博文鏈接！