數據索引與數據組織模型及其套用

《數據索引與數據組織模型及其套用》是2012年出版的圖書，作者是胡運發。本書是面向海量數據處理的屬於數據與知識工程範疇的學術專著。

基本介紹

• 書名：數據索引與數據組織模型及其套用
• 作者：胡運發 著
• ISBN：978-7-309-08694-2/T.442
• 頁數：204頁

出版信息

定價: 30 元

字數: 335千字

開本: 16 開

裝幀: 平裝

出版日期: 2012年7月

內容提要

本書從數據組織的觀點處理數據索引問題，提出一種互關聯後繼索引的商空間模型，從數學變換角度論證該模型優越於現有經典索引模型的多種特性：保序，睦、保假性和壓縮性，導出多種優越能力： (1)log級的快速查詢能力；(2)原文生成能力； (3)高度的壓縮能力。

本書以互關聯後繼索引模型為中心，與多種領域的核心問題相結合，說明該模型如何對數據壓縮、全文資料庫、關係資料庫、Web資料庫、演繹資料庫、知識庫、文本信息隱藏、數據挖掘等領域產生創新性的影響，從而生成一系列新成果。

本書對從事關係資料庫、Web資料庫、事務庫、演繹資料庫、知識庫、邏輯語言、搜尋引擎、數據云、數據壓縮、文本分類、數據挖掘等領域的研究人員、工程技術人員、高等院校的教師與學生有重要的參考價值或借鑑作用。

作者簡介

胡運發，1964年復旦大學數學系畢業，後任該校計算機系教授，博士生導師。研究方向是數據、知識工程與知識庫、創建新型數據索引與數據組織模型。 曾參加我國銀河億次計算機的研製工作、邏輯語言Prolog的開發、智慧型計算機的研製，承擔 “八六三”項目六次，國家自然科學基金項目四次，參加國家自然科學基金重點項目兩次。期間獲得電子工業科技進步二等獎(1986)、國防科工委科技進步一等獎(1994)及二等獎兩次、中國人民解放軍三等功一次、上海科技進步獎二等獎6項。發表論文100餘篇，翻譯出版《劍橋五重奏》(上海科技出版社2003，獲得牛頓科技普及二等獎)，編著教材《數據與知識工程導論》(清華大學出版社，2003)及《人工智慧系統原理與設計》(國防科技大學出版社，1989)。獲得與本專著有關的國家專利一項(2000)。

目錄

上篇

第一章 第一後繼字元有序的互關聯後繼樹索引模型3

1.1全文檢索模型綜述

1.1.1點陣圖（Bitmap）

1.1.2署名檔案（Signature Files）

1.1.3倒排表（Inverted Files）

1.1.4Pat樹和Pat數組

1.1.5∑2相鄰矩陣模型

1.1.6全文索引模型的評價標準

1.2第一後繼字元有序的互關聯後繼樹

1.2.1基本定義

1.2.2後繼區間概念介紹

1.2.3創建第一後繼有序的互關聯後繼樹創建算法

1.3後繼區間查詢算法

1.4後繼區間查詢算法複雜度及其性能分析

1.5實驗與分析

1.6小結

第二章 雙排序互關聯後繼樹創建與查詢算法

2.1引言

2.2雙有序互關聯後繼樹索引創建算法

2.3雙排序互關聯後繼樹查詢算法

2.3.1逆向區間二分查詢算法

2.3.2雙排序互關聯後繼樹二分驗證查詢算法

2.3.3雙排序互關聯後繼樹線性最佳化查詢算法

2.4實驗與分析

第三章 互關聯後繼樹索引的編碼最佳化方法

3.1引言

3.2編碼方案

3.3位編碼算法

3.4原文生成算法

3.4.1字元定位算法

3.4.2後繼樹編碼計數算法

3.4.3後繼樹編碼值算法

3.4.4原文根地址算法

3.4.5原文生成算法

3.5全文檢索算法

3.6實驗數據及分析

3.7小結

第四章 基於互關聯後繼樹索引的文本壓縮

4.1文本數據壓縮的常用技術

4.1.1數據壓縮

4.1.2文本壓縮技術的分類

4.1.3幾種主要的壓縮模型

4.1.4文本壓縮技術的套用

4.1.5壓縮的評判標準

4.2後繼樹靜態詞典壓縮

4.2.1互關聯後繼樹靜態詞典的設計

4.2.2壓縮和解壓算法

4.2.3靜態詞典壓縮算法改進

4.2.4性能比較與分析

4.3互關聯後繼樹自適應詞典壓縮

4.3.1互關聯後繼樹自適應詞典的設計

4.3.2壓縮和解壓算法

4.3.3壓縮算法改進

4.3.4互關聯後繼樹自適應壓縮算法特點

4.3.5性能比較與分析

4.3.6小結

第五章 基於後繼模式樹的XML索引模型

5.1引言

5.2基於後繼模式樹的倒向XML索引

5.3XML的統一索引模型

5.3.1聯合索引的創建

