位標記字符串檢索技術的製作方法
2023-05-31 09:57:21
專利名稱：位標記字符串檢索技術的製作方法
技術領域：
本發明是一種字符串模糊檢索技術，目的是提高資料庫字符串模糊檢索的速度。方法是將組成字符串的基本字符分為m組，並用有m個bit的數據W來標記組成字符串的基本字符信息。如果字符串S的一個基本字符C1屬於第n組，則將數據W自右至左(也可以是自左至右)的第n個bit標記為1，類似地，根據其它基本字符C2、C3、C4…所屬的組對數據W進行標記，標記可以用位的「或」(or)運算進行。完成全部基本字符標記後的數據W，記錄有字符串S的信息，稱為字符串S的「位值」。對字符串Sn的「位值」Wn與待檢索字符串T的「位值」Wt進行位的「和」(and)運算，其結果稱為Wg。如果Wg等於Wt，則「位值」Wn等於或包含Wt。由於不同的字符串可能有相同的位值，在利用「位值」運算對資料庫記錄進行篩選得到初步結果集R1，再用通常的字符逐位比較方式作二次檢索，得出最終的檢索結果集R2。
背景技術：
目前資料庫字符串模糊檢索採用逐位比較方式進行，如判斷字符串bdopfqew中是否包含字符f，計算機以f對字符串bdopfqew從頭至尾進行逐位比較，效率不高。
2004年10月19日，本人申請了「質數代換字符串檢索技術」專利，申請號200410067258.X，該方法有效地提高了字符串模糊檢索的速度，但對於長字符串實施「質數代換字符串檢索」，需要用多個欄位的整數來記錄質數乘積，對存貯空間需求較多。為了提高字符串模糊檢索的速度，並減少對存貯空間的需求，本發明提出用若干個位(bit)來標記字符串的組成信息，對資料庫完成標記後，利用位的「和」運算對記錄作初步篩選，在初步結果中再利用逐位比較方式檢索出最終結果。
發明內容
本發明是一種字符串模糊檢索技術，方法是將組成字符串的基本字符分為m組，並用有m個bit的數據W來標記組成字符串的基本字符信息。其過程有二，一利用位的「或」運算對字符串進行標記；二，利用位的「和」運算進行檢索，下面說明實現原理 收入GBK範圍的21000個漢字及其它符號，均有內碼，根據內碼將全部漢字及其它符號分為31組，對於第n組賦與值2n-1。從二進位來看，每組在自右至左的第n個bit上為1，而其餘bit為0，稱之為「基本位值」。組數值基本位值110000000000000000000000000000000122000000000000000000000000000000103400000000000000000000000000000100480000000000000000000000000000100051600000000000000000000000000010000632000000000000000000000000001000007640000000000000000000000000100000081280000000000000000000000001000000092560000000000000000000000010000000010512000000000000000000000010000000001110240000000000000000000001000000000012204800000000000000000000100000000000134096000000000000000000010000000000001481920000000000000000001000000000000015163840000000000000000010000000000000016327680000000000000000100000000000000017655360000000000000001000000000000000018131072000000000000001000000000000000001926214400000000000001000000000000000000205242880000000000001000000000000000000021104857600000000000100000000000000000000222097152000000000010000000000000000000002341943040000000001000000000000000000000024838860800000000100000000000000000000000 25167772160000000100000000000000000000000026335544320000001000000000000000000000000027671088640000010000000000000000000000000028134217728000010000000000000000000000000002926843545600010000000000000000000000000000305368709120010000000000000000000000000000031107374182401000000000000000000000000000000 設有字符串「大漠孤煙直長河落日圓」，則漢字內碼組數值基本位值大22823812800000000000000000000000010000000漠2844822209715200000000001000000000000000000000孤2339623419430400000000010000000000000000000000煙288954800000000000000000000000000001000直3045211102400000000000000000000010000000000長27265176553600000000000000010000000000000000河2782721104857600000000000100000000000000000000落316832200000000000000000000000000000010日26085151638400000000000000000100000000000000圓22278211048576000000000001000000000000000000008471690 整個字符串的位值742311400000000011100010100010010001010 對「大、漠、孤、煙、直、長、河、落、日、圓」十個字符的位值做「或」(or)運算，可以得到整個字符串的「位值」00000000011100010100010010001010。
另一個方面，字符串「大漠孤煙直長河落日圓」的總值為8471690，去除「河」與「圓」的一個重複值1048576，淨值為7423114。它與00000000011100010100010010001010是對應的。
用此種方法可以得到任何字符串的「位值」，「白雲千載空悠悠」的「位值」為00100010000001001010000000010000。
而「長河落日」的「位值」是00000000000100010100000000000010。
判斷字符串Sn的「位值」Wn是否包含或等於T的「位值」Wt，只要對字符串的「位值」Wn及T的「位值」Wt作「和」(and)運算，結果Wg如果等於Wt，則Wn包含或等於Wt，進一步說，字符串Sn可能包含或等於T。即 Wg＝Wn and Wt 如Wg＝Wt 則Wn包含或等於Wt， 而Sn可能包含或等於T。
大漠孤煙直長河落日圓S1 白雲千載空悠悠S2 00000000011100010100010010001010W1 00100010000001001010000000010000W2 00000000000100010100000000000010Wt 00000000000100010100000000000010Wt 長河落日T 00000000000100010100000000000010Wg1 00000000000000000000000000000000Wg2 ″and″值 從上述可見，「河」與「圓」的「基本位值」相同，而不同字符串「位值」相同是存在的。位標記字符串檢索的目的是利用位運算對資料庫中的字符串做初步檢索得到R1，在結果中用通常的逐位比較法進行二次檢索，得到最終結果R2。位的「和」運算遠比字符逐位比較快，實施中，為了提高檢索速度，應儘量降低R1，使之接近R2，減少二次檢索所用時間。
幾點說明 1.設字符串平均長度為L，資料庫記錄條數為R，待檢索字符串長度為l，標記所用位數為m，則初步檢索結果集R1的條數可以用下式粗略估算 R 1 = ( L * R ) m ! / ( 1 ! * ( m - 1 ) ! ) 此式未考慮字符串標記位值的概率分布問題，故不準確，但大體說明了幾個參數對R1的影響。
設有一個300萬條記錄的書名資料庫，字符串平均長度為16，用31個bit標記，用戶所用檢索關鍵詞長為4，則 R 1 = ( 16 * 3,000,000 ) 31 ! / ( 4 ! * ( 31 - 4 ) ! ) = 1526 可見對於一般漢字語詞、書名、地名、單位名來說，用一個長整數的32個bit中符號位之外的31個bit可以有效地對字符串進行標記。
對於字符串平均長度更長，記錄條數更多的資料庫，在sql SEVER 2000中，可以採用數據類型bigint的63個bit進行標記，相應地，對基本字符分為63組，當然對於32位處理器，用bigint必然在Wn與Wt進行位的「和」運算及比較Wg與Wt是否相等用更多時間，是否採用應作對比測試。實際上，任何資料庫中便於進行位的「或」與「和」運算的任何數據類型均可以用來標記字符串，如果獨立編程構造無正負符號位的專用數據類型自然更佳。
3.對於絕大多數為雙字符的漢語語詞資料庫，可考慮用兩個bit為1的基本位值進行標記，分漢字為31！/(2！*(31-2)！)組，即465組。但如此一來，一個雙字符語詞的「位值」通常4個bit為1，可解析為4！/(2！*(4-2)！)，即6個漢字。如果用戶用一個漢字檢索，10萬條語詞的資料庫，則 R 1 = ( 2 * 100,000 ) * 6 465 = 2580 R 1 = ( 2 * 100,000 ) 31 = 6452 可見採用兩個bit為1的基本位值進行標記性能略有改善，但此種方法適用範圍有限。也就是說，待檢索字符串長度為1個字符時，位標記字符串檢索方法性能次於質數代換字符串檢索方法。
4.基本字符對於漢語通常是漢字，當然檢索漢字時，可以是基本編旁。對於漢語拼音來說，可以是字母、聲母、韻母、音節。對於其它語言來說，可以是字母、音節、單詞等。
5.標記所用數據類型除考慮程式語言、資料庫等軟體因素之外，尚應考慮cpu的位數。對於64位cpu，應優先考慮採用64位bit來標記字符串，以充分利用cpu的性能，提高「位值」的離散度。
4.基本字符的分組，如能實現字頻均衡，則性能自然最優，用漢字內碼進行模運算以分組，相對容易實現而已，不是最優分組。
具體實施例方式 本發明在漢語詞彙、詞組、短語、書名等資料庫字符串模糊檢索中已得到良好的實現，下面以sql SERVER2000構建資料庫，以vb6.0為程式語言，作具體說明，其它程式語言及其它資料庫的字符串模糊檢索可參照實施。
1.建立資料庫 設資料庫shuku有表biao，其中有欄位shuming，數據類型為nvarchar，長度為40。另建立欄位wei，數據類型為「長整型」，也就是4個字節，有32個bit，其中一位為正負數符號，其餘31個bit可以利用。
2利用位的「或」運算對資料庫字符串作「標記」 dim shuzu(30)As Long『定義一個31個元素的長整型數組。shuzu(0)＝1For x＝1 To 30shuzu(x)＝2*shuzu(x-1)Next『對長整型數組的31個元素賦值，從1、2、4、8、16至1073741824，從二進位來看，有一位bit為1，而其餘bit為0，也就是「基本位值」。Dim biaostr As String當前處理的字符串Dim weizhi As Long存貯字符串的位值Dim weizhilin As Long存貯一個字符的基本位值Dim x As Integerbiaors.MoveFirst<!-- SIPO -->『移至資料庫記錄集biaors的第一個記錄Doweizhilin＝0weizhi＝0With biaorsbiaostr＝.Fields(″shuming″)End With『讀入一個記錄之字符串，賦與字符串變量biaostrFor x＝1 To Len(biaostr)index＝Abs(AscW(Mid(biaostr，x，1))Mod 31)『從字符串變量biaostr中取一個字符，並將該字符內碼，以31為模作運算，再取絕對值，並賦與index，也就是對基本字符進行分組。weizhilin＝shuzu(index)『將數組shuzu(index)值賦與weizhilin，是1、2、4、8、16至1073741824之一。weizhi＝weizhi Or weizhilin『將一個字符的「基本位值」weizhilin值與weizhi作位的「或」運算。Next『循環結束，獲得當前字符串的「位值」weizhiWith biaors.Fields(″wei″)＝weizhiEnd Withbiaors.Update『將「位值」weizhi存貯進當前記錄的欄位weibiaors.MoveNext『處理下一個記錄Loop While Not biaors.EOF 3.利用位的「和」運算進行資料庫字符串模糊檢索 Dim shuzu(30)As Longshuzu(0)＝1For x＝1 To 30shuzu(x)＝2*shuzu(x-1)Next<!-- SIPO -->『定義一個31個元素的長整型數組，賦值從1、2、4、8、16至1073741824，與「標記」之數組完成一致。Dim weizhi As Long『存貯一個字符串的位值Dim weizhilin As Long『存貯一個字符的位值Dim textstr As String『存貯當前檢索字符串Dim xAs Integerweizhilin＝0weizhi＝0textstr＝Text1.Text『Text1.Text為待檢索字符串For x＝1 To Len(biaostr)index＝Abs(AscW(Mid(textstr，x，1))Mod 31)weizhilin＝shuzu(index)weizhi＝weizhi Or weiztilinNext『獲得待檢索字符串的「位值」weizhi，方法與資料庫字符串「標記」方法一致。strQuery＝″select*from(SELECT*FROM biao WHERE(wei″weizhi″)＝″weizhi″)DERIVEDTBL WHERE(shuming like′％″textstr″％′)″『將待檢索字符串的「位值」與資料庫各記錄的「位值」作「和」(and)運算，作初步檢索，再以通常字符串模糊檢索方式作二次檢索，得到最終結果。這是sql SERVER2000的查詢語句，其它資料庫可能略有不同。Adodc 1.RecordSource＝strQueryAdodc 1.Refresh『執行檢索DataList1.ListField＝″shuming″<!-- SIPO -->DataList1.ReFill『在列表框中顯示當前檢索結果。
權利要求
1.一種字符串模糊檢索技術，其特徵在於將組成字符串的基本字符分為m組，並用有m個bit的數據W來標記組成字符串的基本字符信息。如果字符串S的一個基本字符C1屬於第n組，則將數據W自右至左(或自左至右)的第n個bit標記為1，類似地，根據其它基本字符C2、C3、C4…所屬的組對數據W進行標記，完成全部基本字符標記後的數據W，記錄有字符串S的信息，稱為字符串S的「位值」。對字符串Sn的「位值」Wn與待檢索字符串T的「位值」Wt進行比較，如果Wn等於或包含Wt，則字符串Sn可能等於或包含字符串T，從而實現字符串的模糊檢索。
2.按照權利要求1所述的方法，其特徵在於標記可以先給各組基本字符賦與相應的第n個bit為1而其餘bit為0的「基本位值」，對一個字符串的全部基本字符的「基本位值」進行位的「或」(or)運算，得到一個字符串的「位值」。
3.按照權利要求1所述的方法，其特徵在於比較兩個「位值」是否有包含關係，可用位的「和」(and)運算進行。對字符串Sn的「位值」Wn與字符串T的「位值，，Wt進行位的「和」(and)運算，結果稱為Wg，如果Wg等於Wt，則Wn等於或包含Wt。
4.按照權利要求1所述的方法，其特徵在於由於不同的字符串可能有相同的「位值」，故利用「位值」運算對資料庫記錄進行篩選得到初步結果R1，再用通常的字符逐位比較方式作二次檢索，得出最終的檢索結果R2。
5.按照權利要求1所述的方法，其特徵在於對於一般語詞、詞組、專有名詞資料庫來說，用一個長整數的32個bit中符號位之外的31個bit可以有效地對字符串進行標記。對於字符串平均長度比較大的資料庫，在sql SEVER 2000中，可以用數據類型bigint的63個bit進行標記，相應地，基本字符則應分為63組。任何資料庫中能進行位的「或」與「和」運算的任何數據類型均可以用來標記字符串，如獨立編程構造無正負符號位的專用數據類型則更佳。
6.按照權利要求1及5所述的方法，其特徵在於標記所用bit的位數，除考慮字符串平均長度外，同時應考慮當前資料庫記錄的條數，記錄條數多的資料庫應用更多位bit來進行標記，相應地，基本字符則應分為更多組。
7.按照權利要求1、5及6所述的方法，其特徵在於標記所用數據類型除考慮程式語言、資料庫等軟體因素之外，尚應考慮cpu的位數。對於64位cpu，應優先考慮採用64位bit來標記字符串，以充分利用cpu的性能，提高「位值」的離散度。
8.按照權利要求1所述的方法，其特徵在於基本字符對於漢語通常是漢字，檢索漢字時，可以是基本編旁；對於漢語拼音來說，可以是字母、聲母、韻母、音節；對於其它語言來說，可以是字母、音節、單詞等。
9.按照權利要求1所述的方法，其特徵在於對基本字符進行分組，每一組的基本字符數目不必相等，應力求在該語言或當前資料庫中各組基本字符字頻之和趨於均衡，尤其是高頻基本字符應均衡分配於各組，以使性能最優。
10.按照權利要求1所述的方法，其特徵在於對於絕大多數為雙字符的漢語語詞資料庫，可用兩個bit為1的基本位值進行標記，分漢字為31～/(2！*(31-2)！)組，即465組，以改進性能。
全文摘要
本發明是一種字符串模糊檢索技術，方法是將組成字符串的基本字符分為m組，並用有m個bit的數據W來標記組成字符串的基本字符信息。如果字符串S的一個基本字符C1屬於第n組，則將數據W自右至左(也可以是自左至右)的第n個bit標記為1，類似地，根據其它基本字符C2、C3、C4…所屬的組對數據W進行標記，標記可以用位的「或」(or)運算進行。完成全部基本字符標記後的數據W，記錄有字符串S的信息，稱為字符串S的「位值」。用一個長整數的32個bit中符號位之外的31個bit可以對一般資料庫字符串有效地進行標記。對於記錄條數很多、字符串平均長度比較長的資料庫，可以用bit位數更多的數據類型進行標記。對字符串Sn的「位值」Wn與待檢索字符串T的「位值」Wt進行位的「和」(and)運算，其結果稱為Wg。如果Wg等於Wt，則「位值」Wn等於或包含Wt。由於不同的字符串可能有相同的位值，在利用「位值」運算對資料庫記錄進行篩選得到初步結果集R1，再用通常的字符逐位比較方式作二次檢索，得出最終的檢索結果集R2。
文檔編號G06F17/30GK1645374SQ20051002338
公開日2005年7月27日 申請日期2005年1月17日 優先權日2005年1月17日
發明者徐文新 申請人:徐文新