一種用於中文字符串匹配的位向量方法
2023-06-19 18:06:06
專利名稱：一種用於中文字符串匹配的位向量方法
技術領域：
本發明涉及一種用於字符串匹配的位向量方法。
背景技術：
模糊字符串匹配在入侵檢測、移動短消息過濾、文本編輯、信息查詢、自動索引、計算生物學、信息提取等領域均有重要應用，已經成為計算機算法設計的一個重要課題。它解決的問題是給定一個字符串，一個模式串，要找出字符串中所有與模式串相似的部分。
解決模糊字符串匹配的經典方法是一種基於生成動態矩陣的方法，自從1980年P.Sellers發表該方法以來，許多人對之進行了改進。這些改進當中，有一種非常有效的方法就是位向量方法。
當今計算機中，整數字長一般為32或64，因此，可將32或64次的比特運算用一次整數運算來完成，從而將運算速度提高32或64倍。位向量方法正是利用了這一點，在模式串長度小於整數字長的情況下，提高了字符串匹配的性能。
現有位向量方法位向量方法適用於，它用到一個與字符集等長的整數數組，這樣每個字符都有一個整數與之相對應。位向量方法的描述如下1)將漢字用兩個字節來表示；2)把這兩個字節合起來作為一個16比特的大整數來處理，所以，每個漢字都對應一個大整數，對應所有漢字的整數構成一個數組；3)將該數組所有整數清為0；4)從頭到尾掃描整個模式串，對其中的每個字符，做如下操作設該字符在模式串中所處位置為p，將該字符對應的整數的第p個比特置1；5)用正在處理字符串中的字符在整數數組中對應的整數進行匹配。
漢字都是用兩個字節表示的。在GB2312中，對每個漢字對應的兩個字節做了明確規定。比如，「陳晨的爸爸」所包含的4個漢字對應的兩個字節分別是(以下是16進位)陳B3 C2晨B3 BF的B5 C4爸B0 D6所以，「陳晨的爸爸」在計算機中就是B3 C2 B3 BF B5 C4 B0 D6 B0 D6
現有位向量方法把這兩個字節合起來作為一個16比特的大整數(0～65535)來處理，所以，每個漢字都對應一個大整數，比如「陳」＝B3C2＝46018「晨」＝B3BF＝46015「的」＝B5C4＝46532「爸」＝B0D6＝45270這樣，要把中文字符串轉化成位向量，就需要長達65536的一個數組M。
因為需要一個和字符集等長的整數數組，而漢字有10000多個，因此，當應用於中文字符匹配時，需要10000整數的空間。如果整數由4個字節組成，則需要40K字節的空間。
在國外，由於拉丁文屬於小字符集，這個問題不明顯。但若考慮的是中文字符串的匹配，因漢字多於1萬個，所需空間也在40K字節以上，這個問題顯得比較突出。
發明內容
本發明要解決的技術問題是為了克服了現有位向量方法在應用於中文時需要大量空間的缺點，提出了一種新的位向量方法。
在計算機中，一個漢字用兩個字節來表示，在本文中稱為低字節和高字節。本方法用到兩個長為256的整數數組，稱為低字節數組和高字節數組。這樣，每個漢字的低字節都和低字節數組中的一個整數對應，高字節也和高字節數組中的一個整數對應。
本發明的新位向量方法為，對在計算機中用兩個字節表示的漢字(1)將兩個字節分別對應一個高字節整數和一個低字節整數進行處理，所有漢字對應的高字節整數和低字節整數分別構成一個高字節數組和低字節數組；(2)將低字節數組和高字節數組中的所有整數全部清為0；(3)從頭到尾掃描整個中文模式串，對其中的每個漢字做如下操作，設某漢字在中文模式串中所處位置為p，則首先，將該漢字的低字節對應的低字節數組中的整數的第p比特置1；其次，將該漢字的高字節對應的高字節數組中的整數的第p比特置1；(4)用正在處理字符串中的字符在兩個整數數組中對應的整數進行匹配。
本位向量方法只需要兩個長為256的整數數組，如果整數是4個字節，共需2K字節空間，是原有位向量方法的5％。
與原有位向量方法相比，由於採取了將漢字的兩個字節分別處理的技術措施，大大減少了所需的空間。
圖1為本發明中的對字符串處理的流程圖；
圖2是字符串「陳晨的爸爸」經原有位向量方法處理後對應的整數數組。
圖3是字符串「陳晨的爸爸」經本發明的位向量方法處理後對應的兩個整數數組。
具體實施例方式
在本發明中，把漢字作為兩個小整數(0～255)來處理。一個漢字對應一個高字節整數、一個低字節整數。以「陳晨的爸爸」為例「陳」高字節整數＝B3＝179，低字節整數C2＝194「晨」高字節整數＝B3＝179，低字節整數BF＝191「的」高字節整數＝B5＝181，低字節整數C4＝196「爸」高字節整數＝B0＝176，低字節整數D6＝214這樣，要把中文字符串轉化成位向量，只需要兩個長為256的數組HM、LM(見圖3)。
設有中文字符串p，和兩個長為256的整數數組LM，HM。本位向量方法可以這樣實現 NewPreprocess(p，LM，HM) Begin For i＝1 to 256 Do Begin LM[i]＝0； HM[i]＝0； End For i＝1 to m Do Begin LM[low(pi)](i)＝1； HM[high(pi)](i)＝1； End End其中，low(pi)表示p中第i個字符的低位字節。
圖2給出了字符串「陳晨的爸爸」經原有位向量方法處理的結果。
圖3中給出了字符串「陳晨的爸爸」經本位向量方法處理的結果。可以看到，「陳」對應的兩個整數的與為「00011」「00001」＝」00001」。即「陳」在計算機中為「B3C2」，用本發明的位向量方法處理後，高字節B3對應「00011」，低字節C2對應「00001」，這兩個數進行逐位與操作，得到「00001」。而「00001」就是「陳」用現有技術中的位向量方法處理後得到的結果。二者結果一致。
同樣地，
「晨」對應的是「00011」「00010」＝「00010」。
「的」對應的是「00100」「00100」＝「00100」。
「爸」對應的是「11000」「11000」＝「11000」。
對比附圖2，說明兩種方法的效果是完全一樣的。
下面對圖2和圖3中的部分對應關係進行說明。
在圖2中，「陳」＝B3C2(16進位)＝46018(10進位)。
「陳」在字符串「陳晨的爸爸」裡是第一個字符，所以第一個比特為1，其他為0。
「晨」＝B3BF(16進位)＝46015(10進位)，對應「00010」，是因為「陳」在字符串「陳晨的爸爸」裡是第二個字符，所以第二個比特為1，其他為0。
又如，「爸」＝B0D6(16進位)＝45270(10進位)，對應「11000」，是因為「爸」在字符串「陳晨的爸爸」裡是第四、五個字符，所以第四、五個比特為1，其他為0。
在圖3中，C2在LM中對應「00001」，等價於說字符串「陳晨的爸爸」的第一個字符的低字節為C2；B0在HM中對應「11000」，等價於說字符串「陳晨的爸爸」的第四、五個字符的高字節為B0；B3在HM中對應「00011」，等價於說字符串「陳晨的爸爸」的第一、二個字符的高字節為B3；
權利要求
1.一種用於中文字符串匹配的位向量方法，對在計算機中用兩個字節表示的漢字(1)將兩個字節分別對應一個高字節整數和一個低字節整數進行處理，所有漢字對應的高字節整數和低字節整數分別構成一個高字節數組和低字節數組；(2)將低字節數組和高字節數組中的所有整數全部清為0；(3)從頭到尾掃描整個中文模式串，對其中的每個漢字做如下操作，設某漢字在中文模式串中所處位置為p，則首先，將該漢字的低字節對應的低字節數組中的整數的第p比特置1；其次，將該漢字的高字節對應的高字節數組中的整數的第p比特置1；(4)用正在處理字符串中的字符在兩個整數數組中對應的整數進行匹配。
全文摘要
一種用於中文字符串匹配的位向量方法，對在計算機中用兩個字節表示的漢字將兩個字節分別對應一個高字節整數和一個低字節整數進行處理，所有漢字對應的高字節整數和低字節整數分別構成一個高字節數組和低字節數組；將兩個字節數組中的所有整數全部清為0；掃描整個中文模式串，對其中的每個漢字做如下操作，設某漢字在中文模式串中所處位置為p，則將該漢字的低字節對應的低字節數組中的整數的第p比特置1並將該漢字的高字節對應的高字節數組中的整數的第p比特置1；用正在處理字符串中的字符在兩個整數數組中對應的整數進行匹配。由於採取了將漢字的兩個字節分別處理的技術措施，大大減少了所需的空間。
文檔編號G06F9/45GK1542614SQ03113380
公開日2004年11月3日 申請日期2003年5月1日 優先權日2003年5月1日
發明者陳開渠, 趙潔, 彭志威 申請人:中興通訊股份有限公司