问题
文本中匹配关键字，正则表达式决定是首选，可是如果是下面的情况呢？
- 需要同时匹配的关键字，数量有成千上万个
- 文本超大，需要将每个位置的关键字都标记出来
然后你就会看到很多OOM......
有向无环图
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。
有向无环图.png
将所有需要匹配的关键字按照如上结构加入图中
步骤
- 初始化图指针指向图的第一列位置
- 开始遍历文本字节序
- 发现当前字节匹配图指向列中的任意字符时，缓存子图搜索路径（当前文本位置，当前图指针的下一列位置）
- 遍历所有子图搜索路径，匹配当前字符，如果发现字符与当前路径不匹配，则删除路径。否则更新当前子图搜索路径（图指针的下一列位置）
- 如果发现路径已经到达结尾处，则将文本开始位置到当前位置的关键字提取出来
- 循环2-5
- 得到的关键字可能内嵌、交叉、相邻，需要考虑贪婪匹配
性能
上万关键字大文本提取百万qps
网友评论