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

Question

这是一个面试问题和对效率的担忧。当有一个非常大的文件(以 GB 为单位)时，比如日志文件。我们如何从文件末尾找到第 10 次出现的单词，如“error”或“java”等。我只能想到扫描整个文件，然后以相反的顺序找出出现的地方。但我认为这不是正确的做法! (最好用 C 或 Java 编码)

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

Answer 1

要在大文本中搜索单词，Boyer Moore算法被广泛使用。

原理(实例见链接):在文件中的某个地方(索引)开始比较时，如果被比较文本的首字母根本不在被搜索的单词中，则没有需要将其其他 [wordLength - 1] 个字符与文本进行比较，索引可以向前移动字长。如果字母在单词中，不完全在这里，而是移动了几个字符，比较也可以移动几个字符等...

• 根据字长和与文本的相似度，搜索可能会加速很多(最多 naiveSearchTime/wordLength)。

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

该算法易于理解和实现。面试的理想选择。

您可能还会问文件是只查找一次还是多次？如果打算多次搜索，可以建议对文件中的词进行索引。 IE。在内存中创建一个结构，允许快速查找单词是否在其中、位置、次数等...我喜欢 Trie algorithm也很容易理解，而且速度非常快(根据文本也可能非常贪婪)。它的复杂度是O(wordLength)。

--

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

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

...