索引許多文檔以啓用支持AND/OR操作的查詢

我們有很多由單詞組成的文檔。索引文檔的最合適的方法是什麼？搜索查詢應該支持AND/OR操作。索引許多文檔以啓用支持AND/OR操作的查詢

查詢運行時應儘可能高效。請說明索引所需的空間。

這些文檔僅包含單詞（不包括AND/OR），並且查詢包含單詞和關鍵字AND/OR。

編輯：會是什麼算法，如果我將只允許2個關鍵字和操作（例如W1和W2）

2010-07-22 DuduAlul

你打算將每個文檔的文本放到數據庫的一個字段中嗎？ – Leslie 2010-07-22 19:57:27

一般來說是的，但我寧願得到一個RAM解決方案。可以說，我有一個巨大的內存，我喜歡在那裏做所有事情。 – DuduAlul 2010-07-22 20:02:58

所需的基本數據是inverted index。這將每個單詞映射到包含它的一組文檔。假設lookup是一個從單詞到文檔集的函數：lookup: W -> Pos(D)（其中W是集合文字，D集合文檔，Pos(D)集合電子集合D）。

比方說你有以下形式的查詢表達式：

Expr ::= Word | AndExpression | OrExpression 
AndExpression ::= Expr 'AND' Expr 
OrExpression ::= Expr 'OR' Expr

所以，你得到代表查詢抽象語法樹。這是與下列類型的節點樹：

abstract class Expression { } 

class Word extends Expression { 
    String word 
} 

class AndExpression extends Expression { 
    Expression left 
    Expression right 
} 

class OrExpression extends Expression { 
    Expression left 
    Expression right 
}

例如，foo AND (bar OR baz)將被轉換爲樹：

 AndExpression 
    /   \ 
    /    \ 
    Word('foo')   OrExpression 
        /   \ 
       /    \ 
      Word('bar')  Word('baz')

爲了評估這棵樹，遵循這些簡單的規則，表示在僞代碼：

Set<Document> evaluate(Expr e) { 
    if (e is Word) 
     return lookup(e.word) 
    else if (e is AndExpression) 
     return intersection(evaluate(e.left), evaluate(e.right)) 
    else if (e is OrExpression) 
     return union(evaluate(e.left), evaluate(e.right)) 

    //otherwise, throw assertion error: no other case remaining 
} 

//implemented by the inverted index, not shown 
Set<Document> lookup(String word)

因此，AND表達式基本上轉換成設定交叉點，而OR表達式transla用於聯合表達式，所有表達都是遞歸地評估的。我敢肯定，如果你盯上以上，你會看到它的美麗:)

你可以代表每個集合（即lookup返回）作爲一個HashSet。如果你使用Java，你也可以使用番石榴懶惰的union和intersection實現，這應該很有趣（特別是如果你研究代碼或用你的想象力來看看這種情況下'懶惰'的真正含義）。據我所知儘管交叉點很少通過交叉散列表來計算 - 相反，通常會發生的情況如下：假設3個要相交的集合，我們選擇一個（最好是最小的）並分配一個計數器（等於1）給每個文件。然後我們迭代其他集合，遞增每個找到的文檔的計數器。最後，我們報告每個文件的計數器變爲3（這意味着文件出現在所有集合中，因此存在於它們的交集中）。

來源

2010-07-24 20:02:10

Google Desktop彈簧腦海，但所有主要的O/S已經建立了類似的功能在或容易添加。我將Spotlight在我的Mac上使用的空間描述爲「合理」。

來源

2010-07-22 20:20:29

我在尋找的是Google桌面如何工作？ :-) – DuduAlul 2010-07-22 20:36:24

隨着許多文件，像Lucene這樣的專用包變得非常有吸引力。

來源

2010-07-22 20:23:43 Wrikken

我很想看一個算法的描述.. 謝謝！ – DuduAlul 2010-07-22 20:31:51

正如@Wrikken所說，使用lucene。

由於您對使用的算法感興趣，有很多，您可以找到一個起點here和更多信息here。

來源

2010-07-23 01:56:42 Recurse

在情況下，只有2個關鍵字被允許（例如，「KEY1與KEY2」）

這是我發現迄今溶液： 1）的鍵映射，HashMap中，其中鍵是關鍵字和值是文檔鏈接列表。 2）docMap一個HashMap，其中關鍵是文檔ID和值關鍵字

的HashSet的現在，這樣的查詢（「鍵1和鍵2」）我想：

LinkedList docs = keyMap.get(key1); 
for each (HashSet doc:docs) 
    if(doc.contains(keys)) 
      result.add(doc); 
return result

怎麼辦您認爲？有沒有更好的辦法？ 3個關鍵字怎麼樣？

來源

2010-07-24 19:48:02 DuduAlul

我想你會發現我的答案翔實。 – 2010-07-24 20:03:39

索引許多文檔以啓用支持AND/OR操作的查詢

回答

相關問題