JAVA 自动识别人名拼音与外国人姓名

SilenceSea 2017-08-01 阅读


我们都知道对于老外的姓名,其实常规来说我们按照空格就可以实现识别拆分,但对于汉语的拼音,如shanhanyu、hanyushan等描述性不是很强或者说不规则的汉语拼音如何进行识别拆分呢?公司技术总监周老师分享了一个算法,个人膜拜中。
英文格式的姓名,其中有些是中文姓名的拼音,有些是存外国人名称。

   CaiBiaohua 
   FangChao
   Yu Jian
   Shi Zhaocun
   J.K. Caldron

这些没有分隔的如何识别姓与名? 有分隔的那个是姓?

预备知识

trie 树

要解决我们的问题,以及其它类似问题,需要一个高效的词典查询算法。
trie树就是其中一种,解决的问题大致如下:
有一个大规模的词典, 有一大段文本, 通过最少次扫描得出这段文本在词典中的所有词。
衍生的问题是:有一段文本, 有一个词典, 从文本开头算起,在词典中最长的词是什么?
trie树算法解决了这个问题。 一般的trie树,虽然效率很高,但是构造字典需要的内存太大,所以常用的是 DoubleArrayTrie。 我们的算法用的就是这个。

最长匹配算法

在分词领域,基本问题是给一段文本,如何切分成单词的序列,这个序列与人的理解大致相同?
英文问题不大,有明显的分隔符。但是中文或者中文的拼音就不灵了。
最长匹配算法是其中一种。就是用一个字典(通常前面说的trie树字典),开头切分出最长的词,然后拿掉他,在剩下的继续最长切分。
万一某位置没有词,就算一个单字词,拿掉这个单字词继续切分。
最长匹配算法的优点是快,几乎没有更快的方案了。
缺点是不能解决很多歧义问题,此外,没有词就切出一个单字词也不是很好。

反向最长匹配算法

与最长匹配类似,只不过算法从文本的尾部开始往前匹配。虽然没有理论依据,实践表明效果略好于最长匹配。

最短路径匹配算法

切分出每一种结果,选取词数目最少的一种。如果有两条以上路径词数最少,没有说明选哪个。

HHM算法

统计每一个词与相邻词共同出现的词频,依此做一个概率模型。然后每一个组合都依据概率设置一个权值,最后挑选权值最大的结果。
由于只考虑每一个词的相邻词,有一个著名的算法 Viterbi 可以优化评估分支,避免每一个分支路径都计算一下。
总的来说,被称为 HHM 算法。这个效果好于前面的算法。问题是需要语料统计词频。

我们的方案

基本思路

我们将拼音视为分词问题,准备一份拼音字典,将一串拼音切分出一个最有可能的序列,就是结果。
如果我们的字典很充分,那么无法得到一个切分结果的(就是中间有字母造成断层),就认为不是拼音。

拼音字典

来自 pinyin4j 项目,字典格式未改,我们把字典文件名改了一下。由于我们只处理拼音,不需要字典中的汉字。

算法实现

词典就是拼音词典。算法类似于HHM,但是权值计算简化为从从尾部往前看最长的组合权最大。
需要的数据结构:

     DoubleArrayTrie:高效的trie实现
     LinkedNode:      为切分实现的链表

LinkedNode 的每一个节点保留到达该节点之前的最优路径,以及本位置开始的各种拼音词(按长度排序)
LinkedNode 的开头添加一个虚拟的假节点表示开始
LinkedNode 的尾部添加一个虚拟的假节点表示结束。

算法从头扫描一遍输入文本(就是拼音文本),建立上述链表。
结束时从尾部开始遍历一遍链表即可。
如果输入不是拼音,必然无法到达尾部。因此从尾部遍历必然得到空结果,这就表明输入不是拼音了。
不是拼音的结果,我们简单地视为外国人名,按空格切分了。


声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。