[發(fā)明專(zhuān)利]信息檢索裝置以及信息檢索方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200810213007.6
• 申請(qǐng)日: 2008-08-20
• 公開(kāi)（公告）號(hào): CN101414976A
• 公開(kāi)（公告）日: 2009-04-22
• 發(fā)明（設(shè)計(jì)）人: 上原輝昭
• 申請(qǐng)（專(zhuān)利權(quán)）人: 沖電氣工業(yè)株式會(huì)社
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56;G06F17/30
• 代理公司: 北京三友知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 黃綸偉

技術(shù)領(lǐng)域

本發(fā)明涉及信息檢索裝置以及信息檢索方法。

背景技術(shù)

例如，圖14所示的在因特網(wǎng)中進(jìn)行分組數(shù)據(jù)中繼的路由器(Router，路線(xiàn)程序)10’進(jìn)行著高速的表檢索。作為該表檢索的例子，說(shuō)明一下NAPT(Network?Address?Port?Translation：網(wǎng)絡(luò)地址端口轉(zhuǎn)換)處理。

NAPT處理是在路由器10’所進(jìn)行的處理中，對(duì)連接因特網(wǎng)時(shí)的專(zhuān)用IP(即本地IP)和全局IP(Global?IP)進(jìn)行轉(zhuǎn)換的處理。通過(guò)該處理，多個(gè)PC(個(gè)人計(jì)算機(jī))可以使用1個(gè)全局IP同時(shí)連接因特網(wǎng)。以下示出結(jié)構(gòu)。

通過(guò)路由器10’內(nèi)的NAPT，將(1)的IP分組的源地址從“本地IP：20”變更為“自身IP：220”。在作為針對(duì)(1)的分組的回復(fù)的(3)的分組中，將發(fā)送目的地地址從“自身IP：220”變更為“本地IP：20”。

由此，可以使多個(gè)PC使用1個(gè)全局IP。

因?yàn)樵撎幚硇枰诟咚傧逻M(jìn)行，而且由于表大小超過(guò)1000，所以提出了使用散列函數(shù)的裝置。

圖15示出使用一般的散列函數(shù)的表檢索裝置的框圖的一個(gè)例子。

此處，主表RAM(Main?Table?RAM)34’中具有NAPT數(shù)據(jù)。

指針表RAM(Pointer?Table?RAM)24’中具有主表RAM?34’的地址。

動(dòng)作情況如下。

輸入NAPT數(shù)據(jù)時(shí)

(1)在地址轉(zhuǎn)換部22’中將成為檢索鑰匙的檢索關(guān)鍵數(shù)據(jù)輸入到散列函數(shù)，得到散列值。

(2)將散列值作為指針表RAM?24’的地址，讀取指針表RAM?24’，如果為空則將下一個(gè)指針生成器(NexPointGen)30’所生成的值插入該地址。如果不為空則使散列值加1后進(jìn)行(2)的處理。

(3)將下一個(gè)指針生成器30’所生成的值作為主表RAM?34’的地址而輸入NAPT數(shù)據(jù)。(然后加上下一個(gè)指針)

讀取NAPT數(shù)據(jù)時(shí)

(1)將檢索關(guān)鍵數(shù)據(jù)輸入到散列函數(shù)，獲得散列值。

(2)將散列值作為指針表RAM?24’的地址，讀取指針表RAM?24’。

(3)將讀取的值作為主表RAM?34’的地址，讀取主表RAM?34’。

(4)如果讀取的值是與檢索關(guān)鍵數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)則結(jié)束。

如果不是與檢索關(guān)鍵數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)，則使散列值加1后進(jìn)行(2)的處理。

刪除NAPT數(shù)據(jù)時(shí)

(1)將檢索關(guān)鍵數(shù)據(jù)輸入到散列函數(shù)，獲得散列值。

(2)將散列值作為指針表RAM?24’的地址，讀取指針表RAM?24’。

(3)將讀取的值作為主表RAM?34’的地址，讀取主表RAM?34’。

(4)如果讀取的值是與檢索關(guān)鍵數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)，則刪除散列值為地址的指針表RAM?24’的數(shù)據(jù)及該指針表RAM?24’的內(nèi)容為地址的主表RAM?34’的數(shù)據(jù)。

如果讀取的值不是與檢索關(guān)鍵數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)，則使散列值加1后進(jìn)行(2)的處理。

當(dāng)進(jìn)行NAPT處理的情況下，由于檢索關(guān)鍵數(shù)據(jù)與對(duì)應(yīng)于檢索關(guān)鍵數(shù)據(jù)的數(shù)據(jù)1對(duì)1地對(duì)應(yīng)起來(lái)，因而可以毫無(wú)問(wèn)題地實(shí)現(xiàn)使用了散列的表檢索方式。

并且，作為與本發(fā)明相關(guān)的技術(shù)，在專(zhuān)利文獻(xiàn)1中公開(kāi)了可以對(duì)使用通配符輸入的關(guān)鍵詞檢索和輸出近似的標(biāo)識(shí)符的標(biāo)識(shí)符檢索裝置。

專(zhuān)利文獻(xiàn)1：日本特開(kāi)平9-223154號(hào)公報(bào)

然而，有時(shí)需要進(jìn)行所輸入的檢索關(guān)鍵數(shù)據(jù)是否屬于特定范圍的范圍檢索。例如，在路由器10’中，在按照IP過(guò)濾器處理那樣輸入的IP地址在特定范圍的情況下，有時(shí)不進(jìn)行數(shù)據(jù)中繼等。

但是，在需要進(jìn)行按照IP過(guò)濾器處理那樣輸入的檢索關(guān)鍵數(shù)據(jù)是否屬于特定范圍的范圍檢索的情況下，無(wú)法使用應(yīng)用了散列的表檢索方式。

換言之，散列檢索雖然可進(jìn)行高速檢索，但因?yàn)榛旧蠈儆?對(duì)1的檢索，所以存在無(wú)法適用于使用通配符(具有某種范圍的特殊字符)的檢索的問(wèn)題。

并且，專(zhuān)利文獻(xiàn)1的技術(shù)是用于從表內(nèi)進(jìn)行采用通配符(例如“^*”)的檢索的技術(shù)，在技術(shù)上應(yīng)用的情形不同。另外，在專(zhuān)利文獻(xiàn)1的技術(shù)中，例如進(jìn)行了檢索ab^*xy的情況下，檢索結(jié)果從ab1xy、ab22xy到ab333xy，連不需要的數(shù)據(jù)也進(jìn)行了檢索，處理也變得復(fù)雜。

發(fā)明內(nèi)容

鑒于上述情況，本發(fā)明的目的在于提供一種信息檢索裝置以及信息檢索方法，其可以判定使用散列函數(shù)輸入的檢索關(guān)鍵數(shù)據(jù)是否為特定范圍內(nèi)的數(shù)據(jù)。