倒排索引建立方法

2023-06-22 12:11:46 4

專利名稱：倒排索引建立方法
技術領域：
本發明涉及信息檢索領域，特別涉及一種倒排索引建立方法。
背景技術：
隨著計算機、網際網路的發展，人類的知識越來越多地以數位化形式存儲。如何在海 量的數位化文本中，快速、準確的檢索人們想要的知識成為急迫的需求。1945年，Varmevar
Bush的論文《就像我們可能會想的......》第一次提出了設計自動的、在大規模的存儲數
據中進行查找的機器的構想。這被認為是現代信息檢索技術的開山之作。進入50年代後， 研究者們開始為逐步的實現這些設想而努力。50年代中期，在利用電腦對文本數據進行檢 索的研究上，研究者取得了一些成果。其中最有代表性的是Luhn在IBM公司的工作(請見 參考文獻 1「H. P. Luhn，「A statistical approach tomechanized encoding and searching of literary information」，IBM Journal ofResearch and Development, vol. 1(4)， PP. 309-317，1957」)，他提出了利用詞對文檔構建索引並利用檢索使用的關鍵詞與文檔中 詞的匹配程度進行檢索的方法，這種方法就是目前常用的倒排索引技術的雛形。所謂的倒排索引(Inverted index)也常被稱為反向索引、置入檔案或反向檔案， 是一種常用的索引方法，它被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中 的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。在現有技術中一種已知的實 現方式中，倒排索引可以被看成一個鍊表數組，每個鍊表的表頭包含關鍵詞，其後續單元則 包括所有包含這個關鍵詞的文檔標號以及一些其他信息。這些信息可以是文檔中該詞的頻 率，也可以是文檔中該詞的位置等信息。這樣在檢索時可以直接利用各個鍊表表頭的關鍵 詞來查找包含這些關鍵詞的文檔，而無需對所有的文檔逐個進行基於關鍵詞的檢索，有利 於提高檢索的效率。Google等知名的搜尋引擎公司多數都採用了倒排索引方法來實現信息 的檢索。現有技術中，倒排索引的建立過程通常包含以下幾個步驟步驟1)、文檔解析。將不同的文檔存儲格式轉換為統一的字符串形式。現在的文 檔格式特別多，如PDF格式、HTML格式、TXT格式、DOC格式等，文檔解析步驟的任務是讀取 文檔文件，轉換為統一的字符串格式。步驟2)、關鍵詞提取。這個步驟主要完成包括中文分詞、去除停用詞、大小寫轉換、 時態還原等操作。步驟3)、建立、存儲倒排索引。將關鍵詞、文章號、關鍵詞的出現位置加入到前面所 述的倒排索引數據結構中，將倒排索引數據結構存儲到資料庫或文件等持久化設備中。現有技術中的倒排索引為根據詞找到文檔提供了快速檢索途徑，但是它的匹配過 程是精確匹配，只有包含檢索詞的文檔才能被搜索到，這在很多場合往往是不夠的。例如， 在企業和政府部門的文本信息搜索應用中，經常會有類似這樣的需求輸入某個人的姓名， 不僅要找到包含該人名的所有文檔，還希望知道和這個人相關的電話號碼、郵箱等信息。顯 然，在搜尋引擎上輸入「電話號碼」這個詞，只能找到含有「電話號碼」這個詞的所有文檔，而找不到只含有用數字表示的電話號碼卻沒出現「電話號碼」這個詞的文檔。本領域技術人員雖然已經認識到了倒排索引技術所存在的上述缺陷，但所提出的 解決方案通常具有實現效率很低的缺陷。如現有技術中對前述問題的一種典型解決方法 是找到包含該人名的所有文檔後，再通過信息抽取系統對搜索到的文檔的全文進行解析， 抽取出所需的電話號碼、郵箱等。這個方法最大的問題是每次搜索都要再對被搜索到的文 檔進行一次信息抽取，當文檔數量巨大，搜索次數很多時，時間開銷顯然讓人無法接受。

