動態搜索和顯示

Question

我有大量的文檔，文本文件，我想搜索相關內容。我見過一個搜索工具，不能記住它在哪裏，實現了一個好方法，正如我在下面的要求中描述的那樣。

我的要求是如下：

• 我需要一個優化的搜索功能：我提供此搜索功能與列表（一個或多個）部分完成的（或全部）與空格分隔單詞。
• 然後函數找到包含單詞開始或等於第一個單詞的所有文檔，然後使用第二個單詞以相同的方式搜索這些找到的文檔，依此類推，最後返回一個包含實際找到與包含它們的文檔（名稱爲&位置）鏈接的單詞，以獲得完整的單詞列表。
• 該文件必須包含全部列表中的文字。
• 我想用這個函數做一個你自己的類型搜索，這樣我就可以實時地以樹狀結構顯示和更新結果。

一種可能的方法來解決我想出如下： 我創建了一個數據庫（最有可能用mysql）三個用表：「文件」，「詞」和「Word_Docs」。

• '文件' 將所有文件（idDoc，名稱，位置）。
• '單詞'將具有（idWord，Word），並且是來自所有文檔的唯一單詞列表（特定單詞只出現一次）。
• 「Word_Docs」將具有（idWord，idDoc），和是的唯一id組合對每個字的列表，並記錄它出現英寸

該函數然後用編輯框上的內容稱爲每個按鍵（除了空間）：

• 字符串標記化
• （這裏我的車輪旋轉了一下）：我相信一個SQL語句可以構造返回所需的數據集：（actual_words，DOC_NAME， doc_location）; （我不是SQL的熱門號碼），或者是爲每個令牌調用一系列調用並解析非重複的idDocs？然後
• 此數據集（/列表/陣列），然後返回

顯示返回的列表含量：

例如：調用： 「SEQ STA鱈魚」 顯示：

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt] 
     - stop - code - Counting Sequences [file://docs/sample/con_seq.txt] 
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc] 

（某某上）

這是做這件事的最佳方法是什麼？該功能需要很快，還是隻有在空間被擊中時才能被調用？ 它應該提供字完成？ （在數據庫中有詞）至少這將防止對不存在的詞進行無用的對函數的調用。 如果字完成：那將如何實現？

（也許是這樣也可以使用這種類型的搜索解決方案瀏覽標籤（在主頁的右上角）？）

Answer 1

你正在談論的內容被稱爲inverted index或發佈列表，並且與您提出的建議以及Mecki提出的建議類似。有很多關於倒排索引的文獻，維基百科的文章是一個很好的開始。

更好的是，不要試圖自己構建它，而應使用現有的倒排索引實現。 MySQL和最新版本的PostgreSQL默認都有全文索引。您可能還想查看Lucene以獲得獨立的解決方案。有很多的東西寫好倒排索引，包括斷詞，詞幹，多字查詢，等，等來考慮，而預建的解決方案將做這一切爲您服務。

Answer 2

不能確定的語法（這是SQL Server的語法），但是：

-- N is the number of elements in the list 

SELECT idDoc, COUNT(1) 
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord 
WHERE w.Word IN ('word1', ..., 'wordN') 
GROUP BY wd.idDoc 
HAVING COUNT(1) = N 

也就是說，沒有使用like。與類似的事情更復雜。

Answer 3

最快的方法當然不會使用數據庫，因爲如果您使用優化數據手動執行搜索，則可以輕鬆擊敗選擇的搜索性能。假定文檔不經常更改，最快的方法是構建索引文件並使用它們來查找關鍵字。該指數文件創建這樣的：

1. 查找文本文件中的所有獨特單詞。即將文本文件按空格拆分爲單詞，並將每個單詞添加到列表中，除非已在列表中找到該單詞。

2. 把你找到的所有單詞按字母順序排序;最快的方法是使用Three Way Radix QuickSort。在對字符串進行排序時，該算法在性能上難以勝任。

3. 將排序後的列表寫入磁盤，每行一個字。

4. 如果您現在要搜索文檔文件，請將其完全忽略，而是將索引文件加載到內存中，並使用二進制搜索來查找索引文件中是否存在單詞。搜索大型排序列表時，二進制搜索很難被擊敗。

或者，您可以在單個步驟中合併步驟（1）和步驟（2）。如果您使用InsertionSort（使用二進制搜索來查找正確的插入位置以將新元素插入到已排序的列表中），則不僅可以使用快速算法來查明該單詞是否已在列表中，以防萬一它不是，你馬上得到正確的位置插入它，如果你總是插入新的，你會在步驟（3）時自動獲得一個排序列表。

問題是，當文檔發生變化時，您需要更新索引...但是，數據庫解決方案也不會這樣嗎？另一方面，數據庫解決方案爲您帶來了一些優勢：即使文檔包含如此多的單詞，您也可以使用它，索引文件不再適合內存（不太可能，因爲即使是所有英文單詞列表也會適合任何普通用戶PC的內存）;但是，如果您需要加載大量文檔的索引文件，則內存可能會成爲問題。好的，你可以使用聰明的技巧來解決這個問題（例如直接在使用mmap等映射到內存的文件中搜索），但這些都是數據庫用來執行快速查找的相同技巧，因此爲什麼要重新創建車輪？此外，還可以防止在文檔發生更改（即，數據庫可以爲您執行鎖定或可以執行更新或更新作爲原子操作）時搜索單詞和更新索引之間的鎖定問題。對於使用AJAX調用列表更新的Web解決方案，使用數據庫可能是更好的解決方案（如果這是用C這樣的低級語言編寫的本地運行的應用程序，則我的第一個解決方案非常合適）。

如果您想在單個select調用中完成所有操作（這可能不是最佳選擇，但是當您使用AJAX動態更新Web內容時，它通常被證明爲導致最少頭痛的解決方案），則需要將所有三個表一起。五月SQL是有些生疏，但我會試試看：

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord 
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX') 
GROUP BY Document.idDoc HAVING NumOfHits=X 

好吧，也許這並不是最快的選擇...我想這是可以做到更快。無論如何，它會查找所有包含至少一個單詞的匹配文檔，然後將所有相同的文檔按ID進行分組，並統計有多少個分組爲togetehr，最後只顯示NumOfHits（IN語句的單詞數）等於IN語句中的單詞數（如果搜索10個單詞，則X爲10）。

Answer 4

Google Desktop Search或類似的工具可能符合您的要求。