基于内容过滤的模式匹配算法比较.pdf

文档介绍：第 期 总 期 情 报 探索 年 月
基转 换 的处理 过 程 ，由“�����”状 态 开始 。� 选 择 关 键 词 集 合 中的 一个 子 集 与 当前 文 本 进 行 匹�
在搜 索 查找 阶段 ．通过这 三个 函数 的交 叉使 用扫描� 配 ，减 少无 谓 的匹配运 算 。��— ������算 法还构 造 了�
文 本 ．定 位 出关键 字在 文本 中的所有 出现 位置 。有 限� 一 个 不 良字 符移 动 距 离 表 ������¨ �，利 用 当前 块 字�
自动机 的构 造使 每个 状态 仅 仅 是 一个 前 缀 的代 表 。� 符 � 查 �������表 ，向后移 动 ��������个 字 符 寻找 下�
当文本 的下个 字 符不是 想要 的字 符时 ，转 到一个 模� 一 个 匹配 入 口点 ；如果 ��������等于 �．表示 � 是一�
式 的最 长前 缀所代 表 的那 个状 态 。这个 状态 也就 是� 个 可能 的 匹配入 口。使 用 ��������表可 以跳 过那 些不�
当前状 态 的合适 的后缀 。应 用有 限 自动机算 法对 一� 可 能成 功 的匹配人 口，提高 匹配 的速 度 。��— �������
个 长度 为 �个 字节 的文 本 �进行 扫 描 ，由于 �中的� 算 法 的 时 间复 杂 度在 最 好 的情 况 能达 到 �����／���
每个字 符仅 有一个 状态 转换 函数 ，因此在 扫描 阶段� ��是块 字符 的长 度 ，是 算法 在每 一个 入 ��点计 算块�
所 需 的时 间复杂 度在 ����，并 且 与具 体模 式 的 长度� 字 符 的时 间 ，�为模 式集 ���的尺寸 ，� 是最 小模 式 的�
和模式 集 的大小无关 。� 长度 �。�
�．�� 快速 多模式 匹配 ������ �算 法� ��— ������算法思路 ：