[發明專利]一種基于樹形結構的檢索方法

有效

• 申請號: 201510818902.0
• 申請日: 2015-11-20
• 公開（公告）號: CN105404677B
• 公開（公告）日: 2018-12-18
• 發明（設計）人: 陳虹宇;羅陽;苗寧
• 申請（專利權）人: 四川神琥科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京天奇智新知識產權代理有限公司 11340
• 代理人: 郭霞

1.一種基于樹形結構的檢索方法，用于中文搜索引擎中對中文網頁數據的處理，包括：

步驟S100，網頁數據預處理；

步驟S200，建立網頁數據索引文件；

步驟S300,接收用戶輸入的查詢字符串，根據網頁數據索引進行檢索；

其中，步驟S200中的所述網頁數據索引文件是對處理后的網頁數據所建立的網頁數據索引組成的文件；所述網頁數據索引是基于二元內相關后續樹創建的索引；

所述二元內相關后續樹定義如下：

(1)后續：對文本T中的字符串a1a2來說，a2稱為a1的后續，文本T最后一個字符的后續稱為結束符，用“#”來表示；文本中總會有相同的字符出現，具體來說就是有相同的字或詞，如果某一個索引項a出現了k次，a不是文本的結尾，那么a有k個后續，記作a[s]，s＝1，2，…，k；

(2)一元后續表達式與一元后續樹：假設全文T是由字符串a1，a2，…，an，#組成的，如果其中的ai1＝ai2＝…＝aik是相同的字符，記為a，而ai1+1，ai2+1，…，aik+1分別是它們的后續，則所有的a和它的后續就構成了一個一元后續表達式a(ai1+1,ai2+1,…,aik+1)，用一棵樹來描述此表達式，a是樹根，ai1+1，ai2+1，…，aik+1是它的后續結點，這棵樹就是a的一元后續樹；

(3)二元后續表達式與二元后續樹：對一元后續表達式進行擴展，如果原文T中有相同的字符串ai1ai1+1＝ai2ai2+1＝…＝aikaik+1，記作ab，則所有的ab和其后續就構成了一個二元后續表達式，記作a(b(ai1+2,ai2+2,…,aik+2))；

(4)a的二元后續樹表示為：a是樹根，ai1+1，ai2+1，…，aik+1是a的后續，(ai1+1,tag1)，(ai2+1,tag2)，…，(aik+1,tagk)則作為a的后續結點，其中，tag1，tag2…，tagk分為是以ai1+1，ai2+1，…，aik+1為根的一元后續樹中ai1+1，ai2+1，…，aik+1的后續所在分支的序號；

(5)內相關后續樹的定義：由一個源文檔庫中全部文檔的所有索引項的后續樹組成的森林，叫做這個源文檔庫的內相關后續樹，當所述后續樹為二元后續樹時，該內相關后續樹為二元內相關后續樹。

2.如權利要求1所述的基于樹形結構的檢索方法，其中，所述網頁數據索引為字索引。

3.如權利要求1所述的基于樹形結構的檢索方法，其中，所述網頁數據索引為詞索引。

4.如權利要求1所述的基于樹形結構的檢索方法，其中，所述網頁數據索引為字索引和詞索引。

5.如權利要求1所述的基于樹形結構的檢索方法，其中，步驟S100進一步包括：

首先對抓取的原始網頁進行分類，然后再按照分類分別提取網頁中的文本信息，得到分類后的文本信息；生成網頁索引文件的過程包括為原始網頁的每個分類分別建立網頁索引文件。

6.如權利要求5所述的基于樹形結構的檢索方法，其中，在步驟S200中，建立網頁數據索引文件進一步包括：

首先，判斷每個分類的文本信息的容量，當所述分類的容量小于1GB時，為所述分類的文本信息建立字索引，當所述分類的容量大于等于1GB時，為所述分類的文本信息建立詞索引。

7.如權利要求6所述的基于樹形結構的檢索方法，進一步包括：

將查詢字符串分別分解為字和詞，對于網頁數據索引是字索引的情況，按字根據所述字索引來進行檢索；對于網頁數據索引是詞索引的情況，按分詞根據所述詞索引來進行檢索。

8.如權利要求7所述的基于樹形結構的檢索方法，具體的檢索過程為：

第一階段，針對網頁數據索引是字索引的情況進行檢索；

首先順序讀入查詢字符串分解后的每一個字，取第一個字A，針對字索引，在二元內相關后續樹中找到以A為根的樹，然后在樹A的葉子中逐個分支地匹配查詢字符串的下一個字B，匹配到B的話則將B的后續編號加入隊列，直到A的全部分支都匹配結束；轉到以B為根的樹，從隊列中取出B樹的分支號，查找相應的葉子結點來匹配字符串中的下一個字C，如此循環直到有一次匹配過程中沒有匹配到或者查詢字符串全部匹配結束，如果匹配成功，則意味著找到了包含查詢字符串的原文；

第二階段，針對網頁數據索引是詞索引的情況進行檢索；

首先順序讀入查詢字符串分解后的每一個詞，取第一個詞A，針對詞索引，在二元內相關后續樹中找到以A為根的樹，然后在樹A的葉子中逐個分支地匹配查詢字符串的下一個詞B，匹配到B的話則將B的后續編號加入隊列，直到A的全部分支都匹配結束；轉到以B為根的樹，從隊列中取出B樹的分支號，查找相應的葉子結點來匹配字符串中的下一個詞C，如此循環直到有一次匹配過程中沒有匹配到或者查詢字符串全部匹配結束，如果匹配成功，則意味著找到了包含查詢字符串的原文。