發明內容
本發明的目的是克服現有技術無法通過倒排索引方法直接查找某一類型數據的 缺陷，從而提供一種新的倒排索引創建方法。為了實現上述目的，本發明提供了一種倒排索引建立方法，所述倒排索引包括抽 取結果表，所述抽取結果表包括文檔號以及與該文檔號相對應的抽取結果記錄，所述抽取 結果記錄包括有類型、內容以及位置信息項；該方法包括步驟1)、對由字符串格式表示的文檔做分詞操作，從所述分詞操作結果中取出一 個詞；步驟2)、判斷所取出的詞是否屬於某一類型的數據，如果屬於，則執行下一步，否 則，執行步驟4)；步驟3)、將所提取出來的詞的內容、在所在文檔中的位置以及判斷該詞是否屬於 某一類型的數據時所採用的檢測方法分別填入所述抽取結果記錄中的內容、位置以及類型 信息項，創建抽取結果表，然後執行下一步；步驟4)、為所取出的詞建立通用的倒排索引表。上述技術方案中，在所述的步驟2)中，採用正則表達式檢測所取出的詞是否屬於 某一類型的數據。上述技術方案中，所述的某一類型的數據包括行動電話號碼、固定電話號碼、身份 證號碼、電子郵箱地址中的一種。上述技術方案中，在所述的步驟2)中，採用命名實體識別的方法檢測所取出的詞 是否屬於某一類型的數據；其中，所述命名實體識別的方法包括基於規則的方法、基於統計 的方法、基於詞庫的方法中的一種。上述技術方案中，所述的某一類型的數據包括人名、公司名、地址中的一種。本發明還提供了一種利用所建立的倒排索引實現搜索的方法，包括步驟1)、利用關鍵詞在倒排索引表中做查找，得到包含有該關鍵詞的文檔的文檔 號；步驟2)、根據所述文檔號從抽取結果表中找出相關文檔的抽取結果並顯示。本發明的優點在於本發明的倒排索引創建方法所創建的倒排索引能夠查找類型數據，避免了現有技 術在查找類型數據時所花費的額外開銷。


