多正则表达式匹配（MultipleRegularExpressionMatching）
⽬前 febird 中的⾃动机库已⽀持正则表达式，并且，⽀持的是多正则表达式匹配：
给定 M 个正则表达式，每个正则表达式有⼀个 [0, M) 的唯⼀ ID，该算法为这些正则表达式⽣成⼀个 DFA。
再给定⼀个输⼊⽂本 Text，长度为 T，假定只计最长匹配，该 Text 可以匹配 M 个正则表达式中的的 K 个。
在该DFA上运⾏我的匹配算法，可以在 O(T + K) 的时间复杂度内到那 K 个正则表达式，这个时间复杂度与 M 完全没有关系！从信息论的⾓度讲，该算法是最优的。
如果要获得在 Text 中的所有 N 个匹配点（N<=T），所要的时间是 O(T + K1 + ... Kn))，其中 Ki 表⽰第 i 个匹配点能匹配的正则表达式数⽬。
这也许是现存的最⾼效的解决该问题的算法，之前我⼀直认为该问题很难解决：，现在，它解决了，世界平静了！
当初我提出该问题的时候，如果我那个时候就开始尝试解决它，也许永远解决不了！
该问题的最终解决，却是源于另外⼏个问题的解决，当我完美⾼效地实现DAWG之后，我就在想⼀个问题：如何实现⼀个动态的基于DAWG 的 Map ？在中，我想象了⼀个解决⽅案（类似红⿊树索引号），但是后来经过仔细的思考，那个⽅案根本就⾏不通！
再后来，我⼜开始思考短语注⾳问题，短语注⾳问题的难点在于短语中的多⾳字，如果⼀个短语有多个多⾳字，这个短语所有可能的注⾳数量是指数的！如果我们只想从汉字短语得到它的所有可能注⾳，那这根本就不是问题！短语注⾳问题是：
给定⼀个汉字短语集合，以及每个汉字的所有发⾳（可能是多个，如果算上模糊⾳，就更多了）
要求：从该短语集合与汉字注⾳⽣成⼀个数据结构，该数据结构可以实现以下功能：
给定⼀串拼⾳，以最快的速度，到这串拼⾳对应的短语。
这个问题⼀开始遇到的时候，觉得很困难，也就⼀直没有太上⼼，因为这是个Map问题，那个时候在我的⼤脑中，只有 DAWG 能实现基于DFA 的 Map，⽽我知道 DAWG 根本⽆法解决这种指数问题。
再到后来，偶然⼀个机会，我也不记得具体的动机是什么，我为 DFA 增加了⼀个接⼝：
int match_key(char delim, string text, function<void(int keylen, string value)> on_match);
delim ⼀般是 \t ，创建⽤于该接⼝的 DFA 时，输⼊是⼀⾏⾏的 (key, value) ⽂本： key \t value
match_key 碰到 \t 时，将已匹配的字符串长度作为 keylen ， \t 后⾯的部分作为 value，通过 on_match 回调返回给调⽤
⽅，之所有⽤回调，是因为在 ADFA 中，同⼀个 key 对应多个 value 是⼀种很⾃然的事情，⽽这多个 value 可能⾮常多。总之，从⽤户来看，这是⼀个⾮常简单有效的接⼝。并且，⾃动机的创建是⼀个分离的通⽤的程序(adfa_build)。这就形成了⼀个最简单的⽣态：adfa_build 从⽂本⽂件⽣成 DFA ⼆进制⽂件，在线服务器程序加载 DFA ⼆进制⽂件并调⽤ match_key 。不需要为每⼀个不同的服务器程序专门写⼀个 addfa_build ！
然后，我很快就意识到，这可以解决注⾳问题，关键是⽣成那个 DFA！最简单的办法是从短语集合⽣成⼀个个 (pinyin, 汉字) 的 (key, value) pair，这⾥ key 是拼⾳，汉字是 value，如果⼀个短语有多⾳字，就⽣成多个 (key, value) pair，先不管对应同⼀个 value 的 key 数⽬可能因为多⾳字从⽽是指数个。只傻乎乎地将这些 (key, value) pair 输出给 adfa_build 程序，最终肯定能⽣成那个 DFA，⽽且是最⼩化的 DFA，因为该 DFA 创建过程是 Onfly Minimize 的，内存⽤量不会超爆。但是，但是——内存是不会爆，时间却仍然是指数级的！
这个问题曾经困扰了我很久，那段时间，我⽇思夜想，就是⽆法解决指数问题！后来终于有⼀天，洗澡的时候，我忽然意识到，⽤ NFA 作为媒介！因为我很早就实现了 Jan Daciuk 的 Onfly ADFA Minimization 算法，在 match_key 给我灵感之后，有⼀天突发奇想，结合match_key 的 delim，对 Daciuk 的算法做了⼀个理论上的泛化： add_adfa_tail，这个 adfa_tail 可以拥有任何复杂的 DAG 结构，如果把那多个可能的注⾳放到这个 adfa_tail 中，问题就解决了⼀半，剩下的⼀半，就是 DFA 的翻转，很简单的事情！
………………
…
………
……
再接下来，灵感继续光临，多正则表达式匹配，只需要在每个正则表达式之后，附加⼀个 delim+ID，⼀⼤半问题就解决了，剩下的⼀⼩半，就是纯粹的⼯程技术问题了
再后来，就是⼀些优化和泛化问题了，到⽬前为⽌，我的 DFA 多正则匹配算法还可以获取⼀类正则表达式的 submatch……
欲知更多请参考：正则匹配多个

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。