在Python中執行字符串搜索的最快方法

我的任務是在非常短的文檔列表（例如200個字符）中搜索字符串或模式。但是，假設有100萬份這樣的文件。什麼是執行此搜索最有效的方法？我正在考慮對每個文檔進行標記並將這些單詞放在散列表中，並將單詞作爲鍵和文檔編號作爲值，然後創建一個單詞包。然後執行單詞搜索並檢索包含該單詞的文檔列表。從我所看到的是這個操作將採取O（n）操作。有沒有其他方法？可能沒有使用散列表？在Python中執行字符串搜索的最快方法

另外，有沒有一個python庫或第三方包可以執行高效的搜索？

來源

2012-10-28 Rkz

既然你正在尋找一個圖書館，你有沒有看過PyLucene？

http://lucene.apache.org/pylucene/features.html

雖然Lucene的通常實現排檢索（基於相對得分的比賽） - 而不是精確的匹配 - 這可以用於精確短語搜索。以下是如何使用Lucene搜索精確短語的鏈接。它是用Java編寫的，但給人的想法：

Exact Phrase search using Lucene?

你的問題具體問及效率。以什麼方式提高效率？我假設你的意思是用戶最快的查找時間。如果您的確在談論速度純粹是根據用戶的查找時間，那麼沒有比實際索引文檔中的所有單詞更快的方法，只要您願意耐受索引所有文檔的初始時間在語料庫中。這通常是合乎邏輯的選擇，因爲索引是一次性事件，用戶搜索經常發生。顯然，這帶有相當大的內存使用量。因此，如果您正在討論內存使用方面的效率問題，那麼您需要遍歷所有文檔並對每個文檔執行正則表達式搜索。如果您想避免索引的初始查找時間，您也可以使用這種方法，但是，再次，這不太可能是給定大的語料庫大小的邏輯限制因素，並且考慮到關心通常滿足將會使多個查詢。

我想指出的唯一的另一件事是，既然你提到您正在搜索模式，而不是說說而已，索引只有一行字，如果你想支持查詢模式（不會幫助，除非該模式是文檔中的單詞之一！）

如果您不打算使用Lucene，而是想自己實現這一點，請查看使用倒數索引的索引。這裏是如何，如果你正在尋找做短語查詢創建反向索引一個很好的解釋：

http://www.searchenginepeople.com/blog/how-search-really-works-the-index-2.html

來源

2012-10-28 05:57:01 smaccoun

非常感謝您的解釋。我在談論查找時間方面的效率，而不是記憶。我會嘗試PyLucene並看看它是如何工作的。 – Rkz

雖然你的想法使用哈希表來製作包的話聽起來很有趣，但我認爲當你打開每個文件，將它讀入內存，標記它，製作散列表，將每個令牌放入散列表中，，那麼索引你的哈希表找到包含單詞的每個文檔的文檔ID，你花更多的時間比你會如果你只是使用正則表達式，做每個文件中搜索：

import re 
import os 
import sys 

searchterm = sys.argv[1] 
searchexp = re.compile("(%s)" % searchterm, re.M) 

for filename in os.listdir(sys.argv[2]): 
    f = open(os.path.join(sys.argv[2], filename), 'r') 
    contents = f.read() 
    f.close() 
    if searchexp.search(contents): 
     print(filename)

這太慢了嗎？

來源

2012-10-28 04:51:05 joe

謝謝。我知道正則表達式，但我想獲得更多的投入來評估我的思維過程。我會試着看看哪一個表現更好。 – Rkz

對於這個問題，我認爲沒有比Russox所描述的here更好的解決方案，他爲可悲的退役谷歌代碼搜索引擎開發。

來源

2012-10-28 04:54:40 rici

這很有趣。謝謝 – Rkz

大多數搜索引擎通過倒排索引的原理工作的。基本上，對於每個標記（詞，trigram等），您存儲包含此標記的文檔的排序列表。在匹配查詢時，您將合併所有必需令牌的列表以生成候選文檔列表。如果索引匹配不能保證查詢匹配，則查詢表達式必須在匹配的文檔上重新測試。

有很多解決方案來存儲倒排索引，其中一些已經是（Lucene，Sphinx，PostgreSQL FTS）支持在倒排索引上評估表達式。

搜索引擎的魔力主要發生在預處理和標記文檔以及根據用戶請求生成搜索查詢。預處理技巧包括詞的規範化，通過詞幹和單詞存儲多個不同的表示。對於查詢構造，您可能想要做同義詞替換之類的事情。正則表達式有點棘手，但有一個關於implementing index support for regular expression searches in PostgreSQL的好消息。

來源

2012-10-28 09:53:07

這絕對是一個有趣的演講，謝謝你提及。 – Rkz

在Python中執行字符串搜索的最快方法

回答

相關問題