1、 引言

信息檢索是自動(dòng)識(shí)別和分類(lèi)文字信息的過(guò)程，它的目的是從文檔中提取出與用戶(hù)請(qǐng)求相關(guān)的信息 。文檔的基本單位是詞，詞在文檔里出現(xiàn)的次數(shù)（以下稱(chēng)之為頻率）是衡量詞本身重要性的一個(gè)指標(biāo) 。而詞在一條語(yǔ)句里的出現(xiàn)次數(shù)（以下稱(chēng)之為密度）則決定了這條語(yǔ)句的重要性。所以說(shuō)語(yǔ)句的重要性由構(gòu)成語(yǔ)句的詞的出現(xiàn)頻率以及該詞在語(yǔ)句里的密度這兩個(gè)因素決定?；谶@種邏輯我們可以使用關(guān)鍵詞的頻率和密度來(lái)標(biāo)示文檔里的重要語(yǔ)句，從而將文檔內(nèi)容進(jìn)行分類(lèi)，避免語(yǔ)言學(xué)里復(fù)雜的語(yǔ)法和句法分析，同時(shí)還能得到相對(duì)準(zhǔn)確的結(jié)果。在實(shí)際操作中，出現(xiàn)頻率極高和極低的詞將被忽略，因?yàn)檫@些詞往往與文檔的內(nèi)容關(guān)系不大。通過(guò)去除一些預(yù)定義的高頻詞和同義詞將顯著降低信息檢索的工作量，之后得到的關(guān)鍵詞列表則可以用來(lái)識(shí)別重要的語(yǔ)句。這些語(yǔ)句很有可能包含了和文檔內(nèi)容最密切相關(guān)的信息，所以這些語(yǔ)句將被用來(lái)與用戶(hù)輸入的請(qǐng)求作比較，作為檢索結(jié)果返回給用戶(hù)。這種信息檢索方法的核心是計(jì)算每個(gè)關(guān)鍵詞在文檔里的出現(xiàn)次數(shù)，并根據(jù)各個(gè)詞的重要性對(duì)詞列表進(jìn)行排序。本文第二部分將介紹一種硬件哈希算法來(lái)加速關(guān)鍵詞的計(jì)數(shù)工作，而排序則將作為后續(xù)工作進(jìn)行研究。

2 、方法描述

在計(jì)算關(guān)鍵詞在文檔里出現(xiàn)次數(shù)的過(guò)程中，需要一種存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)相關(guān)信息，這種存儲(chǔ)結(jié)構(gòu)必須易于執(zhí)行查找、插入及刪除操作。哈希是一種以常數(shù)平均時(shí)間執(zhí)行查找、插入和刪除操作的算法。在計(jì)算關(guān)鍵詞在文檔里的出現(xiàn)次數(shù)時(shí)應(yīng)用哈希算法可以大大降低查找次數(shù) 。理想的哈希表數(shù)據(jù)結(jié)構(gòu)是一個(gè)包含有關(guān)鍵字的具有固定大小的數(shù)組。一般情況下一個(gè)關(guān)鍵字就是帶有相關(guān)值（關(guān)鍵詞及其在文檔里的出現(xiàn)次數(shù)）的字符串。假設(shè)哈希表的大小為T(mén)ableSize，則每個(gè)關(guān)鍵字被映射到從0到TableSize-1這個(gè)范圍內(nèi)的某個(gè)數(shù)，并且被存放到對(duì)應(yīng)的存儲(chǔ)空間。這個(gè)映射稱(chēng)之為哈希函數(shù)，理想情況下哈希函數(shù)應(yīng)該計(jì)算簡(jiǎn)單并且應(yīng)該保證兩個(gè)不同的關(guān)鍵字映射到不同的單元，不過(guò)由于單元的數(shù)目是有限的，而關(guān)鍵字一般情況下是遠(yuǎn)遠(yuǎn)大于單元數(shù)目的，所以?xún)蓚€(gè)關(guān)鍵字有可能哈希到同一個(gè)單元，這種情況稱(chēng)之為沖突。因此我們需要尋找一個(gè)哈希函數(shù)，該函數(shù)要在單元之間均勻的分配關(guān)鍵字，盡可能的將沖突發(fā)生的概率降到最低。

圖1 硬件哈希結(jié)構(gòu)

