有向无环图在大文本匹配N多关键字中的应用

问题

文本中匹配关键字，正则表达式决定是首选，可是如果是下面的情况呢？

• 需要同时匹配的关键字，数量有成千上万个
• 文本超大，需要将每个位置的关键字都标记出来
  然后你就会看到很多OOM......

有向无环图

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

有向无环图.png

将所有需要匹配的关键字按照如上结构加入图中

步骤

1. 初始化图指针指向图的第一列位置
2. 开始遍历文本字节序
3. 发现当前字节匹配图指向列中的任意字符时，缓存子图搜索路径（当前文本位置，当前图指针的下一列位置）
4. 遍历所有子图搜索路径，匹配当前字符，如果发现字符与当前路径不匹配，则删除路径。否则更新当前子图搜索路径（图指针的下一列位置）
5. 如果发现路径已经到达结尾处，则将文本开始位置到当前位置的关键字提取出来
6. 循环2-5
7. 得到的关键字可能内嵌、交叉、相邻，需要考虑贪婪匹配

性能

上万关键字大文本提取百万qps

代码

https://github.com/sunpeak/DAG_text