《巨量串匹配基礎》討論如何把巨量字元串的串匹配問題自動生成一個最佳化的完全自動機，以及其簡化和有效硬體的實現，進一步討論模糊化的U-不確定控制下的巨量字元串和干擾條件下的V-不確定控制下的巨量字元串的串匹配，以及超長字元串的部分匹配的算法和硬體實現方法。《巨量串匹配基礎》的有關研究工作前後得到國家自然科學基金GJZRJJ-60873002的資助，973課題2007CB311103的資助。《巨量串匹配基礎》可作為計算機科學技術相關專業領域研究人員提高理論素質的參考書，也可以作為相關專業研究生學習專業基礎的研究資料。
基本介紹
- 書名：巨量串匹配基礎
- 作者：高慶獅 高小宇
- 出版日期：2012年1月1日
- 語種：簡體中文
- ISBN：9787030330604, 7030330609
- 外文名：Foundation of Matching in Massive Strings
- 出版社：科學出版社
- 頁數：73頁
- 開本：32
- 品牌：北京科瀚偉業
內容簡介,圖書目錄,
內容簡介
《巨量串匹配基礎》編輯推薦：串匹配在網路安全（網路入侵檢測、計算機病毒特徵碼匹配、保密通訊，信息監控、國家網際網路骨幹網的有害信息防治，等等），生物計算（DNA序列匹配，蛋白質計算），拼寫檢查、搜尋引擎、語言翻譯、數據壓縮，等等重要領域上有廣泛套用。《巨量串匹配基礎》在介紹前人主要成果的基礎上，以作者在該領域獲得的成果為主軸，系統討論各種類型的“他匹配”和“自匹配”的理論模型、求解算法和計算複雜性，以及面向算法的計算機系統結構模型。
圖書目錄
第1章 緒論
1.1 需求
1.2 半個世紀研究工作（1951-2001年）的總結
1.3 Shift-Or算法
1.4 多字元串匹配
1.5 Aho-Corasick算法與Aho-Corasick自動機
1.6 完全自動機與擴展的Aho-Corasick自動機
第2章 巨量字元串匹配完全自動機的自動生成
2.1 Bi-構成樹的形成
2.2 狀態分配：Bi-構成樹節點編碼形成
2.3 相似子樹：狀態轉換補充連線
2.4 狀態連線補全
2.5 計算複雜性
2.6 一個例子
第3章 面向巨量字元串匹配完全自動機的專用系統結構
3.1 雙元素的樹節點表示與第5步的完全連線
3.2 一個例子
3.3 實現巨量串匹配完全自動機的專用計算機系統結構描述
3.4 參數變化的影響
3.5 巨量串匹配完全自動機並行處理
第4章 帶U-V控制的巨量字元串匹配完全自動機
4.1 U-不確定串中的相交和同源後續奇點引起的問題
4.2 U-不確定串的不相交化
4.3 U-不確定串的同源後續奇點的兩種解決方法
4.4 U-不確定串的無同源後續奇點化的形式描述
4.5 兩兩不相交且無同源後續奇點的U-不確定字元串的完全自動機
4.6 快速自動生成V-不確定串多串匹配完全自動機算法
4.7 V-不確定字元串多串匹配需要多台並行工作的完全自動機
4.8 快速自動生成U-V-不確定串多串匹配完全自動機算法
4.9 多U-V-不確定串的交錯
4.10 U-V-不確定串多串匹配需要並行工作的多完全自動機台數與正則表達式匹配可能的遺漏
4.11 一個例子
第5章 多超長串部分匹配完全自動機及其專用系統結構
5.1 問題與方法
5.2 基本硬體系統
5.3 兩段字元串（At，Bip）比對的工作流程
5.4 一個例子
5.5 求出匹配成功準確字元串
5.6 求出多個匹配成功字元串的準確位置
5.7 幾個問題的討論
參考文獻
1.1 需求
1.2 半個世紀研究工作（1951-2001年）的總結
1.3 Shift-Or算法
1.4 多字元串匹配
1.5 Aho-Corasick算法與Aho-Corasick自動機
1.6 完全自動機與擴展的Aho-Corasick自動機
第2章 巨量字元串匹配完全自動機的自動生成
2.1 Bi-構成樹的形成
2.2 狀態分配：Bi-構成樹節點編碼形成
2.3 相似子樹：狀態轉換補充連線
2.4 狀態連線補全
2.5 計算複雜性
2.6 一個例子
第3章 面向巨量字元串匹配完全自動機的專用系統結構
3.1 雙元素的樹節點表示與第5步的完全連線
3.2 一個例子
3.3 實現巨量串匹配完全自動機的專用計算機系統結構描述
3.4 參數變化的影響
3.5 巨量串匹配完全自動機並行處理
第4章 帶U-V控制的巨量字元串匹配完全自動機
4.1 U-不確定串中的相交和同源後續奇點引起的問題
4.2 U-不確定串的不相交化
4.3 U-不確定串的同源後續奇點的兩種解決方法
4.4 U-不確定串的無同源後續奇點化的形式描述
4.5 兩兩不相交且無同源後續奇點的U-不確定字元串的完全自動機
4.6 快速自動生成V-不確定串多串匹配完全自動機算法
4.7 V-不確定字元串多串匹配需要多台並行工作的完全自動機
4.8 快速自動生成U-V-不確定串多串匹配完全自動機算法
4.9 多U-V-不確定串的交錯
4.10 U-V-不確定串多串匹配需要並行工作的多完全自動機台數與正則表達式匹配可能的遺漏
4.11 一個例子
第5章 多超長串部分匹配完全自動機及其專用系統結構
5.1 問題與方法
5.2 基本硬體系統
5.3 兩段字元串（At，Bip）比對的工作流程
5.4 一個例子
5.5 求出匹配成功準確字元串
5.6 求出多個匹配成功字元串的準確位置
5.7 幾個問題的討論
參考文獻
