使用延迟文本和字节索引处理非常大的文本文件

Question

我正在尝试处理一个非常大的unicode文本文件(6GB +).我想要的是计算每个独特单词的频率.Data.Map当我遍历文件时,我使用严格来跟踪每个单词的计数.这个过程需要太多时间和太多内存(20GB +).我怀疑地图很大,但我不确定它应该达到文件大小的5倍!代码如下所示.请注意我尝试了以下内容:

• 使用Data.HashMap.Strict而不是Data.Map.Strict.Data.Map似乎在较慢的内存消耗增加率方面表现更好.

• 使用lazy ByteString而不是lazy 读取文件Text.然后我编码为文本做一些处理,然后对其进行编码,回ByteString了IO.

  import Data.Text.Lazy (Text(..), cons, pack, append)
  import qualified Data.Text.Lazy as T
  import qualified Data.Text.Lazy.IO as TI
  import Data.Map.Strict hiding (foldr, map, foldl')
  import System.Environment
  import System.IO
  import Data.Word
  
  dictionate :: [Text] -> Map Text Word16
  dictionate = fromListWith (+) . (`zip` [1,1..])
  
  main = do
      [file,out] <- getArgs
      h <- openFile file ReadMode
      hO <- openFile out WriteMode
      mapM_ (flip hSetEncoding utf8) [h,hO]
      txt <- TI.hGetContents h
      TI.hPutStr hO . T.unlines . 
        map (uncurry ((. cons '\t' . pack . show) . append)) . 
        toList . dictionate . T.words $ txt
      hFlush hO
      mapM_ hClose [h,hO]
      print "success"
  

我的做法有什么问题？在时间和内存性能方面,完成我想要做的最好的方法是什么？

Answer 1

此内存使用是预期的.Data.Map.Map消耗约6N的记忆单词+键和值的大小(Johan Tibell从这篇优秀文章中获取的数据).甲懒惰 Text值占用7个词语+ 2*N个字节(四舍五入至机器字大小的倍数),以及Word16 占用两个单词(报头+有效载荷).我们假设一台64位机器,所以字大小为8字节.我们还假设输入中的平均字符串长度为8个字符.

考虑到这一点,内存使用的最终公式是6*N + 7*N + 2*N + 2*N单词.

在最坏的情况下,所有的单词都会有所不同,并且会有很多单词(6 * 1024^3)/8 ~= 800 * 10^6.在上面的公式中插入我们得到的最坏情况的地图大小约.102 GiB,这似乎与实验结果一致.反方向求解这个等式告诉我们你的文件包含200*10^6不同的单词.

至于解决这个问题的替代方法,可以考虑使用trie(如J.Abrahamson在评论中所建议的)或近似方法,例如count-min sketch.