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

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

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

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

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

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

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

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