IT·行·思·录

Lantern论文检索系统于10月份的时候开始酝酿，最近用了12天集中编码实现，发点感慨。 系统组成总体上比较简单： 服务器是Linux+Apache HTTP Server+Apache Tomcat 7.0.5； Apache PDFBox 1.3.1提取pdf文件； libcurl 7.21.2抓取网页，分析完的pdf链接给迅雷下载（我真懒）； 用Apache Lucene 3.0.3进行索引建立和查询； 使用jQuery 1.4.1（autocomplete插件）做自动补全功能； 用ImageMagic将pdf转化为图像，配合AJAX技术做pdf预览； Flex SpringGraph做作者关系图（主要由zfr同学完成）； 界面优化和Logo设计有hx同学完成； 使用了Java、JSP、Flex、C++编码； 各种软件搭在一起学起来工作量就有点大，另外由于本人原来一直习惯命令编程模式，没有写过JSP，也不会Javascript和CSS，原来计划的写前端队友由于各种考试没有时间，所以本人只能临阵磨枪——不过w3cschool很不错，jQuery、AJAX现学现用还算比较快，主要浪费的时间是跟论文的各种结构斗争。 一些经验和思考： 最开始抓取网页的时候由于访问太过频繁，被封IP了，可见爬虫一定要有礼貌，最好伪装成普通用户的访问频率。 由于论文的无结构性，加上PDFBox或各种软件都无法规避文章中公式、图片等带来的如无意义文本的问题，从pdf文件中抽取论文各部分内容是一个比较麻烦的问题，最后都没有做好。 建立索引的时候（特别是大数据量的时候）要充分分析自己的需求，比如提取snippet的时候Lucene的highlight包需要位置索引，对于每个field是否分析也很不一样…… 各种基本功能要做好都很复杂（不然为啥搜索引擎公司就写那么几个界面也要几千人），比如自动补齐和相关推荐我最后直接用词典、高频短语、简单n-gram轮排索引，结果显得很粗糙；归一化、停用词实现起来各种问题……这一个个不起眼的细节后面都隐藏着很多大的难题。 以一些系统效果贴图结束——

一个月前左右的某晚与Doctor Bai、Felix021讨论一个问题，其中要解决用尽量少的空间在尽量少的时间内查找一个集合中的一个元素（可以进行预处理）。 当时我们分析了trie、binary tree、block tree、hashing等各种查询方法的时空复杂度方面的优势劣势。讨论到最后对时空复杂度的限制都到了苛刻的地步。为了达到空间复杂度严格为n、每次查询时间复杂度为O(1)，我提出针对已知数据集构造一个“特别”的哈希函数，该函数对于当前数据集满足任意两个不同的key通过哈希后不会产生冲突。 当时felix用实际经验佐证这几乎是不可能的，Doctor Bai也对此持怀疑态度，不过还是承认：对于特定的数据集合，这种函数是可能存在的。 最近在读《深入搜索引擎》（Managing Gigabytes即MG的中文版）时居然遇上了这种避免所有冲突的哈希函数——最小完美哈希函数。 以下转述MG中对于最小完美哈希函数的介绍。 哈希的一些概念 哈希是一种常用的具有查找表功能并且提供平均情况下快速访问的标准方法。 哈希函数h：将n个键值xj的集合映射到一个整数集合的函数h(xi)，其值域是0<=h(xj)<=m-1，允许重复。 其中m>n/a，a（<=1）是装载因子。a越小，两个不同键值在相同哈希值相互冲突的可能性越小，然而冲突总是不可避免。 完美哈希函数 若一个哈希函数满足对于任意的xi和xj，当且仅当i=j时才有h(xi)=h(xj)，就是完美哈希函数(Perfect Hash Function, PHF)。即对一个键值集合L进行哈希时，不可能产生任何冲突。 如果哈希函数不仅是完美的，并映射到值域范围m=n，n个键值中的任意一个都一一映射到唯一整数，这是装载因子a=1，该函数称为“最小完美哈希函数”(Minimal Perfect Hash Function, MPHF)。 若一个最小完美哈希函数同时满足对于xi<xj，有h(xi)<h(xj)，即满足“保序性”（order preserving），则称为保序最小完美哈希函数(Order Preserving Minimal Perfect Hash Function, OPMPHF)。 当然，以上性质都是针对某一个键值集合L的，即所得哈希函数对于另外的键值集合可能不在满足以上性质。 完美哈希函数的设计 最小完美哈希函数是针对特定函数集合的，所以生成这些哈希函数需要对所求单一静态集合进行预计算生成函数。 最小完美哈希函数公式： h(t) = ( g(h1(t)) + g(h2(t)) ) % n h1(t1) = sum(t[i]*w1[i] ,  i:1–>|t|) % m h2(t1) = sum(t[i]*w2[i] [...]