從大文件訪問n-gram頻率

我對自然語言處理和java編程頗爲陌生。我有一個非常大的文本文件，其中包含ngram和相關頻率（aaprox。250 mb）。我需要在程序運行時得到頻率值，以ngram爲單位。該NGRAM頻率在文件中提供以下（例如只）：使用系統從大文件訪問n-gram頻率

the quick 445 
quick brown 458 
brown fox 11 
fox jumped 123

我試圖通過填充HashSet的閱讀在啓動文件...但它花了將近1500毫秒一個18MB的文件（測試.currentTimeMillis（））。現在我正在考慮對n-gram計數進行排序，並將250MB文件分成小塊，並通過將文件集索引到單獨的索引並引用它來填充列表並按需獲取頻率。

但是，我不知道是否有這樣做的另一個更容易或更有效的方法。請讓我知道是否有更好的方法來做到這一點。（如果它不使用任何腳本或庫，它會更好......）。謝謝你們。

來源

2013-02-21 td123

如果讀取18 MB需要1.5s，則讀取完整的250 MB大約需要20s。這真的是你程序的瓶頸嗎？根據我的經驗，在閱讀完n-gram之後，你對n-gram做的是慢速部分。我寫的一些代碼運行了好幾天，所以20年代沒有任何區別。 – mbatchkarov 2013-02-21 11:55:15

我真的需要減少程序的啓動時間，這對我來說更有效率。 – td123 2013-02-22 02:07:52

我同意@mbatchkarov加載時間通常不是最重要的優化目標。但運行時間通常與內存佔用密切相關（內存訪問速度較慢，所以您可以放入緩存的工作集越多越好）。

你的初始每個兩字組映射到整數計數（大概在java.util.HashMap中）的方法是合理的，但非常存儲器密集型的。您的計數文件包含數百萬個bigrams，並且每個文件都必須表示爲單獨的字符串。那些字符串消耗（至少）大約40個字節的內存，並且每個計數都需要一個Integer對象 - 在大多數JVM實現中大約需要20個字節。我粗略的信封猜測把這個數據結構放在了千兆字節之上。

但是你可以做的更好，通過觀察，雖然兩字組只在您的文件時（和你的數據結構）一次，最有個性的話被重複很多次 - 你可以矇混過關，而不用重複存儲起來。

我將與從字地圖以整數索引開始 - 例如，從例如，= 0，快速= 1，棕色= 2，等等。我不知道你的詞庫的大小，但是對於頻繁的英語單詞的典型映射可能有幾十或幾十萬個單詞。所以字符串存儲將會更小。

要存儲的數量，可以將這些整詞索引結合成一個複合鍵，並使用您的地圖是關鍵。一個簡單的「組合」方法就是簡單地將第一個單詞的索引和第二個索引中的OR進行位移。

僞代碼：

HashMap<String, Integer> lexicon = new HashMap<String, Integer>(); 

// Iterate through the file, mapping each word to 
for (String file line) { 
    ... Parse out word1 and word2 
    if (!lexicon.containsKey(word1)) { 
     lexicon.put(word1, lexicon.size()); 
    } 
    if (!lexicon.containsKey(word2)) { 
     lexicon.put(word2, lexicon.size()); 
    } 
}

現在，遍歷文件再次，添加計數到一個單獨的計數圖。

HashMap<Long, Integer> countMap = new HashMap<Long, Integer>(); 

for (String file line) { 
    ... Parse out word1, word2, and count 
    int i1 = lexicon.get(word1); 
    int i2 = lexicon.get(word2); 
    long key = (i1 << 32) | i2; 
    countMap.put(key, count); 
}

訪問兩字組數類似於它映射 - 查找兩個詞的索引，創建註冊表項，並查找在您的計數圖。這應該大大減少你的存儲空間。但我會更進一步，並將類型特定的地圖替換爲通用HashMaps，如FastUtil或Trove。原始數據結構將爲數據映射中的每個Long和Integer消除大量〜12-20字節的開銷。

上面的僞代碼假定您使用32位整數你詞索引，並將它們組合成64位多頭。如果您的詞庫足夠小，則可以使用16位短路和32位整數，並節省更多空間。

編輯：我應該清楚的是，如果你想實現一個完整的n元語言模型（trigram，4-gram等），則有更高效的表示方法，並且n-gram模型處理得很好由幾個圖書館（我建議你看看OpenGRM和Lingpipe）。但是，上面的僞代碼是一個簡單的，相對有效的方法來做一個簡單的bigram模型。

來源

2013-02-21 23:19:11 AaronD

我喜歡用整數映射單詞的想法。我會嘗試實施這種方法。感謝您的詳細解答。 – td123 2013-02-22 02:12:52

看看BerkeleyLM這是一個處理ngrams的特殊庫。

來源

2013-02-22 19:52:12

從大文件訪問n-gram頻率

回答

相關問題