一種字符數據的檢索方法
2023-10-08 21:13:29 2
專利名稱：一種字符數據的檢索方法
技術領域：
本發明涉及一種數據檢索技術，尤其是字符類數據的檢索方法。
背景技術：
用戶在進行詞典類數據的查詢操作中，用戶往往出現不能十分確定查詢關鍵字的具體拼寫的情況；或者，用戶需要查詢具有部分相同字符的數據。針對以上兩種情況，可以依據用戶輸入的不確定的字符串，從源數據中查找出一系列與之相似的數據，供用戶參考，同時也支持包括通配符的關鍵字的查找。在關鍵字中加入通配符「？」或「*」以查找所有與之預期相同或者相近的字符數據。其中通配符「？」匹配文件名中的單個字符，而通配符「*」匹配零個或多個字符。例如data？.dat的模式所能查找到的文件包括data1.dat或者dataN.dat；當使用′*′字符代替′？′字符時(即data*.dat的模式)，則會擴大檢索出的文件範圍，則下列名稱的文件將出現在查詢結果中data12222.dat或者data12XF.dat等。
如本領域技術人員所知，關鍵字的查找方法是對源數據中所有數據逐一進行比對。所述源數據通常是保存在磁碟上的單詞索引文件。由於對磁碟操作的速度較慢，並且逐一進行對比的算法較為繁瑣，因而，現有技術不能提供更高的檢索速度。現有技術的一種改進方法是先將磁碟文件中的數據讀入內存，進而在內存中進行字符匹配的操作，但是由於不同檢索應用中的索引文件大小不同，尤其在索引文件較大的情況下，將其全部讀入內存會佔用相當部分的內存空間，進一步由於該改進方法僅改變了匹配操作的環境，而依然沿用了現有技術中較為繁瑣的字符匹配算法，因而所述對現有技術的改進並沒有明顯的提高字符查找的速度。
發明內容
本發明的目的是提供一種字符數據的查找方法，該方法能夠快速的反饋與關鍵字相似的字符數據。
為解決上述技術問題，本發明的目的是通過以下技術方案實現的1)提取源資料庫中字符數據的前兩位字母組合作為索引項建立索引；2)記錄每個索引項所對應的字符數據的存儲地址；3)加載所述索引到內存；以及，4)根據輸入關鍵字的前兩位字母加載該字母組合索引項對應的字符數據到內存；5)遍歷內存中的字符數據，輸出與關鍵字匹配的數據。
在上述方法基礎上，1)中進一步包括建立一位字母組合的索引項，該索引項對應於以該字母為首字母，且前兩位為字母與非字母組合的字符數據；以及，4)之前還包括查找索引中是否有與輸入關鍵字前兩位字符相匹配的索引項，若有則進行4)，否則加載與輸入關鍵字首位字符相匹配的索引項到內存。
上述方法中，3)中進一步將索引保存到哈希表。所述源資料庫中字符數據按字符順序進行排列；則2)具體為記錄確定的索引項所對應第一個字符數據的地址，以及進一步記錄包括確定的索引項所對應字符數據的數量。本發明所述非字母字符包括空格符、數字、分隔符等。
以上技術方案可以看出，本發明是一種字符數據的檢索方法，該方法中，在設計索引文件的時候建立了二級索引，及將所有字符數據最前面的兩個字母作為二級索引項，並記錄每二級索引項所對應單詞的存儲位置；並且，在每次查詞操作的時候僅根據查找關鍵字的前兩位字符加載相應的字符數據到內存，進而在該字符數據的集合範圍內進一步遍歷進行匹配操作等。因而，本發明具有查詞速度快的優點。
進一步，本發明採用哈希表管理二級索引的信息，即在每次程序運行時，將所述二級索引與索引項下字符數據的存儲位置讀入哈希表，以便於之後的查找。每次對源模型的查找只需要對用戶輸入的關鍵字進行分析，剝離出二級索引，再對哈希表進行查找從而找到相對索引項的偏移並將從此偏移開始的單詞集合塊讀入內存從而進行查找和匹配。這樣不僅進一步降低了內存佔有量，也提升了匹配速度。
圖1為二級索引結構圖；圖2為本發明實施例流程圖；圖3為目標模型與源模型匹配流程圖。
具體實施例方式
本發明涉及字符數據的檢索方法。其中包括以下概念。
源數據指所有被搜索的數據。如在電子詞典中，所述源數據即指所有單詞或詞組的集合，這些單詞或詞組通常以名稱為單詞索引的磁碟文件的形式存在。
源模型將用戶輸入的欲查找的字符串稱為源模型(Source Pattern)，亦為搜索關鍵字，源模型中可包括特殊的字符串。數據集中於之比對的字符串成為「目標模型(Target Pattern)」目標模型與用戶所輸入的字符串相似的單詞集合稱為目標模型，目標模型可以理解為依據用戶的輸入，從源數據劃分出的小範圍數據集合。
以下說明本發明的具體實施方式
。本發明優選實施例的核心在於在源數據中建立二級索引，建立二級索引文件，即提取源資料庫中字符數據的前兩位字母組合作為索引項建立索引和建立一位字母組合的索引項，該索引項對應於以該字母為首字母，且前兩位為字母與非字母組合的字符數據；在內存中，採用哈希表保存所述二級索引文件，即所述索引項與其所對應的字符數據的對應關係；以及，查找索引中是否有與輸入關鍵字前兩位字符相匹配的索引項，若有則加載該字母組合索引項對應的字符數據到內存；否則加載與輸入關鍵字首位字符相匹配的索引項到內存；最後，遍歷內存中的字符數據，輸出與關鍵字匹配的數據。
由上可知，本發明的核心之一在於建立二級索引。圖1為本發明二級索引結構圖，參照該圖具體說明二級索引的建立。
本發明所建立的二級索引是將源數據中所有字符數據最前面的兩個字母做成二級索引；以及，進一步建立一位字母的索引項，該一位字母的索引項對應於以該字母為首字母，且前兩位為字母與非字母組合的字符數據。並記錄以下信息二級索引項；該二級索引項所對應源數據中第一個字符數據在索引文件中的偏移(P)；該二級索引項所對應源數據中第一個字符數據在索引文件中的偏移與以下一個二級索引項所對應源數據中的第一個字符數據在索引文件中的偏移之差(Pc)。
將二級索引項、所述字符數據的偏移(P)以及所述偏移之差(Pc)這三個數據組成一個元組(tuple)，附加在索引文件前面，一個元組結構是(二級索引，P，Pc)。
如圖，二級索引項ab的元組結構為ab:323:745，其中以ab開頭的第一個單詞是abacus，這個單詞在索引文件中的偏移是323，其中以ac開頭的第一個單詞是academic，這個單詞在索引文件中的偏移是1068，之差為745，說明以ab開頭的單詞共有745個。進一步如圖1所示，其中二級索引項a的元組結構為a:0:323，該索引項所對應的源數據為以a為首字母的詞組或字符組合，如圖，第一個字符數據為a case in point，該詞組在索引文件中的偏移為0，且索引項a下的最後一個字符數據為A.M.，其偏移為322，則索引項a對應源數據的字符數據數為323。
圖2為本發明實施例流程圖，參照該圖說明本發明的實現方式。
步驟21在現有源數據的索引文件基礎上，創建二級索引，將二級索引和偏移等記錄在元組中，把所有二級索引的元組附加到索引文件前面；所述二級索引的建立方法參照上文說明；步驟22程序啟動後，加載索引文件前面的所有元組數據到內存中，並保存到哈希表中；所述哈希表是一種數據結構，其基本思想是根據當前待查找數據的特徵，以記錄關鍵字為自變量，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。具體的，哈希表根據關鍵值碼直接進行訪問，即通過把關鍵值碼映射到表中一個位置來訪問記錄，以加快查找的速度；所述映射函數叫做哈希函數，例如F(a)＝b，其中F為哈希函數，a表示鍵值，b為返回值。相對於樹型結構、列表結構等數據結構的查找，哈希表的檢索效率較高；本實施例中採用哈希表保存建立的二級索引，每次程序啟動的時候將這些數據讀入哈希表中，每次對源模型的查找只需要對用戶輸入的單詞進行分析，剝離出二級索引再對哈希表進行查找從而找到相對索引的偏移並將從此偏移開始的單詞集合塊讀入內存從而進行查找和匹配，這樣不僅降低的內存佔有量，也提升了匹配速度；步驟23獲取用戶輸入的關鍵字；步驟24取所述關鍵字字符串的前2位字符作為在哈希表中進行查找的關鍵值碼(key)，若字符串為一個字符，則將該字符作為關鍵值碼；步驟25依據關鍵值碼，利用哈希函數返回二級索引的偏移(P)和與上一個二級索引之間的偏移差(Pc)；若步驟24中獲取的兩位字符為字母組合或一個字母，則根據查找哈希表中與之匹配的二級索引項；例如若所查關鍵字為abacus，則返回索引項ab所對應字符數據在索引文件中的偏移以及所述偏移差；若步驟24中獲取的兩位字符為字母和非字母的組合，則經查找發現哈希表中不存在與之匹配的二級索引項，則返回以該關鍵字首字母為二級索引項的偏移(P)以及所述的偏移差(Pc)；例如若待查關鍵字為A.M.，則前兩位字符組合為A.，經查找沒有建立該字符組合的二級索引項，此時應返回索引項a所對應字符數據在索引文件中的偏移即偏移差；若關鍵字前兩位字符組合中包含通配符「？」或「*」，所述通配符「？」和「*」通常被用來和普通字符(如a到z)組合，作為一個字符串進行查找，「？」代表一個字符，「*」代表一串字符；如果通配符在第一位，則通常不具備操作意義，因而忽略；若通配符在第二位，基於通配符的定義，應返回首字母為關鍵字第一位字母的所有二級索引項的所述偏移和偏移差；例如若輸入關鍵字為a？acus，則基於通配符的定義，發現a？與a、ab至az的所有二級索引字符組合均匹配，因而，返回以a為開頭的所有二級索引項的偏移和偏移差；對於通配符*，採用相同的算法操作；
步驟26從索引文件中找到該偏移值所對應的單詞，並從這個單詞開始偏移Pc個的單詞，作為一個數據集合讀到內存中，稱為目標模型；步驟27遍歷目標模型中的每個單詞，分別與用戶輸入的源模型進行比對，返回所有匹配的數據，並進行顯示。
步驟27中所述源模型與目標模型的對比操作分為以下三種情況1)用戶輸入源模型中沒有通配符，順序比較源模型中每個位置的字符是否與目標模型中相同位置的字符都相同，若都相同，則說明匹配成功；2)用戶輸入源模型中含有「？」，首先判斷源模型與目標模型的長度是否相等.如果相等則繼續數據流否則返回，其中若「？」出現在源模型頭部，這種情況一般沒有操作意義，可忽略；若「？」出現在源模型尾部(如abacu？)，則將源模型中′？′之前各個位置的字符與目標模型相同位置的字符逐一順序比較，如果各個位置的比較結果都相同則匹配成功；若「？」出現在源模型中部，則應順序比較源模型中′？′之前的字符，且逆序比較′？′之後的字符，如果都相等則匹配成功；3)用戶輸入源模型中含有′*′，若′*′出現在源模型中部(如ab*s)，則將源模型中′*′前的所有位置的字母與目標模型相應位置的字母順序進行比較，如果相應位置都相同，則進一步將源模型中′*′後的所有字母按照逆序與目標模型進行比較，如果相應位置都相同則匹配成功；若「*」出現在源模型尾部(如ab*)，只需將源模型中「*」之前各個位置的字母與目標模型相同位置的字母逐一順序比較，如果各個位置的比較結果都想同，則匹配成功。
依據以上原則，參照圖3，進一步說明當目標模型被加載到內存後，步驟27中遍歷目標模型，分別與用戶輸入關鍵字(源模型)進行對比的操作。
步驟31分析源模型；步驟32判斷源模型中是否包含通配符；若不包含通配符則進行步驟33；若通配符為「？」，則進行步驟35；若通配符為「*」，則進行步驟310；步驟33判斷源模型的每個字符是否與目標模型中相同位置的字符相同，若相同則進行步驟34，否則結束該次匹配操作；步驟34返回目標模型；步驟35比較源模型核目標模型長度是否相同；若相同則進行步驟36，否則結束此次匹配操作；步驟36返回「？」所在位置；若「？」在源模型第一位，則結束此次匹配操作；若「？」在源模型最後一位，則進行步驟37；否則進行步驟38；步驟37順序比較源模型？之前的每個字符是否與目標模型中相同位置的字符都相同，若相同則進行步驟34，否則結束此次匹配操作；步驟38順序比較源模型？之前的每個字符是否與目標模型中相同位置的字符都相同，若相同，則進行步驟39，否則結束此次匹配操作；步驟39逆序比較源模型？之後的每個字符是否與目標模型中相同位置的字符都相同，若相同，則進行步驟34，否則結束此次匹配操作；步驟310返回「*」所在位置；若「*」在源模型第一位，則結束此次匹配操作；若「*」在源模型最後一位，則進行步驟33；否則進行步驟311；步驟311順序比較源模型*之前的每個字符是否與目標模型中相同位置的字符都相同，若相同則進行步驟312，否則結束此次匹配操作；
步驟312逆序比較源模型*之後的每個字符是否與目標模型中相同位置的字符都相同，若相同則進行步驟34，否則結束此次匹配操作。
以上僅為依據步驟27中所述匹配原則進行的源模型與目標模型匹配的具體實施例。其中部分步驟間的執行順序可進行調整，本文不再贅述。
以上對本發明所提供的一種字符數據的檢索方法進行了詳細介紹，本文中應用了具體個例對本發明的原理及實施方式進行了闡述，以上實施例的說明只是用於幫助理解本發明的方法及其核心思想；同時，對於本領域的一般技術人員，依據本發明的思想，在具體實施方式
及應用範圍上均會有改變之處，綜上所述，本說明書內容不應理解為對本發明的限制。
權利要求
1.一種字符數據檢索方法，其特徵在於1)提取源資料庫中字符數據的前兩位字母組合作為索引項建立索引；2)記錄每個索引項所對應的字符數據的存儲地址；3)加載所述索引到內存；以及，4)根據輸入關鍵字的前兩位字母加載該字母組合索引項對應的字符數據到內存；5)遍歷內存中的字符數據，輸出與關鍵字匹配的數據。
2.如權利要求1所述的字符數據檢索方法，其特徵在於1)中進一步包括建立一位字母組合的索引項，該索引項對應於以該字母為首字母，且前兩位為字母與非字母組合的字符數據；以及，4)之前還包括查找索引中是否有與輸入關鍵字前兩位字符相匹配的索引項，若有則進行4)，否則加載與輸入關鍵字首位字符相匹配的索引項到內存。
3.如權利要求1所述的字符數據檢索方法，其特徵在於3)中進一步將索引保存到哈希表。
4.如權利要求1所述的字符數據檢索方法，其特徵在於源資料庫中字符數據按字符順序進行排列。
5.如權利要求4所述的字符數據檢索方法，其特徵在於2)具體為記錄確定的索引項所對應第一個字符數據的地址。
6.如權利要求5所述的字符數據檢索方法，其特徵在於2)中進一步包括記錄確定的索引項所對應字符數據的數量。
7.如權利要求2所述的字符數據檢索方法，其特徵在於所述非字母字符包括空格符、數字、分隔符。
全文摘要
本發明涉及一種字符數據的檢索方法。包括1)提取源資料庫中字符數據的前兩位字母組合作為索引項建立索引；2)記錄每個索引項所對應的字符數據的存儲地址；3)加載所述索引到內存；以及，4)根據輸入關鍵字的前兩位字母加載該字母組合索引項對應的字符數據到內存；5)遍歷內存中的字符數據，輸出與關鍵字匹配的數據。本發明能夠快速的反饋與關鍵字相似的字符數據，並且不僅降低了內存佔有量，也具有較高的匹配速度。
文檔編號G06F17/30GK1776688SQ20051013181
公開日2006年5月24日 申請日期2005年12月15日 優先權日2005年12月15日
發明者陳亮, 林劍峰 申請人:北京金山軟體有限公司