查看大量字符串中存在的有效方法

我有一組超過1億個字符串，每個字符串長度可達63個字符。我有很多磁盤空間和很少的內存（512 MB）。我需要單獨查詢存在情況，並且不存儲其他元數據。查看大量字符串中存在的有效方法

我事實上的解決方案是BDB btree。有沒有更好的選擇？我知道leveldb和京都內閣，但不夠熟悉，以確定優勢。

2012-11-15 Drew Sears

你能容忍偶爾的誤報嗎？ – senderle

假陰性是不可接受的;偶爾的誤報可能是可以容忍的。 –

只需將它們全部存儲在'set'中，並根據需要讓操作系統的虛擬內存管理器將其分頁到磁盤。您也可以使用'pickle'將其明確保存到磁盤。不需要建立數據庫。 – martineau

如果誤報可以接受，那麼一種可能的解決方案是使用bloom filter。布隆過濾器類似於散列表，但不是使用一個散列值來索引一個存儲桶表，而是使用多個散列來索引一個位數組。這些索引對應的位被設置。然後，爲了測試一個字符串是否在過濾器中，該字符串再次被散列，並且如果相應的索引被設置，則該字符串在過濾器中「in」。

它不存儲關於字符串的任何信息，因此它使用的內存很少 - 但是如果兩個字符串之間存在衝突，則不可能實現衝突解決。這意味着可能存在誤報（因爲不在過濾器中的字符串可能會與過濾器中的字符串散列到相同的索引）。但是，不能有錯誤的否定;任何真正在該集合中的字符串都將在布隆過濾器中找到。

有一個few Python implementations。推出自己也不難;我記得自己使用bitarray s自己編碼一個快速和髒的布隆過濾器，表現相當不錯。

來源

2012-11-15 20:47:02 senderle

你的「快速和骯髒的實現是如何解決誤報？ – martineau

@martineau，好吧，它並沒有真正的。我的情況是錯誤的肯定是可以接受的，我正在迭代一個非常大的數據集，尋找可能的重複。我不需要確定它們是否重複;我只是稀疏數據集進行進一步處理。 – senderle

你說你有很多磁盤，對吧？一種選擇是將字符串作爲文件名存儲在嵌套的子目錄中。您既可以直接使用字符串：在d/r/e/w/ sears

或利用字符串的哈希，並遵循類似的過程

店「畫了西爾斯」：
- MD5（」 drew sears'）='f010fe6e20d12ed895c10b93b2f81c6e'
- 創建一個名爲f0/10/fe/6e/20d12ed895c10b93b2f81c6e的空文件。
認爲它是一個基於操作系統優化的基於哈希表的索引NoSQL數據庫。

附帶好處：
- 您可以在該文件中稍後的時間和存儲數據改變了主意。
- 您可以使用rsync將數據庫複製到其他系統。

來源

2012-11-15 21:00:41

+1創造力 - 但使用操作系統來檢查是否存在這樣深度嵌套的文件會更慢，更不用說創造它們。 – martineau

其實現在我想到了更多，爲什麼有一堆嵌套的子目錄？相反，只需爲每個字符串創建一個空文件並將它們全部存儲在一個目錄中。當然，可能會有一些文件系統問題... – martineau

沒有測試，我不確定它是否會變慢。它實際上可以非常精細地取決於文件系統。對於較小的目錄，很多文件系統要快得多，而且大多數（所有？）現代FSes都很好地緩存目錄查找。這是嵌套子目錄的動機。 –

查看大量字符串中存在的有效方法

回答

相關問題