如何在內存不足的環境中查找書中的高頻詞？

Question

最近在一次技術性採訪中，我被要求編寫一個程序，以在教科書中找到高頻詞（出現最多次數的詞）。程序的設計應該以最小內存來處理整個教科書。性能不是問題。我能夠編程來查找單詞的頻率，但它消耗了大量的內存。

你如何使這個操作減少內存密集？任何策略/解決方案？

-Snehal

Answer 1

您可能使用了內存密集但具有恆定查找時間的哈希表 - 因此性能/內存的權衡是顯而易見的。當你到達書本的最後，你會知道你的答案。另外，爲每個單詞增加計數器是快速的（因爲快速哈希表查找）。

該譜的另一端是查看第一個單詞，然後瀏覽整本書以查看該單詞出現的次數。這需要最少的內存。然後你對下一個單詞也做同樣的事情，並閱讀整本書。如果這個單詞出現的次數更多，則將其添加爲頂部單詞（或前N個單詞）。當然，這是非常低效的 - 如果第一個和第三個單詞相同，即使你對第一個單詞做了同樣的事情，你也會再次閱讀整本書。

Answer 2

一種方法是先對列表進行排序。

我們可以在沒有很多內存的情況下對單詞進行排序（交易時表現較慢）。

然後，我們可以有一個簡單的計數循環，可以找到最大頻率的單詞，而無需將所有內容保存在內存中，因爲它們處於排序形式。

Answer 3

你的意思是很多進程內存？如果是這樣，一種方法是使用磁盤作爲虛擬內存（也就是寫一個文件系統包裝）。

Answer 4

如果表現真的不用擔心，你可以依次瀏覽每個單詞，檢查它是否在你的「前N」，如果不是，則計算所有它的出現次數。這樣你只能存儲N個值。當然，你會多次重複相同的單詞，但正如你所說的，性能不是問題 - 而且代碼很簡單（通常比較好 - 所有其他條件相同）。

Answer 5

一個可能的解決方案是使用一個trie數據結構來存儲與其出現次數相關的所有單詞。

其他解決方案可能在答案被找到此相關的問題：Space-Efficient Data Structure for Storing a Word List?

Answer 6

OK，如果發生的話就只是在最高ñ興趣，這樣做是兩遍，與第一遍的一種方式基於修改的Bloom Filter。取而代之的是使用位圖來跟蹤哈希出現次數，而不是使用整數數組 - 取決於您的輸入大小，可以使用字節，16位，32位甚至64位。如果布隆過濾器只是簡單地設置一個單詞的每個哈希值對應的位，您就會在數組中的哈希索引處增加計數。

這種方法的問題是，兩個單詞可能會給出相同的散列值。所以你需要做第二遍，忽略單詞，除非它們的哈希總數超過了某個閾值，這樣就減少了你需要分配的內存數量來做精確計數。

因此，只需創建一個位圖，併爲最高出現的散列值設置位。然後在單詞的第二遍中，如果一個單詞在其位圖中具有其「哈希」，請查找它或將其添加到哈希表並增加其計數。這通過創建只有最高出現的單詞的哈希表來最大限度地減少內存使用量。

Answer 7

我是一名物理學家，所以我最喜歡的方法是近似。 您無需瀏覽整個文本即可獲取最頻繁的單詞。相反：

• 解析塊足夠小，以便爲您的內存限制，
• 跳過文本的隨機量，
• 重複，結合積累的結果。
• 列表滿意地收斂時停止。

如果您使用的更小的塊（例如排序）內存高效的算法，那麼你可以得到甚至比最有效的算法，上面寫着每一個字遠遠更快的性能。

注意：這確實假定最頻繁的單詞確實出現在整個文本中最頻繁，而不僅僅是在文本中的一個地方。對於英文文本來說，這個假設是真實的，因爲整個詞彙的頻率就像'the'等。如果您擔心這一要求，則需要算法完成整個文本的至少一遍。

Answer 8

我可能會得到下投票支持這一...

如果文字是英語，你只是想找到頂級的5個高頻詞，這裏是你的程序：

print "1. the\n"; 
print "2. of\n"; 
print "3. and\n"; 
print "4. a\n"; 
print "5. to\n"; 

快速運行和消耗最少的內存！

Answer 9

像許多很好的面試問題一樣，這個問題有點含糊不清/不精確，迫使受訪者提出澄清問題和陳述假設。我認爲這裏有很多其他答案都很好，因爲他們揣摩這些假設並展示出全面的理解。

