深入搜索引擎 海量信息的压缩、索引和查询PDF电子书下载

第1章　概览 1

1.1　文档数据库（document databases） 7

1.2　压缩（compression） 10

1.3 索引（indexes） 12

1.4　文档索引 16

1.5　MG海量文档管理系统 20

1.6　进一步阅读 21

第2章　文本压缩 23

2.1 模型 26

2.2 自适应模型 29

2.3　哈夫曼编码 32

范式哈夫曼编码 38

计算哈夫曼编码长度 44

总结 51

2.4　算术编码 51

算术编码是如何工作的 53

实现算术编码 56

保存累积计数 59

2.5 符号模型 61

部分匹配预测 61

块排序压缩 64

动态马尔科夫压缩 69

基于单字的压缩 71

2.6　字典模型 73

自适应字典编码器的LZ77系列 74

LZ77的Gzip变体 78

自适应字典编码器的LZ78系列 79

LZ78的LZW变体 81

2.7 同步 84

创造同步点 84

自同步编码 87

2.8　性能比较 89

压缩性能 91

压缩速度 94

其他性能方面的考虑 97

2.9　进一步阅读 98

第3章 索引 102

3.1　样本文档集合 106

3.2　倒排文件索引 110

3.3　压缩倒排文件 115

无参模型（Nonparameterized models） 117

全局贝努里模型 120

全局观测频率模型（Global observed frequency model） 123

局部贝努里模型（Local Bernoulli model） 124

有偏贝努里模型（Skewed Bernoulli model） 125

局部双曲模型（Local hyperbolic model） 127

局部观测频率模型（Local observed frequency model） 128

上下文相关压缩（Context-sensitive compression） 130

3.4　索引压缩方法的效果 132

3.5　签名文件和位图 134

签名文件 135

位片签名文件（Bitsliced signature files） 139

签名文件分析 144

位图 147

签名文件和位图的压缩 148

3.6　索引方法的比较 151

3.7　大小写折叠、词根化和停用词 153

大小写折叠 154

词根化 154

影响索引长度的因素 155

停用词（stop word） 156

3.8　进一步阅读 159

第4章　查询 162

4.1　访问字典的方法 166

访问数据结构 167

前端编码（Front coding） 170

最小完美哈希函数 173

完美哈希函数的设计 176

基于磁盘的字典存储 181

4.2　部分指定的查询术语 182

字符串暴力匹配（Brute-force string matching） 182

用n-gram索引 183

循环字典（Rotated lexicon） 184

4.3 布尔查询（Boolean Query） 186

合取查询（conjunctive query） 187

术语处理顺序 188

随机访问和快速查找 189

分块倒排索引 192

非合取查询（Nonconjunctive Query） 194

4.4　信息检索和排名 195

坐标匹配（Coordinate matching） 196

内积相似度 197

向量空间模型 202

4.5　检索效果评价 205

召回率和精确率 205

召回率-精确率曲线 207

TREC项目 208

万维网搜索（World Wide Web Searching） 212

其他有效性评价方法 215

4.6　余弦法实现 216

文档内频率 217

余弦值的计算方法 220

文档权重所需的内存 222

累加器内存 227

快速查询处理 228

按频率排序的索引 229

排序 233

4.7　交互式检索 236

相关性反馈 237

概率模型 239

4.8　分布式检索 241

4.9　进一步阅读 245

第5章　索引构造 248

计算模型 251

索引构造方法概览 252

5.1　基于内存的倒排 253

5.2　基于排序的倒排 256

5.3　索引压缩 260

压缩临时文件 261

多路归并 264

原地多路归并 265

5.4　压缩的内存内倒排 271

大内存倒排 271

基于字典的切分（Lexicon-based partitioning） 276

基于文本的切分 278

5.5　倒排方法的比较 281

5.6　构造签名文件和位图 282

5.7　动态文档集合 284

扩展文本（Expanding the text） 284

索引扩展（Expanding the index） 285

5.8　进一步阅读 290

第6章　图像压缩 292

6.1 图像类型 293

6.2　CCITT二值图像的传真标准 297

6.3　二值图像的上下文压缩 301

上下文模型 304

二值上下文模型 307

“超视力”压缩（Clairvoyant compression） 309

6.4　JBIG：二值图像标准 310

分辨率降低（Resolution reduction） 311

模板和自适应模板 316

编码及概率估计 317

6.5　连续色调图像的无损压缩 318

GIF和PNG无损图像格式 319

FELICS：快速、有效且无损图像压缩系统 321

CALIC：基于上下文自适应无损图像解码器 325

JPEG-LS：无损图像压缩新标准 326

6.6　JPEG：连续色调图像标准 328

6.7　图像的递增传输 333

金字塔编码 334

金字塔编码的压缩 335

中位数聚合 337

误差模型 338

6.8　图像压缩技术总结 339

6.9　进一步阅读 340

第7章　文本图像 342

7.1　文本图像压缩概念 344

7.2　有损压缩和无损压缩 348

7.3　标记抽取 350

跟踪标记的边界 350

清除图像中的标记 353

按自然阅读顺序排序标记 355

7.4　模板匹配 356

全局模板匹配 357

局部模板匹配 359

基于压缩的模板匹配 360

库模板筛法 363

评价模板匹配方法 364

7.5　从标记到符号 368

库构造 368

符号及其偏移量 370

7.6　编码文本图像分量 371

库 371

符号数 372

符号偏移 372

原始图像 373

7.7　效果：有损和无损的模式 375

7.8　系统考虑 381

7.9　JBIG2：图像文本压缩标准 382

7.10　进一步阅读 384

第8章　混合图文 385

8.1　方向 387

用Hough变换检测直线 388

左侧留白查找 390

投影轮廓 391

从斜率直方图到文本谱 396

8.2　切分 400

自下向上的切分方法 400

自上向下的组合的切分方法 402

基于标记的切分 403

使用短文本字符串切分 405

利用文本句法切分 408

8.3　分类 409

8.4　进一步阅读 412

第9章　系统实现 414

9.1　文本压缩 415

选择压缩模型 416

选择编码器 419

哈夫曼编码的限制 421

长度限制的编码 427

9.2　文本压缩效果 432

压缩有效性 432

解压速度 436

解压内存 436

动态文档集合 439

9.3 图像和文本图像 441

压缩二值图像 443

压缩灰度图像 444

压缩文本图像 444

9.4　构造索引 446

9.5　索引压缩 448

9.6　查询处理 450

布尔查询 450

排名查询 453

9.7　进一步阅读 455

第10章　信息爆炸 457

10.1　信息技术发展2000年 457

10.2　Internet：一种全球信息资源 459

10.3　纸张问题 462

10.4　面对信息爆炸 464

网页搜索引擎 464

基于代理的信息检索 466

数据挖掘 468

10.5　数字图书馆 468

10.6　更好地管理海量数据 470

10.7　小就是美 472

10.8　对生活的个人信息支持 474

10.9　进一步阅读 475

附录A　MG系统指南 477

A.1　安装mg系统 477

A.2　一个简单的存储和检索例子 479

A.3　数据库创建 484

A.4　对一个索引文档集合进行查询 488

A.5　非文本文件 490

A.6　图像压缩程序 492

附录B　新西兰图书馆 493

B.1　什么是NZDL 493

计算机科学报告（Computer Science Technical Reports） 493

其他文档集合 496

文档集合的发展 502

音频集合（audio collections） 502

音调索引（Melody Index） 503

B.2　NZDL是如何工作的 505

原始文档 505

搜索和索引 506

B.3 影响 508

B.4　进一步阅读 508

参考文献 509