使用延迟文本和字节字符串处理一个非常大的文本文件

Question

我正在尝试处理一个非常大的Unicode文本文件（6GB+）。我想要的是统计每个唯一单词的频率。在遍历文件时，我使用严格的 Data.Map 来跟踪每个单词的计数。 这个过程需要太多的时间和内存（20GB+）。我怀疑Map很大，但我不确定它是否应该达到文件大小的5倍！ 以下是代码。请注意，我尝试了以下操作：

• Using Data.HashMap.Strict instead of Data.Map.Strict. Data.Map seems to perform better in terms of slower memory consumption increase rate.

• Reading the files using lazy ByteString instead of lazy Text. And then I encode it to Text do some processing and then encode it back to ByteString for 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"
  

我的方法有什么问题？在时间和内存性能方面，实现我想做的最佳方式是什么？

- haskelline

---

@leftaroundabout 假设最坏情况，文件中的所有单词都是唯一的。地图大小应达到30GB吗？ - haskelline

这一点并不奇怪，@duplode 只是使用了一个拥有比你所用的文件更少独特单词的文本文件（这在自然语言中是不可避免的，并且由于使用了许多相同文本的副本而没有得到帮助）。 - leftaroundabout

7.6.3，x86-64。不知道你的输入是什么，我猜我的结果支持leftaroundabout所说的（我的文件是由自然语言文本制成的，因此有相对较少的不同单词）。 - duplode

只是问一个愚蠢的问题：你正在使用“-O2”编译吗？ - Daniel Wagner

你可以尝试使用类似 bytestring-trie 的工具，这会对你有所裨益。 - J. Abrahamson

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。

- Mikhail Glushenkov

Answer 2

在传统数据处理领域，这个问题通常会通过排序（如果需要，可以在磁盘或磁带上进行外部排序），然后扫描已排序的文件以计算单词分组运行的数量来解决。当然，在排序的早期阶段可以进行一些部分归约，以节省一些空间和时间。

- none