使用 自动机 解决 拼音输入法 中的 多音字 组合爆炸
背景
为了保证输入效率,我们需要有一个从 词条拼音 到 词条汉字 的映射表,比如,拼音序列 ZiDongJi 对应的词条是 自动机 , 自冻鸡 ;从而,逻辑上讲,这是一个 map<string,list<string> >。
组合爆炸
假定我们有一个汉语词表,该词表的词条超过千万,每个词条可能是一句话(比如名言警句),并且,因为汉语中存在多音字,从而,包含多个多音字的词条都可能有很多种发音,这个数目在最坏情况下是指数级的,第一个字有 X1 个读音,第二个字有 X2 个读音,…,n 个字的词条就有 X1*X2*X3*…*Xn 种读音。另外,除了多音字,还有简拼,对于短词来说,简拼的重码率很高,不实用,但是对于长词/句,简拼的重码率就很低了。
如果我们用 HashMap/std::unordered_map 或 TreeMap/std::map 保存这个注音词典,对于普通无多音字的词条,无任何问题。一旦有多音字, X1*X2*X3*…*Xn 可能是一个非常大的数字,几十,几百,几千,几千万都有可能,这完全是不可接受的!一个折衷的办法就是仅选择概率最大的拼音,但很可惜,有些情况下这个拼音可能是错的!
使用自动机
我之前有一篇文章介绍 把自动机用作 Key-Value 存储 ,使用里面的方法,具体到该问题,就是:
用 string kv = X1*X2*X3*…*Xn + ‘\t’ + 汉字词条 来逐个插入,动态 MinADFA 算法可以保证内存用量不会组合爆炸,但是,除了内存,还有时间,如此逐个展开,时间复杂度也是指数的!
这个问题我想了很久,终于有一天,想出了一个完美的解决办法:
- 在 MinADFA 中加入一个功能:在线性时间内,给一个唯一的前缀,追加一个 ADFA后缀
- 该 ADFA后缀 可以包含 X1*X2*X3*…*Xn 个 word,并且结构还可以任意复杂(最近我的研究发现,该后缀甚至不必是 ADFA,可以包含环!)
- 这个算法是整个问题的关键,余下的,就只是简单的技巧而已
- 将 string kv = X1*X2*X3*…*Xn + ‘\t’ + 汉字词条 翻转
- rev(X1*X2*X3*…*Xn) 构成一个 ADFA
- rev(‘\t’+汉字词条) 是一个唯一前缀
- 将所有的词条做这样的处理,就构成一个 DFA({rev(拼音+’\t’+汉字)})
- 将该 DFA 翻转,得到 NFA(rev(DFA({rev(拼音+’\t’+汉字)})),再将该 NFA 转化成 DFA
- 查找时,使用 map2 的方法(DFA_Interface::match_key),因为组合爆炸,不能用 map1
这个方法非常完美!虽然 NFA 转化 DFA 最差情况下是 NSpace(比NP还难) 的,但是在这里,可以证明,这个转化是线性的:O(n)。
更有趣的问题:短语纠错
本网站首页 就是一个使用自动机进行短语纠错的示例。