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

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