1、 I 3 2 0 計 獲 得 更 多 的 跳轉 。 算 機 工 程 算法和 ， 年 月 日 相 同 的 代價 下 ， 。 總之 ， ， 本文 算 法 使 代 價 與 算法相 比 ， 箅 法在 模 式 串 較 長 當 模式 串 長 度 在 函 數 的 分子 減 小 分 母 增 大 平 均 情 況 下 本 文算 法 較 。 和 模 式 數 較少 時 性 能 改進 更 多 ， 。 之 箅法的 箅法 、 算 法和 算法的 時 間 復雜 度更 優 間且模式較少 時 算法查找時間僅為 算法的 。 允 聆斗 坧 為 測試本文 左右 ， 算 法的 左右 ， 算 法的 當模 式 串長 度大于 時 箅 算法 的性

2、 能 ， 并與 ， 算法 、 法對 性 能 的 改 進 更 大 個 比較 。 算法 、 箅 法和 ： 算 法 進行 橫 向 對 比 （ 選取 以 下 在實 際 應 用 中 一 ， 大 部 分模 式 串 的 長 度 都 在 ， 以上 】 。 為 評 價 栴 標進 行 考察 查找 時間 。 （ 文 中 單個字 符平均比 。 般 情況 下 算 法 的平 均性 能 。 隨 機 選取 長 度 在 以上 較 次數 ， 即 箅法 執行字 符 比 較操作 總 數除 以 文 本 長度 ， 模 式 串 進 行 實 驗測 忒 。 跳 轉 閑 數 調 用 次數 即 分 別 調 用 函 數 出 跳 轉 函 數跳 躍 距

3、 離 即 分 別 調 用 函 數 ： 和 吻 的次數 圖 屮 數 據 顯示 ， ， 隨 著模 式串 數 目 増加 ， 箅法的 査 ， 辦 和 從扣 跳 過 的 找 時 間 基 本 穩定 其 余 算法 的 査 找 時 間 和 平 均 比 較 操 作 數 且 增 長 速 率逐 漸 放 級 。 總字符 數 之和 距 離之 和 。 （ 平均 收益 ， ， 即跳 躍 距離 之 和除 以 比 較操作數 均 呈亞 線 性 增 長 度 算 法的 ， 其中 ， 欖 式串 長 平均代價 。 即 發現 失 配 所 花 的 代 價 之 和 除 以 跳 躍 箅 法 的查 找 時 間 是 算法 的 ； 箅法的 左右 箅法

4、 的 丨 ， 箅 實 驗環境 如 內存 ； 操 作系 統 ， 法的 左右 箅 法的 平均比 較操作 數是 算法 的 算法和 ， 算 法均選用 開源軟件 算 法和 本文算法均采 左右 ， 箅 屮 的實 現 版 本 算法 、 法的 左右 。 用 語言 實 現 。 待 閃 配 文 本 由 路透社 的 新 聞 文 本 數 據集 ， 一 組成 ， 共約 。 待匹配模 式串集 合 。 從 站提 供 的 島 頻 詞 匯 表 中 隨 機 選 取 為 考 察模 式 串 長 度 和 數 丨 對 箅 法 性 能 的 影響 目 ， 模 式 串 按長 度 分 為 個 部分 目從 丨 ， 各 以 邢 分 冉按照串 數 為

5、 單位 遞 增 。 分為 組 ， 各組 模 式 串 數 衣 顯示 了不 同模 式串 長度 和數 目 下 ， 箅法較其 （ 丨 數 査 找 時 間 隨 擬式 數 口 變化 的悄況 表 綠 査 釤 丨 務 侔 一 一 “ 一 “ “一 ” ° 憤 力 數 平 均 比較 數 隨 鏌 式 丨 數 丨 變 化 的悄 況 閣 査 找 時 間 和 平均 比 較 搡 作 數 ， 在 箅 法 執行 的 過 程 中 ° 比 較 拗 作 和狀 態 轉 移 是 十 分 耗 時的 。 與 算法 和 ， 算法 相 比 ， 算法進 一 步 減少 ， 了 比 較 操 作和 狀態轉移 進 而 在 性能 ，

6、獲 得 了 明顯 提 升 。 細 、 冬 所不 ， ， 其中 模式 串 ， 度 可以看 出 在模 式 串 較 少 時 ， 箅法 、 算 法和 ， 箅法 都 初 較 好 的 性 能 能 也 更 加 穩定 。 但 箅 法 平 均代 價 史 低 ， 性 這娃 為 在模式 中 較少 時 模 式 串 集合 中 ， 出 現 的 字符 較 少 算法 和 ， 算法 跳 轉 函 數 的 值 較 大 發 現 壞 字符 的 概 卒 也 較 大 扣 函 數 的 優 化 作 用 十分 明 顯 ， ； 但隨肴模式 串 數 的 增加 ” “ ， 單 個 字符 出 現的 概率 迅速 升 商 ， 好后綴出 現 的概 率 、 斷

7、增加 跳 轉 函 數 的 值 和 發現 壞 字 符 第 卷 第 期 許家 銘 ， 李曉東 ， 金 鍵 ， 等 一 ： 種 高 效 的 多 模 式字 符 串 匹 配 算 法 的 概 率 則 迅速 減 小 雙 字 符 出 現 的概 率 ， 、 函 數 的 優 化作 用 明 顯 減 弱 丨 然而 結 束語 本 文將 了 ， 及賊 模式 。 數勒 刷 加 的 逨 率 比 單字符小 和壞前 綴規則 ， 多 字符 ， 算法和 職與 。 算 法 相結 合 ， 提出 增 加 了 調 用 咖 函 數 的概 率 、 ， 使 卻 函數 種 快逨 的 多 模 式 叩 二 法 ！ 在 匹配 過 柳 能夠 尺 二 樣 在

8、 模式 串 較 多 時 仍 具有 較大 的值 且 始 終 起 絕 大部 分 的 優 化作用 ， 大 幅 減 少 了 比較 操 作 數 平況下本文豸 。 法 有 較 好 的 性能 ， ， 在 各 項 評 價 指 標 上均 優 于 且 對 模式 串 數 目 算法 ， 、 丨 算 法和 的 增 加不 敏 感 ， 性 、 能 更 加 穩定 信 息 檢 索等 。 本 文 算 法 可 應 用 于多 種 領 域 如入 侵檢測 。 后 續 研 究 工 作將 在 提 高 匹 配 效 率 的 基 礎 上 ， ， 對算法進 行改 進 一 以 降 低 最 壞 情 況 下 的 時間 復 雜 度 參 考文 獻 。 、 滄 書 參 畚 投式 數 函 數調 丨 丨丨 隨校式 串數 丨 丨 變 化 的悄 況 ？ 一 一“ ， “ ， 揹式審 數 函 數 跳 轉 距 離隨 模 式 串 數 變 化的 情況 】 圖 ” 壞 字 符 規 則 和 好 后 綴 規 則 優 化效 果 對 比 ， 王 永成 ， 沈 州 ， ， 許 ， 一 躧 改進 的 多 模 式 匹 配 算 法