1、 导言
信息检索是自动辨认和分类文字信息的进程，它的意图是从文档中提取出与用户恳求相关的信息 。文档的基本单位是词，词在文档里呈现的次数（以下称之为频率）是衡量词自身重要性的一个目标 。而词在一条句子里的呈现次数（以下称之为密度）则决议了这条句子的重要性。所以说句子的重要性由构成句子的词的呈现频率以及该词在句子里的密度这两个要素决议。依据这种逻辑咱们能够运用关键词的频率和密度来标明文档里的重要句子，然后将文档内容进行分类，防止语言学里杂乱的语法和句法剖析，一起还能得到相对精确的成果。在实际操作中，呈现频率极高和极低的词将被疏忽，因为这些词往往与文档的内容关系不大。经过去除一些预界说的高频词和近义词将显着下降信息检索的作业量，之后得到的关键词列表则能够用来辨认重要的句子。这些句子很有或许包括了和文档内容最密切相关的信息，所以这些句子将被用来与用户输入的恳求作比较，作为检索成果回来给用户。这种信息检索办法的中心是核算每个关键词在文档里的呈现次数，并依据各个词的重要性对词列表进行排序。本文第二部分将介绍一种硬件哈希算法来加快关键词的计数作业，而排序则将作为后续作业进行研讨。
2 、办法描绘
在核算关键词在文档里呈现次数的进程中，需求一种存储结构来存储相关信息，这种存储结构有必要易于履行查找、刺进及删去操作。哈希是一种以常数均匀时刻履行查找、刺进和删去操作的算法。在核算关键词在文档里的呈现次数时运用哈希算法能够大大下降查找次数 。抱负的哈希表数据结构是一个包括有关键字的具有固定巨细的数组。一般状况下一个关键字便是带有相关值（关键词及其在文档里的呈现次数）的字符串。假定哈希表的巨细为TableSize，则每个关键字被映射到从0到TableSize-1这个范围内的某个数，并且被存放到对应的存储空间。这个映射称之为哈希函数，抱负状况下哈希函数应该核算简略并且应该确保两个不同的关键字映射到不同的单元，不过因为单元的数目是有限的，而关键字一般状况下是远远大于单元数意图，所以两个关键字有或许哈希到同一个单元，这种状况称之为抵触。因而咱们需求寻觅一个哈希函数，该函数要在单元之间均匀的分配关键字，尽或许的将抵触发生的概率降到最低。
图1 硬件哈希结构
如图1（a）所示，首要将文档转换为一个关键词的列表，之后这个列表将经过哈希函数映射到哈希表数据结构中。每个关键词都将经过哈希函数映射到哈希表中的一个单元，假如该单元已经有内容，则比较该内容与输入的关键词是否相同，相同则“呈现次数”添加一次；不同则为抵触，抵触处理计划将在后边介绍；假如该单元没有内容则阐明输入的关键词是榜首次呈现，则将该关键词存储在这个单元，“呈现次数”计为一次。哈希函数经过FPGA硬件来完结，为了有用运用FPGA的硬件资源，选用按位异或并与素数相乘的哈希算法。在实际操作中这个算法将被用来作为榜首级的哈希函数，发生初始哈希表地址，因为关键词是一个可变长度的字符串，不能直接存储在哈希表里，取而代之的是一个指针（如图1（b）所示）。这个指针指向存储器堆里的一块存储区，关键词及其呈现次数存储在这块存储区内。为了标明指针指向的存储区是否有内容，哈希表中除了存储指针之外还需求存储指针指向的存储区的状况。这些作业由一个硬件堆存储控制器来办理 。输入的关键词首要经过榜首级哈希函数映射到哈希表中的状况指示和指针，假如状况指示为有内容，则经过指针得到其指向的存储内容，与输入关键词比较，相同则“呈现次数”添加一次，不同则经过抵触处理计划处理；假如状况指示为无内容，则阐明输入的关键词是榜首次呈现，该关键词将被存储到这块存储区，“呈现次数”计为一次。为了将比较运算的时刻降到最小，数据宽度需求尽或许宽一些，然后答应多个字符的比较并行完结。
抵触处理计划的本质是将发生抵触的数据存储在一个保存区域。一般的抵触处理计划分为两种：链表法和敞开寻址法。链表法将一切映射到同一地址的关键字放在一个动态分配的链表里。因为给链表里新的关键字分配空间需求时刻，然后导致这种计划的速度相对较慢，并且算法实际上还需求完结另一种数据结构（链表），因而并不适合在信息检索里运用。本文选用的是敞开寻址法来处理抵触。敞开寻址法的数据和保存区域在一个表里，运用伪随机勘探法，答应每个循环发生一个新的勘探地址。敞开寻址法的一个缺陷在于当哈希表里的条目添加的时分抵触的次数和查找途径的长度也跟着添加，然后导致均匀检索时刻的添加。因而，它的功能由表密度而不是列表长度决议，而表的巨细则依赖于运用数据和希望的功能。
3、 硬件完结及试验成果
本文的硬件结构依据Xilinx Virtex-II FPGA，其最高频率为127.47MHz，FPGA资源运用率为392/5120 = 7.6%。文档存储运用1片128M x 72位的SDRAM，哈希表存储运用2片1M x 36位的ZBT（零总线翻转）SRAM。本文第二部分描绘的算法经过一个5级流水线 来完结，如图2所示。每级需求的时钟周期的数目在图2（a）中给出，其间N为查找关键字的字符数，括号内为至少需求的时钟周期数目。为了最优化功能，3个干流水线是堆叠的，如图2（b）所示。
图2 处理进程流水线
将这种结构的功能与软件完结做一下比较，比较成果见表1，运用的测验数据集是相同的。
4、 定论
本文描绘了一种依据FPGA的硬件哈希算法，该算法用来加快信息检索进程中的关键词计数作业，试验成果表明，运用FPGA硬件哈希算法在进步信息检索速度方面显着优于高主频处理器上的软件完结。
本文作者立异点：本文经过运用关键词呈现的频率和密度来标明文档里的重要句子，然后将文档内容进行分类，防止了语言学里杂乱的语法和句法剖析。一起运用FPGA技能进步了信息检索的速度，得到了比较满意的成果。
责任编辑：gt
