帶有不需要的字的文檔檢索

我正在構建一個數據結構，該數據結構有助於索引總長度爲n的S文檔的集合，以便它支持以下查詢：給定兩個單詞P1和P2，count所有包含P1但不是P2。我希望答案是完整的（不要錯過結果）。帶有不需要的字的文檔檢索

我已經構建了一個通用後綴樹，並選取每個sqrt（n）葉節點及其祖先（並刪除每一個childed節點）。對於每個內部節點v，我預先計算針對節點u的查詢的答案。

但是，如果查詢包含在節點v和u的樹中出現的單詞，我可以在O（1）中得到答案，但是當單詞不在其中一個節點時，我可以做什麼我們挑選的？通過保留一個O（n ）數據結構並進行預處理，併爲O（1）時間檢索準備好所有可能的答案，但我的目標是將此數據結構構建在O（n）空間並使查詢儘可能高效。

來源

2012-06-19 Adi Sherf

聽起來像inverted index仍然會對你有用。它是包含它們的文檔的有序列表上的文字地圖。這些文檔需要有一個共同的總體排序，並且它們按照它們出現在每個單詞桶中的順序排列。

假設你n在字語料庫的總長度出現（而不是詞彙尺寸），可以在時間O(n log n)和線性空間構成。

鑑於P1和P2，您進行了兩個單獨的查詢以分別獲取包含兩個詞的文檔。由於這兩個列表都有一個共同的排序，你可以做一個線性的合併類算法只選擇那些含有P1文件，但不P2：

c1 <- cursor to first element of list of docs containing P1 
c2 <- cursor to first element of list of docs containing P2 
results <- [] # our return value 

while c1 not exhausted 
    if c2 exhausted or *c1 < *c2 
    results.append(c1++) 
    else if *c1 == *c2 
    c1++ 
    c2++ 
    else # *c1 > *c2 
    c2++ 

return results

通知循環迭代至少一個光標的每通;它在兩個初始查詢的大小總和中以線性時間運行。由於只有來自c1光標的東西輸入results，我們知道所有結果都包含P1。最後，請注意，我們總是隻提前輸入「滯後」遊標：這個（以及整個文檔排序）可以保證，如果一個文檔出現在兩個初始查詢中，將會有一個循環迭代，其中兩個遊標都指向該文檔。當這種迭代發生時，中間條款必然會啓動並且通過推進兩個遊標來跳過文檔。因此，包含P2必然的文檔不會將添加到results。

此查詢是一個稱爲布爾查詢的常規類的示例;可以將此算法擴展到大多數布爾表達式。某些查詢打破了算法的效率（迫使它遍歷整個詞彙空間），但基本上只要你不否定每個詞（即不要求not P1 and not P2），你就沒問題。請參閱this進行深入處理。

來源

2012-06-20 07:04:41 phs

帶有不需要的字的文檔檢索

回答

相關問題