資訊檢索：布爾檢索-建立倒排索引(2)
- 2019 年 11 月 21 日
- 筆記
倒排索引
倒排索引用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。假定我們有3個文檔：
doc1 = ["1", "hello", "word", "i", "love", "dazhu"] doc2 = ["2", "hi", "i", "can", "speak", "love"] doc3 = ["3", "can", "i", "say", "hello", "make", "dazhu", "hi"]
將文檔中的單詞做為index，出現的文檔號做為內容。比如：
hello -> [1,3]
代表hello出現在文檔 1,3之中。 為每個單詞都進行類似處理，最終獲得的結果，就叫倒排索引。左邊的所有單詞項，稱之為詞典，而每個詞典項（如'hello'），指向一個倒排記錄表（如[1,3]）
建立過程
通過以下的步驟，可以為文檔集建立倒排索引
獲取每個文檔的單詞表（程式碼 give_word_list）
以doc1為例，經過處理，獲得了如下單詞表：
['dazhu', '1'] ['hello', '1'] ['i', '1'] ['love', '1'] ['word', '1']
後面的數字代表文檔編號。例如['dazhu', '1']代表doc1包含dazhu這個辭彙。
合併單詞表並排序(程式碼 give_index)
同理，處理doc2和doc3,合併所有結果並排序，可得一個如下的列表：
['can', '2'] ['can', '3'] ['dazhu', '1'] ['dazhu', '3'] ['hello', '1'] ......
合併重複詞典項（程式碼 merge_index）
由上可見，很多單詞同時出現在不同的文檔，所以這個列表的詞典項有重複。因為已經進行排序，可以用簡單的演算法將相同詞典項合併。 最終得到結果如下：
['can', ['2', '3']] ['dazhu', ['1', '3']] ['hello', ['1', '3']] ['hi', ['2', '3']] ['i', ['1', '2', '3']] ......
倒排索引至此已完全建立。
搜索
依照前文，我們已經可以求兩個集合的交集並集，有了倒排索引，就能進行布爾查詢。 例如，要求文檔集中包含"i"和"can"的文檔號。可進行如下操作： 1. 取出 i 的倒排記錄表：['1', '2', '3'] 2. 取出 can 的倒排記錄表：['2', '3'] 3. 對這兩個集合求交集 4. 得返回值[2,3]
參考程式碼
import and_or def give_word_list(doc): result = [] for word_index in range(1,len(doc)): result.append([doc[word_index], doc[0]]) result.sort() return result def give_index(*docs): result = [] for doc in docs: word_list = give_word_list(doc) result += word_list result.sort(key=lambda x:x[0]) return result def merge_index(index_unmerge): result = [] temp_key = "" for item in index_unmerge: if item[0] != temp_key: result.append([item[0], [item[1]]]) temp_key = item[0] else: ## merge last item last_item = result[len(result) - 1] last_item[1].append(item[1]) return result def get_doclist_form_index(word, index): for item in index: if item[0] == word: return item[1] return [] doc1 = ["1", "hello", "word", "i", "love", "dazhu"] doc2 = ["2", "hi", "i", "can", "speak", "love"] doc3 = ["3", "can", "i", "say", "hello", "make", "dazhu", "hi"] index_unmerge = give_index(doc1, doc2, doc3) final_map = merge_index(index_unmerge) ## search doc include "i" "can" doclist_1 = get_doclist_form_index("i", final_map) doclist_2 = get_doclist_form_index("can", final_map) result = and_or.arr_and(doclist_1, doclist_2) print(result)
