给上千个文件，每个文件大小为1K—100M。给n个词，设计算

[问答题]

给上千个文件，每个文件大小为1K—100M。给n个词，设计算法对每个词找到所有包含它的文件，你只有100K内存

查看答案及解析

为你扣下F键

用n个词构建字典树，然后每个文件都来跑一遍该字典树即可

发表于 2019-03-11 21:58:07 回复(0)

孤寡孤寡的熊猫很安静

这个题，难道不是用倒排索引？

发表于 2018-05-25 10:55:23 回复(0)

逐梦者的脚步

应该采用AC自动机

发表于 2019-04-12 09:23:43 回复(0)

勇士夺冠

0: 用一个文件info 准备用来保存ｎ个词和包含其的文件信息。
1 : 首先把ｎ个词分成ｘ份。对每一份用生成一个布隆过滤器（因为对ｎ个词只生成一个布隆过滤器，内存可能不够用）。把生成的所有布隆过滤器存入外存的一个文件Filter中。
２：将内存分为两块缓冲区，一块用于每次读入一个布隆过滤器，一个用于读文件(读文件这个缓冲区使用相当于有界生产者消费者问题模型来实现同步)，大文件可以分为更小的文件，但需要存储大文件的标示信息（如这个小文件是哪个大文件的）。
３：对读入的每一个单词用内存中的布隆过滤器来判断是否包含这个值，如果不包含，从Filter文件中读取下一个布隆过滤器到内存，直到包含或遍历完所有布隆过滤器。如果包含,更新info 文件。直到处理完所有数据。删除Filter文件。

备注：
１：关于布隆过滤器：其实就是一张用来存储字符串hash值的BitMap.
２：可能还有一些细节问题，如重复的字符串导致的重复计算等要考虑一下。

编辑于 2016-10-25 15:38:40 回复(2)