哈希+映射或索引+映射來濃縮使用字符串

我有〜200K命名屬性和〜25K文件。我使用Python提取每個文件的屬性是否保持爲一組屬性，每個文件一組。哈希+映射或索引+映射來濃縮使用字符串

要做到這一點，我可能會並行地在計算場上運行數百個單獨的Python提取腳本。每個文件都留下一些表示提取的集合。

進一步處理涉及讀取這些20K組並處理累積的數據。生成關於這組文件/屬性的報告。

我遇到的一個問題是，如果我將提取的集合存儲爲文本，那麼長屬性名稱字符串和文件名字符串將重複浪費磁盤空間並增加解析時間。

我正在考慮爲排序後的屬性名稱創建一箇中央索引，並且只保存索引 - 對於文件名來說是相同的，就像導入的.py文件一樣。

將索引用於排序的名稱列表的另一種方法是使用str。散列（）價值作爲索引，這可能意味着更快的處理，但我擔心兩個不相等的字符串可能會以相同的散列（）值結束。這可能發生嗎？

我會在所有機器上使用相同的Python可執行文件和操作系統版本。

來源

2010-11-02 Paddy3118

您是否事先知道房產？如果你這樣做，你可能會考慮Perfect hashing（即你可以散佈散列的設置而不是完整的屬性/文件列表）。

一個非常粗糙的（但可能工作的方式）會有幾個不同的散列函數（h1，h2 ...）;開始與str.hash（）並計算散列值。如果發生衝突，請嘗試使用元組（h1（屬性），h2（屬性））作爲散列。如果仍有衝突，請使用（h1（屬性），h2（屬性），h3（屬性））等，直到沒有衝突。 h_x函數實際上可以是一些可配置的函數，推薦的方法是嘗試一些隨機的散列函數。

然而，在我看來，這可能是矯枉過正，只分發文件的列表/屬性可能會輕鬆很多......

來源

2010-11-02 11:23:23 ondra

散列的整點你是從值中計算出來的，並且給定值的哈希值不會改變。你不能只是不斷改變哈希，直到它不碰撞。 – 2010-11-02 12:08:29

您可以不斷更改散列函數，直到散列值永遠不會碰撞爲止，並且只需要讓所有分佈式進程使用此特定散列函數即可。這被稱爲完美哈希;我認爲這是（或者至少）在一些編譯器中用來合理編譯巨大的'case'語句。 – ondra 2010-11-03 08:24:51

所以它歸結爲完美的哈希或使用索引？我想我會把它們編碼起來，然後看看最好的。 – Paddy3118 2010-11-03 23:08:04

哈希可以碰撞。你將不得不考慮這一點。

來源

2010-11-02 10:38:00

所以沒有靈丹妙藥:-) – Paddy3118 2010-11-04 07:40:42

哈希+映射或索引+映射來濃縮使用字符串

回答

相關問題