如圖1（a）所示，首先將文檔轉(zhuǎn)換為一個(gè)關(guān)鍵詞的列表，之后這個(gè)列表將通過(guò)哈希函數(shù)映射到哈希表數(shù)據(jù)結(jié)構(gòu)中。每個(gè)關(guān)鍵詞都將通過(guò)哈希函數(shù)映射到哈希表中的一個(gè)單元，如果該單元已經(jīng)有內(nèi)容，則比較該內(nèi)容與輸入的關(guān)鍵詞是否相同，相同則“出現(xiàn)次數(shù)”增加一次；不同則為沖突，沖突解決方案將在后面介紹；如果該單元沒(méi)有內(nèi)容則說(shuō)明輸入的關(guān)鍵詞是第一次出現(xiàn)，則將該關(guān)鍵詞存儲(chǔ)在這個(gè)單元，“出現(xiàn)次數(shù)”計(jì)為一次。哈希函數(shù)通過(guò)FPGA硬件來(lái)實(shí)現(xiàn)，為了有效利用FPGA的硬件資源，選用按位異或并與素?cái)?shù)相乘的哈希算法。在實(shí)際操作中這個(gè)算法將被用來(lái)作為第一級(jí)的哈希函數(shù)，產(chǎn)生初始哈希表地址，因?yàn)殛P(guān)鍵詞是一個(gè)可變長(zhǎng)度的字符串，不能直接存儲(chǔ)在哈希表里，取而代之的是一個(gè)指針（如圖1（b）所示）。這個(gè)指針指向存儲(chǔ)器堆里的一塊存儲(chǔ)區(qū)，關(guān)鍵詞及其出現(xiàn)次數(shù)存儲(chǔ)在這塊存儲(chǔ)區(qū)內(nèi)。為了標(biāo)示指針指向的存儲(chǔ)區(qū)是否有內(nèi)容，哈希表中除了存儲(chǔ)指針之外還需要存儲(chǔ)指針指向的存儲(chǔ)區(qū)的狀態(tài)。這些工作由一個(gè)硬件堆存儲(chǔ)控制器來(lái)管理 。輸入的關(guān)鍵詞首先通過(guò)第一級(jí)哈希函數(shù)映射到哈希表中的狀態(tài)指示和指針，如果狀態(tài)指示為有內(nèi)容，則通過(guò)指針得到其指向的存儲(chǔ)內(nèi)容，與輸入關(guān)鍵詞比較，相同則“出現(xiàn)次數(shù)”增加一次，不同則通過(guò)沖突解決方案處理；如果狀態(tài)指示為無(wú)內(nèi)容，則說(shuō)明輸入的關(guān)鍵詞是第一次出現(xiàn)，該關(guān)鍵詞將被存儲(chǔ)到這塊存儲(chǔ)區(qū)，“出現(xiàn)次數(shù)”計(jì)為一次。為了將比較運(yùn)算的時(shí)間降到最小，數(shù)據(jù)寬度需要盡可能寬一些，從而允許多個(gè)字符的比較并行完成。

沖突解決方案的實(shí)質(zhì)是將發(fā)生沖突的數(shù)據(jù)存儲(chǔ)在一個(gè)保留區(qū)域。通常的沖突解決方案分為兩種：鏈表法和開(kāi)放尋址法。鏈表法將所有映射到同一地址的關(guān)鍵字放在一個(gè)動(dòng)態(tài)分配的鏈表里。由于給鏈表里新的關(guān)鍵字分配空間需要時(shí)間，從而導(dǎo)致這種方案的速度相對(duì)較慢，而且算法實(shí)際上還需要實(shí)現(xiàn)另一種數(shù)據(jù)結(jié)構(gòu)（鏈表），因此并不適合在信息檢索里使用。本文采用的是開(kāi)放尋址法來(lái)解決沖突。開(kāi)放尋址法的數(shù)據(jù)和保留區(qū)域在一個(gè)表里，使用偽隨機(jī)探測(cè)法，允許每個(gè)循環(huán)產(chǎn)生一個(gè)新的探測(cè)地址。開(kāi)放尋址法的一個(gè)缺點(diǎn)在于當(dāng)哈希表里的條目增加的時(shí)候沖突的次數(shù)和搜索路徑的長(zhǎng)度也隨著增加，從而導(dǎo)致平均檢索時(shí)間的增加。因此，它的性能由表密度而不是列表長(zhǎng)度決定，而表的大小則依賴(lài)于應(yīng)用數(shù)據(jù)和期望的性能。

3、 硬件實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果

本文的硬件結(jié)構(gòu)基于Xilinx Virtex-II FPGA，其最高頻率為127.47MHz，F(xiàn)PGA資源利用率為392/5120 = 7.6%。文檔存儲(chǔ)使用1片128M x 72位的SDRAM，哈希表存儲(chǔ)使用2片1M x 36位的ZBT（零總線(xiàn)翻轉(zhuǎn)）SRAM。本文第二部分描述的算法通過(guò)一個(gè)5級(jí)流水線(xiàn) 來(lái)實(shí)現(xiàn)，如圖2所示。每級(jí)需要的時(shí)鐘周期的數(shù)目在圖2（a）中給出，其中N為搜索關(guān)鍵字的字符數(shù)，括號(hào)內(nèi)為至少需要的時(shí)鐘周期數(shù)目。為了最優(yōu)化性能，3個(gè)主流水線(xiàn)是重疊的，如圖2（b）所示。

圖2 處理過(guò)程流水線(xiàn)

將這種結(jié)構(gòu)的性能與軟件實(shí)現(xiàn)做一下比較，比較結(jié)果見(jiàn)表1，使用的測(cè)試數(shù)據(jù)集是一樣的。

4、 結(jié)論

本文描述了一種基于FPGA的硬件哈希算法，該算法用來(lái)加速信息檢索過(guò)程中的關(guān)鍵詞計(jì)數(shù)工作，實(shí)驗(yàn)結(jié)果表明，使用FPGA硬件哈希算法在提高信息檢索速度方面明顯優(yōu)于高主頻處理器上的軟件實(shí)現(xiàn)。

本文作者創(chuàng)新點(diǎn)：本文通過(guò)使用關(guān)鍵詞出現(xiàn)的頻率和密度來(lái)標(biāo)示文檔里的重要語(yǔ)句，從而將文檔內(nèi)容進(jìn)行分類(lèi)，避免了語(yǔ)言學(xué)里復(fù)雜的語(yǔ)法和句法分析。同時(shí)利用FPGA技術(shù)提高了信息檢索的速度，得到了比較滿(mǎn)意的結(jié)果。

責(zé)任編輯：gt