2010-04-17 136 views
4

如果我們想要在倒排索引結構中搜索像這樣的「t1 t2 t3」(t1,t2,t3必須排隊)查詢,我們應該採用哪種方式?如何在倒排索引結構中搜索短語查詢?

1-首先我們搜索「t1」項並找到所有包含「t1」的文檔,然後對「t2」和「t3」執行此項工作。然後找到文件「t1」,「t2」和「t3」的位置彼此相鄰。

2-首先我們搜索「t1」項並找到所有包含「t1」的文檔,然後在我們找到的所有文檔中,我們搜索「t2」,然後在這個結果中找到文檔包含「t3」。

我有一個完整的倒排索引。我想知道上面的哪些方法是優化的,(1)或(2)?

非常感謝。

回答

4

由於wikipedia入口井解釋,

還有的 倒排索引兩個主要變量:a 創紀錄的水平 倒排索引(或倒排文件索引 或只是倒排文件)包含對每個 單詞的引用文件列表 。甲字電平倒排索引(或 全倒排索引倒排列表) 另外含有的 文檔內的每個字的位置。 後一種形式提供更多功能 (如詞組搜索),但需要更多 時間和空間才能創建。

既然你不告訴我們你有哪個變種,我們不能真正回答你的問題,但考慮每一種可能性會有所幫助。

要打開和搜索文檔通常是一個代價高昂的操作,除非您的文檔非常小,所以您希望將其最小化 - 而選項(2)並沒有真正將其最小化。如果你有一個倒列表,帶選項(1),你甚至不需要打開任何文件;如果您只有倒排文件,您將不可避免地需要打開文檔並對其進行掃描(因爲您無法確認文字鄰接關係) - 但至少在選項(1)中,您可以最大限度地減少文檔數量打開並掃描(僅包含包含每個單詞的文檔列表的交集)。

因此,無論哪種情況,選項(1)都更有前途(除非您的文檔特別小)。