5.3.2XML數據與全文數據的協同查詢

5.4XPath的自頂向下與自底向上查詢

5.4.1絕對位置路徑的查詢樹解析

5.4.2自頂向下查詢

5.4.3自底向上查詢

5.5基於後繼模式樹的協同查詢

5.5.1後繼模式樹上的路徑查詢

5.5.2基於後繼模式樹的自底向上協同查詢

5.6系統實現與實驗

5.7小結

第六章 基於互關聯後繼模型的搜尋引擎

6.1引言

6.1.1搜尋引擎的原理

6.1.2主流搜尋引擎介紹

6.1.3黃頁搜尋引擎基本需求

6.2基於互關聯後繼索引的搜尋引擎

6.2.1搜尋引擎與互關聯後繼樹的結合

6.2.2互關聯後繼樹搜尋引擎的索引結構

6.3匹配度計算

6.3.1匹配度定義

6.3.2匹配度計算公式

6.3.3匹配度計算實現技術

6.3.4詞位置號的保存

6.3.5匹配度計算

6.3.6實驗與分析

6.4搜尋結果排序技術

6.4.1通用排序算法介紹

6.4.2基於動態劃分的多權值快速排序

6.4.3基於區間的劃分算法

6.5小結

下篇

第七章 序列文本索引的粒子模型

7.1引言

7.2文本索引的粒子模型

7.2.1序列對象有序化

7.2.2有序化的序列對象粒子化

7.2.3有序化的序列對象粒子的結構關係

7.3互關聯後繼索引—文本序列商空間Istr1, 2的性質

7.3.1商空間的熵的性質

7.3.2保假性與保序性

7.3.3Istr1, 2的特殊性質

7.4小結

第八章 創建索引模型的數學方法

8.1創建全文索引模型的數學變換

8.2互關聯後繼索引模型性能分析與比較

8.2.1倒排表和Pat數組的性能分析

8.2.2互關聯後繼索引模型性質

8.2.3分析與比較

8.3存儲模型比較分析

8.3.1原文和索引都在記憶體

8.3.2原文在外存索引放置於記憶體的情況

8.3.3原文和索引都放置於外存的情況

8.4與Pat樹等其他索引模型的關係

8.5小結

第九章 互關聯後繼索引模型的熵與壓縮原理

9.1引言

9.2粒子細分的方法不能降低信息量

9.3公因子方法壓縮原理

9.4差異熵壓縮的原理

9.4.1一元編碼

9.4.2Golomb方法

9.4.3編碼模式方法和實例

9.5小結

第十章 事務庫的組織與數據挖掘

10.1FP-Growth方法簡介

10.2隱式互關聯間接後繼樹/圖的挖掘方法

10.2.1隱式互關聯間接後繼樹（/圖）表示

10.2.2ISTR+樹創建算法

10.2.3Istr+樹頻繁項集挖掘算法

10.2.4Istr+樹挖掘算法與FP-growth算法的比較

10.3可變維數的隱式間接互關聯後繼樹的挖掘方法

10.3.1可變維數的隱式間接互關聯後繼樹表達

10.3.2T-Istr+間接後繼表的性質與頻繁項的挖掘算法

10.3.3算法複雜性分析

10.4小結

第十一章 關係資料庫與演繹資料庫的數據組織

11.1協同查詢問題的回顧

11.2關係的互關聯後繼的數據表達

11.3關係R?Istr+互關聯隱式間接後繼索引表與演算

11.3.1基於R?Istr+索引表的關係演算

11.3.2R?Istr+查詢操作的複雜性分析

11.4基於R?Istr+的關係庫的協同查詢

11.5演繹資料庫的索引與演繹

11.5.1演繹資料庫的索引

11.5.2基於I-Istr+的基本查詢算法（集合查詢算法）

11.5.3演繹資料庫的演算

11.5.4對規則的演算

11.5.5複雜性的對比

11.6小結

第十二章 邏輯程式或知識庫的索引

12.1邏輯程式的簡單介紹[Hu88]

12.2嚴格有序的邏輯程式的索引模型

12.2.1第一種函詞的序列表示

12.2.2創建邏輯子句索引的步驟

12.2.3互關聯後繼樹索引與Warren抽象機數據的關係

12.2.4基於互關聯後繼索引的合一操作——索引合一

12.2.5推理步驟說明

12.2.6子句的或並行

12.2.7串列執行機制的改進——子目標級別優選

12.3邏輯程式並行性

12.3.1第二種函詞表示方法

12.3.2創建互關聯後繼索引的步驟

12.3.3合一中的並行

12.3.4邏輯程式並行推理的實例

12.4結論

第十三章 基於互關聯後繼數據組織模型的文本信息隱藏技術

13.1引言

13.2相關技術與術語介紹

13.2.1術語介紹

13.2.2相關技術介紹

13.3基於互關聯後繼索引模型的文本信息隱藏方法

13.3.1信息隱藏過程

13.3.2信息提取過程

13.3.3控制功能

13.4安全強度分析

13.5小結

參考文獻