一种高效的多模式字符串匹配算法

1、 I 3 2 0 计 获 得 更 多 的 跳转 。 算 机 工 程 算法和 ， 年 月 日 相 同 的 代价 下 ， 。 总之 ， ， 本文 算 法 使 代 价 与 算法相 比 ， 箅 法在 模 式 串 较 长 当 模式 串 长 度 在 函 数 的 分子 减 小 分 母 增 大 平 均 情 况 下 本 文算 法 较 。 和 模 式 数 较少 时 性 能 改进 更 多 ， 。 之 箅法的 箅法 、 算 法和 算法的 时 间 复杂 度更 优 间且模式较少 时 算法查找时间仅为 算法的 。 允 聆斗 坧 为 测试本文 左右 ， 算 法的 左右 ， 算 法的 当模 式 串长 度大于 时 箅 算法 的性

2、 能 ， 并与 ， 算法 、 法对 性 能 的 改 进 更 大 个 比较 。 算法 、 箅 法和 ： 算 法 进行 横 向 对 比 （ 选取 以 下 在实 际 应 用 中 一 ， 大 部 分模 式 串 的 长 度 都 在 ， 以上 】 。 为 评 价 栴 标进 行 考察 查找 时间 。 （ 文 中 单个字 符平均比 。 般 情况 下 算 法 的平 均性 能 。 随 机 选取 长 度 在 以上 较 次数 ， 即 箅法 执行字 符 比 较操作 总 数除 以 文 本 长度 ， 模 式 串 进 行 实 验测 忒 。 跳 转 闲 数 调 用 次数 即 分 别 调 用 函 数 出 跳 转 函 数跳 跃 距

3、 离 即 分 别 调 用 函 数 ： 和 吻 的次数 图 屮 数 据 显示 ， ， 随 着模 式串 数 目 増加 ， 箅法的 査 ， 办 和 从扣 跳 过 的 找 时 间 基 本 稳定 其 余 算法 的 査 找 时 间 和 平 均 比 较 操 作 数 且 增 长 速 率逐 渐 放 级 。 总字符 数 之和 距 离之 和 。 （ 平均 收益 ， ， 即跳 跃 距离 之 和除 以 比 较操作数 均 呈亚 线 性 增 长 度 算 法的 ， 其中 ， 榄 式串 长 平均代价 。 即 发现 失 配 所 花 的 代 价 之 和 除 以 跳 跃 箅 法 的查 找 时 间 是 算法 的 ； 箅法的 左右 箅法

4、 的 丨 ， 箅 实 验环境 如 内存 ； 操 作系 统 ， 法的 左右 箅 法的 平均比 较操作 数是 算法 的 算法和 ， 算 法均选用 开源软件 算 法和 本文算法均采 左右 ， 箅 屮 的实 现 版 本 算法 、 法的 左右 。 用 语言 实 现 。 待 闪 配 文 本 由 路透社 的 新 闻 文 本 数 据集 ， 一 组成 ， 共约 。 待匹配模 式串集 合 。 从 站提 供 的 岛 频 词 汇 表 中 随 机 选 取 为 考 察模 式 串 长 度 和 数 丨 对 箅 法 性 能 的 影响 目 ， 模 式 串 按长 度 分 为 个 部分 目从 丨 ， 各 以 邢 分 冉按照串 数 为

5、 单位 递 增 。 分为 组 ， 各组 模 式 串 数 衣 显示 了不 同模 式串 长度 和数 目 下 ， 箅法较其 （ 丨 数 査 找 时 间 随 拟式 数 口 变化 的悄况 表 綠 査 釤 丨 务 侔 一 一 “ 一 “ “一 ” 憤 力 数 平 均 比较 数 随 镆 式 丨 数 丨 变 化 的悄 况 阁 査 找 时 间 和 平均 比 较 搡 作 数 ， 在 箅 法 执行 的 过 程 中 比 较 拗 作 和状 态 转 移 是 十 分 耗 时的 。 与 算法 和 ， 算法 相 比 ， 算法进 一 步 减少 ， 了 比 较 操 作和 状态转移 进 而 在 性能 ， 获 得 了 明显 提 升 。

6、 細 、 冬 所不 ， ， 其中 模式 串 ， 度 可以看 出 在模 式 串 较 少 时 ， 箅法 、 算 法和 ， 箅法 都 初 较 好 的 性 能 能 也 更 加 稳定 。 但 箅 法 平 均代 价 史 低 ， 性 这娃 为 在模式 中 较少 时 模 式 串 集合 中 ， 出 现 的 字符 较 少 算法 和 ， 算法 跳 转 函 数 的 值 较 大 发 现 坏 字符 的 概 卒 也 较 大 扣 函 数 的 优 化 作 用 十分 明 显 ， ； 但随肴模式 串 数 的 增加 ” “ ， 单 个 字符 出 现的 概率 迅速 升 商 ， 好后缀出 现 的概 率 、 断增加 跳 转 函 数 的 值

7、 和 发现 坏 字 符 第 卷 第 期 许家 铭 ， 李晓东 ， 金 键 ， 等 一 ： 种 高 效 的 多 模 式字 符 串 匹 配 算 法 的 概 率 则 迅速 减 小 双 字 符 出 现 的概 率 ， 、 函 数 的 优 化作 用 明 显 减 弱 丨 然而 结 束语 本 文将 了 ， 及賊 模式 。 数勒 刷 加 的 逨 率 比 单字符小 和坏前 缀规则 ， 多 字符 ， 算法和 職与 。 算 法 相结 合 ， 提出 增 加 了 调 用 咖 函 数 的概 率 、 ， 使 却 函数 种 快逨 的 多 模 式 叩 二 法 ！ 在 匹配 过 柳 能够 尺 二 樣 在 模式 串 较 多 时 仍

8、具有 较大 的值 且 始 终 起 绝 大部 分 的 优 化作用 ， 大 幅 减 少 了 比较 操 作 数 平况下本文豸 。 法 有 较 好 的 性能 ， ， 在 各 项 评 价 指 标 上均 优 于 且 对 模式 串 数 目 算法 ， 、 丨 算 法和 的 增 加不 敏 感 ， 性 、 能 更 加 稳定 信 息 检 索等 。 本 文 算 法 可 应 用 于多 种 领 域 如入 侵检测 。 后 续 研 究 工 作将 在 提 高 匹 配 效 率 的 基 础 上 ， ， 对算法进 行改 进 一 以 降 低 最 坏 情 况 下 的 时间 复 杂 度 参 考文 献 。 、 滄 書 參 畚 投式 数 函 数调 丨 丨丨 随校式 串数 丨 丨 变 化 的悄 况 ？ 一 一“ ， “ ， 揹式审 数 函 数 跳 转 距 离随 模 式 串 数 变 化的 情况 】 图 ” 坏 字 符 规 则 和 好 后 缀 规 则 优 化效 果 对 比 ， 王 永成 ， 沈 州 ， ， 许 ， 一 躧 改进 的 多