背景

为了保证输入效率，我们需要有一个从 词条拼音 到 词条汉字 的映射表，比如，拼音序列 ZiDongJi 对应的词条是 自动机 ， 自冻鸡 ；从而，逻辑上讲，这是一个 map<string,list<string> >。

组合爆炸

假定我们有一个汉语词表，该词表的词条超过千万，每个词条可能是一句话（比如名言警句），并且，因为汉语中存在多音字，从而，包含多个多音字的词条都可能有很多种发音，这个数目在最坏情况下是指数级的，第一个字有 X₁ 个读音，第二个字有 X₂ 个读音，…，n 个字的词条就有 X₁*X₂*X₃*…*X_n 种读音。另外，除了多音字，还有简拼，对于短词来说，简拼的重码率很高，不实用，但是对于长词/句，简拼的重码率就很低了。

如果我们用 HashMap/std::unordered_map 或 TreeMap/std::map 保存这个注音词典，对于普通无多音字的词条，无任何问题。一旦有多音字， X₁*X₂*X₃*…*X_n 可能是一个非常大的数字，几十，几百，几千，几千万都有可能，这完全是不可接受的！一个折衷的办法就是仅选择概率最大的拼音，但很可惜，有些情况下这个拼音可能是错的！

使用自动机

我之前有一篇文章介绍 把自动机用作 Key-Value 存储 ，使用里面的方法，具体到该问题，就是：
用 string kv = X₁*X₂*X₃*…*X_n + ‘\t’ + 汉字词条 来逐个插入，动态 MinADFA 算法可以保证内存用量不会组合爆炸，但是，除了内存，还有时间，如此逐个展开，时间复杂度也是指数的！

这个问题我想了很久，终于有一天，想出了一个完美的解决办法：

1. 在 MinADFA 中加入一个功能：在线性时间内，给一个唯一的前缀，追加一个 ADFA后缀
   • 该 ADFA后缀 可以包含 X₁*X₂*X₃*…*X_n 个 word，并且结构还可以任意复杂（最近我的研究发现，该后缀甚至不必是 ADFA，可以包含环！）
   • 这个算法是整个问题的关键，余下的，就只是简单的技巧而已
2. 将 string kv = X₁*X₂*X₃*…*X_n + ‘\t’ + 汉字词条 翻转
   • rev(X₁*X₂*X₃*…*X_n) 构成一个 ADFA
   • rev(‘\t’+汉字词条) 是一个唯一前缀
3. 将所有的词条做这样的处理，就构成一个 DFA({rev(拼音+’\t’+汉字)})
4. 将该 DFA 翻转，得到 NFA(rev(DFA({rev(拼音+’\t’+汉字)}))，再将该 NFA 转化成 DFA
5. 查找时，使用 map2 的方法（DFA_Interface::match_key），因为组合爆炸，不能用 map1

这个方法非常完美！虽然 NFA 转化 DFA 最差情况下是 NSpace(比NP还难) 的，但是在这里，可以证明，这个转化是线性的：O(n)。

更有趣的问题：短语纠错

本网站首页 就是一个使用自动机进行短语纠错的示例。