如何找到大文本文件中单词的第n次出现(反向)？

Question

这是一个面试问题和对效率的担忧.当存在非常大的文件(以GB为单位)时,就像日志文件一样.我们怎样才能从文件末尾找到第10个出现的'error'或'java'等单词.我只能想到扫描整个文件,然后以相反的顺序找出事件.但我不认为这是正确的做法!(最好用C或Java编码)

我还想知道另一件事.当面试官特别提到它是一个非常大的文件时,我们开始编写代码时应该考虑哪些因素(除了记住扫描是非常昂贵的事情)

Answer 1

为了在大文本中搜索单词，博耶摩尔算法被广泛使用。

原理（参见链接的实例）：当在文件中的某个位置（索引）开始比较时，如果正在比较的文本的第一个字母根本不在正在搜索的单词中，则不需要比较文本中的其他 [wordLength - 1] 个字符，并且索引可以向前移动到单词长度。如果字母在单词中，不完全在这里，而是移动了几个字符，则比较也可以移动几个字符等......

• 根据单词长度和与文本的相似度，搜索可能会加速很多（最高可达 naiveSearchTime / wordLength）。

编辑由于您从文件末尾搜索，因此首先要比较单词的第一个字母（不是最后一个）。例如，在“2001 a space odyssey”中搜索“space”，单词space 's' 将与odyssey 的第一个'y'进行比较。接下来的比较是将相同的“s”与文本空间“c”进行比较。
最后，为了找到第 n 次出现，每次找到该单词时，一个简单的计数器（初始化为n）都会递减，当它达到 0 时，就这样了。

该算法易于理解和实现。非常适合面试。

您可能还会问该文件是只搜索一次还是多次？如果打算多次搜索，您可以建议从文件中索引单词。即在内存中创建一个结构，允许快速查找单词是否在其中、在哪里、出现了多少次等...我喜欢Trie 算法，它也很容易理解，而且速度非常快（也可能非常贪婪内存，具体取决于文本）。其复杂度为O(wordLength)。

--

当面试官提到“非常大的文件”时，需要考虑很多因素，例如

• 搜索算法如上
• 文字能装入内存吗？（例如，当处理所有文件时）我是否必须实现文件查找算法（即一次仅使用内存中文件的一部分）
• 文件在哪里？内存（快速）、硬盘（较慢但至少是本地）、远程（通常较慢、连接问题、远程访问、防火墙、网络速度等）
• 文件是否被压缩？（解压缩后将占用更多空间）
• 该文件是由一个文件还是几个块组成的？
• 它包含文本还是二进制？如果是文本，其语言会指示字母出现的概率（例如，在英语中 Y 出现的频率比法语中高得多）。
• 如果相关，建议对文件单词进行索引
• 提议从大文件创建一个更简单的文件（例如删除重复的单词等...），以便获得更小、更容易处理的文件

...