爲什麼當字典類可以從大的文件被用於字符串計數特里數據結構

假設我需要從一個非常大的文件數字（詞被「拆分」）爲什麼當字典類可以從大的文件被用於字符串計數特里數據結構

我會做以下

不加載內存中的整個文件，逐行讀取流。
對於每一行拆分單詞並添加不同的單詞到「字典」（我的意思是，在.NET中使用Dictionary Class ）和它們的計數。

現在檢索最頻繁的單詞，對字典進行排序並獲取它。

但是大多數解決方案都是爲此而傾向於使用Trie Data結構，請說明原因（同樣，如果爲什麼不通過字典散列表得到澄清，這將很好）。

謝謝。

來源

2014-09-01 Sunil Vurity

什麼意思_very large_ exactly？ – 2014-09-01 22:09:09

「爲什麼不用字典散列表」：一個'字典 * *是一個散列表;它基本上與'Hashtable'類相同，除了它是通用的。 – 2014-09-01 22:20:17

你爲什麼不自己嘗試一下。當您查詢「c＃trie類」時，您會從Google獲得大量幫助。當你比較它對Linq查詢或字典的有效性時，你會發現一些對現代計算機工作方式非常重要的知識。並且能夠提出一個很好的問題。 – 2014-09-01 22:23:12

您可以使用File.ReadLines，它與流式閱讀器相似。

var mostFrequent = File.ReadLines("Path") 
    .SelectMany(l => l.Split()) // splits also by tabs 
    .GroupBy(word => word) 
    .OrderByDescending(g => g.Count()) 
    .First(); // or Take(10) if you want the top 10 

Console.Write("Word:{0} Count:{1}", mostFrequent.Key, mostFrequent.Count());

來源

2014-09-01 22:15:00

是的，但它沒有回答這個問題...... – 2014-09-01 22:19:15

@ThomasLevesque：_「現在檢索最常用的詞，排序字典並得到它。」_我不明白他爲什麼需要字典，如果他只是想找到最常用的詞+數。 – 2014-09-01 22:19:35

非常大，我的意思是一個TB文件或10 TB或更多 – 2014-09-01 22:20:45

我不禁提及，這不僅是一個map-reduce問題，它是the map-reduce problem。

除此之外，您使用trie實現的原因是爲了查找每個單詞來增加其計數（或添加一個還不存在於trie中的單詞）的效率。在基本特里，每個單詞的查詢時間是O(n)，其中n是單詞中的字符數。然後，在整個文檔中，如果沒有並行處理，則只需查看O(n)時間即可進行查找，其中n是文檔中的字符數。然後，它可能（可能）是深度優先搜索來檢索所有單詞，以便您可以提取所需的信息。深度優先搜索的最差情況的性能與O(n)相同，但由於共同前綴，預期情況會更好。

如果使用不同的結構（例如標準System.Collections.Generic.Dictionary<TKey, TValue>），它涉及散列查找，則代價與散列查找和實現以及散列衝突的普遍性有關。然而，即使這可能不是成本的主要部分。假設arguendo散列查找是恆定時間和平凡的。由於相同的散列碼不能保證有相同的字符串，因爲the MSDN docs warn repeatedly，仍然有必要比較字符串是否相等，這幾乎肯定實現爲O(n)，其中n是字符數（爲了簡單起見）。所以，根據trie和一些基於散列查找的字典的實現，基於散列查找的字典可能不會比trie好，而且可能更糟糕。

對我的分析有一個有效的批評可能是在trie中的每個節點的查找可能不是恆定時間;它將取決於用於確定後續節點邊緣的集合。然而，如果我們不關心以後對鍵進行排序，那麼基於散列查找的字典在這裏可能會工作得很好。當輸入是一個字符時，哈希衝突不太可能發生，並且等同比較比完整字符串要少得多。插入性能也可能是合理的，同樣取決於實施。

但是，如果你知道你要確定頂部n字由字計數，你可能需要保持頂級n字數的軌道，你除了在特里樹人保持跟蹤去。這樣，在填充特里樹後，您不需要重新計算頂部n。

來源

2014-09-02 04:07:12 Andrew

這也是關於內存消耗。它需要更少的時間來保存來自_very_大文件的單詞。在每個變體的哈希表中，你都會有另一個記錄。但是，你會重新使用已經存在的單詞部分。 – 2016-06-27 15:45:46

爲什麼當字典類可以從大的文件被用於字符串計數特里數據結構

回答

相關問題