我是假設文本在某個地方被「離線」存儲，但是有一種方法可以遍歷文本中的每個單詞而無需將整個文本加載到內存中。

然後下面的F＃代碼找到前N個單詞。只有數據結構是鍵值對（詞，頻率）的映射，並且它只保留那些的前N個，所以內存使用是O（N），這很小。運行時間是O（numWordsInText^2），它很差，但在問題約束條件下可以接受。該算法的要點很簡單，對於文本中的每個單詞，計算它發生的次數，並且如果它處於運行最佳狀態-N，則將其添加到列表中，並刪除以前的最小條目。

請注意，下面的實際程序將整個文本加載到內存中，僅僅是爲了方便說明。

#light 
// some boilerplate to grab a big piece of text off the web for testing 
open System.IO 
open System.Net 
let HttpGet (url: string) = 
    let req = System.Net.WebRequest.Create(url) 
    let resp = req.GetResponse() 
    let stream = resp.GetResponseStream() 
    let reader = new StreamReader(stream) 
    let data = reader.ReadToEnd() 
    resp.Close() 
    data 
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1" 
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries) 
// perhaps 'words' isn't actually stored in memory, but so long as we can 
// 'foreach' over all the words in the text we're good 
let N = 5 // how many 'top frequency' words we want to find 
let FindMin map = 
    // key-value pair with mininum value in a map 
    let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map 
    map |> Map.fold_left 
     (fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v)) 
     seed 
let Main() = 
    let mutable freqCounts = Map.of_list [ ("",0) ] 
    for word in words do 
     let mutable count = 0 
     for x in words do 
      if x = word then 
       count <- count + 1 
     let minStr,minCount = FindMin freqCounts 
     if count >= minCount then 
      freqCounts <- Map.add word count freqCounts 
     if Seq.length freqCounts > N then 
      freqCounts <- Map.remove minStr freqCounts 
    freqCounts 
    |> Seq.sort_by (fun (KeyValue(k,v)) -> -v) 
    |> Seq.iter (printfn "%A") 
Main() 

輸出：

[the, 75] 
[to, 41] 
[in, 34] 
[a, 32] 
[of, 29] 

Answer 10

好吧，如果你想絕對可怕的性能...

就拿書中的第一個字，又算什麼呢多少次發生。記下書中的第二個單詞，數出它發生的次數。如果它不是最後一個字，就放棄最後一個字。等等......你最終會多次統計相同的單詞，除非你把它們保存在某個地方，但如果你真的想要最小化內存，這應該只需要幾個整數。應該在O（n^2）時間運行，其中n是書中單詞的數量。

Answer 11

如何創建一個字鍵的二叉樹（當你不斷從文件中讀取單詞）。這有助於搜索O（Log（n））中已經重複的單詞。所以最後你得到O（nLog（n））進行頂級單詞搜索。

基本算法中會

在一個文件中的每個字：

1. 創建一個給定的單詞唯一的密鑰（加權的ASCII字符，例如「蝙蝠」可能是1 *「B」 + 2 * 「A」 + 3 *「C」;
2. 這個單詞添加到樹如果單詞已經存在增加新的計
3. 訂閱字和當前計數maintainTop5（文字，計數）maintainTop5（。 ）保持top5計數和關聯詞的動態列表。

文件末尾有5個單詞。

Answer 12

您可以使用組合外部合併排序和優先隊列。合併排序將確保您的內存限制得到遵守，並且優先級隊列將保持您的最高K搜索。顯然，優先級隊列必須足夠小以適應內存。

• 首先，分割輸入串分割成塊，排序每個組塊，並存儲到二次存儲（外部排序） - O（N log n）的
• 讀取每個塊和塊內，計算單詞的頻率，從而在此步驟結束時，塊內的每個塊減少到（唯一字 - 頻率計數）。 O（n）
• 開始讀取塊中的元素並聚合每個單詞。由於塊已分類，因此可以在O（n）中執行
• 現在，維護K個元素的最小優先級堆（堆的頂部是堆中的最小元素）。如果它的計數大於堆中的頂部元素，則彈出頂部和推動當前字，然後爲下一個（唯一字 - 最終計數）填充首先K個元素的優先堆。 O（N日誌K）

因此，最終的時間複雜度爲爲O（n（日誌K + log n）的） -