圖1為本發明的倒排索引建立方法的流程圖2為本發明中所涉及的抽取結果表的示意圖；圖3為利用本發明所創建的倒排索引實現搜索的方法的流程圖。
具體實施例方式下面結合附圖和具體實施方式
對本發明加以說明。在本發明中，除了要從文檔中提取關鍵詞，並為關鍵詞建立倒排索引外，還能夠根 據需要從文檔中抽取出相關信息並存儲。使得用戶在搜索時，通過關鍵詞可以直接找到抽 取出來的相關信息，無需再對原始文檔進行解析，從而提高搜索時的時間效率。下面以通訊 信息為例，對建立包含有通訊信息的倒排索引的過程加以說明。與現有技術相同，在建立倒排索引的過程中，首先要解析文檔，將不同的文檔存儲 格式轉換為統一的字符串形式。如將PDF格式、HTML格式、TXT格式、DOC格式中的任意一 種轉換為統一的字符串格式。該步驟中的轉換操作與現有技術並無二致，因此不在此處做 重複說明。在將文檔轉換為統一的字符串格式後，下面就要從文檔中提取關鍵詞。與現有技 術中所涉及的關鍵詞的概念不同的是，在本發明中，關鍵詞這一概念所包含的範圍更為廣 泛。本發明中的關鍵詞除了現有技術中常見的特定字符數據外(如若干個確定的漢字或字 母)，還可以包括某種類型的數據，如固定電話號碼、行動電話號碼、電子郵箱、身份證號碼 等。對這些內容不同但類型相同的數據的提取採用現有技術中的文本匹配的方法已經無法 實現，因此需要採用一些特殊的技術手段。同種類型的數據一般來說都有一些共同的特點，例如，如果都是行動電話號碼，那 麼這些數據應該都是由數字組成，並且具有相同的位數，又如，如果都是電子郵箱，那麼在 數據中應當包含@字符。因此，在本實施例中可以設定一些特殊字符來做初步提取，然後 再通過能夠對規則加以描述的正則表達式來實現詳細的提取過程。基於上述原因，參考圖 1，本發明在得到用字符串格式描述的文檔後，首先對該文檔做分詞操作，從分詞後的結果 中取出一個詞，然後判斷所取出的詞中是否包含有特殊字符，如果有特殊字符，那麼就可以 採用與該特殊字符相對應的正則表達式做匹配操作，將成功匹配的結果提取出來，如果不 含有特殊字符或者正則表達式匹配不成功，則按照現有技術中的關鍵詞提取方法提取關鍵 詞。下面以行動電話號碼為例，對上述過程加以說明。由於不同用戶的行動電話號碼的數 字組合存在差異，因此，除非已經知道行動電話號碼的具體內容，否則很難依靠現有的關鍵 詞提取方法從文檔中找出所有屬於行動電話號碼類型的數據。在本實施例中，採用正則表 達式來實現對行動電話號碼類型數據的提取。例如，中國大陸地區的行動電話號碼的正則 表達式如下(15 [13567890] \d {8} 13 [13567890] \d {8})。那麼在關鍵詞提取過程中，在分 詞後，判斷從分詞結果中所取出的一個詞內是否有數字，如果有數字，就採用上述的正則表 達式對該詞做匹配操作，將成功匹配的結果提取出來。上文以從文檔中提取行動電話號碼類型的數據為例，對關鍵詞提取的有關操作做 了說明。在實際應用中，還可以以同樣的方法實現對包括固定電話號碼、身份證號碼、電子 郵箱在內的多種類型的數據的提取，只是在提取這些類型的數據的時候，對該類型數據的 識別方法可能會有一定的變動(如所採用的特殊字符的具體內容會有所不同)，另外，所採 用的正則表達式也會有所不同。下面給出了固定電話號碼、行動電話號碼、電子郵箱、身份證號碼等類型的數據各自所對應的正則表達式。本領域技術人員應當了解，根據實際需要
還可以提取其它類型的數據，而其它類型數據也會有各自對應的正則表達式。
權利要求
1.一種倒排索引建立方法，所述倒排索引包括抽取結果表，所述抽取結果表包括文檔 號以及與該文檔號相對應的抽取結果記錄，所述抽取結果記錄包括有類型、內容以及位置 信息項；該方法包括步驟1)、對由字符串格式表示的文檔做分詞操作，從所述分詞操作結果中取出一個詞；步驟2)、判斷所取出的詞是否屬於某一類型的數據，如果屬於，則執行下一步，否則，執 行步驟4)；步驟3)、將所提取出來的詞的內容、在所在文檔中的位置以及判斷該詞是否屬於某一 類型的數據時所採用的檢測方法分別填入所述抽取結果記錄中的內容、位置以及類型信息 項，創建抽取結果表，然後執行下一步；步驟4)、為所取出的詞建立通用的倒排索引表。
2.根據權利要求1所述的倒排索引建立方法，其特徵在於，在所述的步驟2)中，採用正 則表達式檢測所取出的詞是否屬於某一類型的數據。
3.根據權利要求2所述的倒排索引建立方法，其特徵在於，所述的某一類型的數據包 括行動電話號碼、固定電話號碼、身份證號碼、電子郵箱地址中的一種。
4.根據權利要求1所述的倒排索引建立方法，其特徵在於，在所述的步驟2)中，採用命 名實體識別的方法檢測所取出的詞是否屬於某一類型的數據；其中，所述命名實體識別的 方法包括基於規則的方法、基於統計的方法、基於詞庫的方法中的一種。
5.根據權利要求4所述的倒排索引建立方法，其特徵在於，所述的某一類型的數據包 括人名、公司名、地址中的一種。
6.一種利用權利要求1-5之一所建立的倒排索引實現搜索的方法，包括步驟1)、利用關鍵詞在倒排索引表中做查找，得到包含有該關鍵詞的文檔的文檔號； 步驟2)、根據所述文檔號從抽取結果表中找出相關文檔的抽取結果並顯示。
全文摘要
本發明提供一種倒排索引建立方法，所述倒排索引包括抽取結果表，所述抽取結果表包括文檔號以及與該文檔號相對應的抽取結果記錄，所述抽取結果記錄包括有類型、內容以及位置信息項；該方法包括對由字符串格式表示的文檔做分詞操作，從所述分詞操作結果中取出一個詞；判斷所取出的詞是否屬於某一類型的數據，如果屬於，則執行下一步，否則，為所取出的詞建立通用的倒排索引表後結束操作；將所提取出來的詞的內容、在所在文檔中的位置以及判斷該詞是否屬於某一類型的數據時所採用的檢測方法分別填入所述抽取結果記錄中的內容、位置以及類型信息項，創建抽取結果表，然後為所取出的詞建立通用的倒排索引表。
文檔編號G06F17/30GK102110123SQ20091026070
公開日2011年6月29日 申請日期2009年12月29日 優先權日2009年12月29日
發明者單大甫, 吳泉源, 周斌, 崔凱, 李愛平, 楊樹強, 梁政, 蔣子海, 賈焰, 鄒鵬, 韓偉紅, 韓毅, 黃九鳴 申請人:中國人民解放軍國防科學技術大學