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

Question

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

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

Answer 1

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

原理(参见链接中的实际示例)：当在文件中的某个位置(索引)开始比较时，如果要比较的文本的第一个字母根本不在被搜索的单词中，则不需要将其其他wordLength -1字符与文本进行比较，并且索引可以向前移动到单词长度的前面。如果字母在单词中，不是在这里，而是移动了几个字符，比较也可以移动几个字符，等等。

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

编辑由于您是从文件的末尾开始搜索的，因此首先要比较单词的第一个字母(而不是最后一个)。例如，在"2001 a space odyssey“中搜索" space”，单词space 's‘首先要与奥德赛'y’进行比较。下一个比较是与文本空间'c‘相同的's’。

最后，为了找到第n次出现的单词，每次找到单词时，都会递减一个简单的计数器(初始化为n)，当它达到0时，就是这样。

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

您可能还会问，文件是只搜索一次还是搜索几次？如果要多次搜索，您可以建议对文件中的单词进行索引。也就是说，在内存中创建一个结构，允许快速查找一个单词是否在其中，在哪里，多少次等。我喜欢的Trie algorithm也容易理解，而且速度非常快(可以非常贪婪的内存也取决于文本)。其复杂度为O(wordLength)。

--

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

• search algorithm如上所述
• 文本能放入内存吗？(例如，在处理所有文件时)我是否必须实现文件查找算法(即一次只使用内存中文件的一部分)
• 文件在哪里？内存(快速)，硬盘(较慢，但至少是本地)，远程(通常较慢，连接问题，访问远程，防火墙，网络速度等)
• 文件是否压缩？(是否会占用更多的空间，一旦uncompressed)
• is的文件由一个或几个块？
• 它包含文本或二进制文件？如果是文本，它的语言给出了字母出现的概率的指示(例如，在英语中，Y出现的频率比在French).
• Offer中要高得多，以索引文件中的单词如果relevant
• Offer从大一创建一个更简单的文件(如删除重复的单词等))为了拥有更小的、更容易处理的东西，

..。

Answer 2

这个问题的答案有两个部分。一个是使用的算法，可以是任何好的字符串搜索算法(Boyer、Moore / KMP / Trie等)。另一部分是IO。为了加快速度，因为你不能真正地从文件中向后读取，一个好的方法是：

1. 为(i = 1；(filesize - 10MB * i) filesize- 10MB * i) >= 0；i++)分配一块内存比如10MB
2. {
3. seek to (filesize -10MB*i)

read 10MB to (filesize-10MB*i) and read 10MB to memory

1. Search in the current chunk )反向搜索当前块中的字符串，并在计数器达到10时递增计数器

H19停止计数H210 G211

这是一个严重面向IO的问题，你可以使用多线程系统或多台机器来改进这种方法，在这些系统中，你可以并行地从文件到内存进行搜索和读取(即，步骤3和4)。

这是C++代码，但您知道如何在Java语言中这样做。

Answer 3

添加@AlexeyFrunze的评论，请参阅此处的相关帖子：read file backwards (last line first)。然而，也许面试官感兴趣的是一个解决方案，在这个方案中，你以正常的向前方向阅读，看看你将如何解决内存有限的问题。

非常棒的帖子@0，所以我只会提到一些关于在一个真正的大文件中查找末尾的第k个单词的问题，其中k很小，比如10，这表明你不应该记住整个文件然后向后搜索。

你可以维护一个先进先出的缓冲区。queue大小为k，您可以在其中存储遇到的匹配位置。随着你找到越来越多的匹配项，你会忘记之前的那些。给定const int k = 10;和long match_pos[k];初始化为0和count，您可以为排队寻址match_pos[count % k] = pos。一旦你到达文件的末尾，

if (count >= k)
{
    int kth_match_pos = match_pos[(count + 1) % k];
    // ...
}

检查缓冲区中最旧的条目，以便您可以向后跳转n字节，其中n为pos - kth_match_pos。如果相关的上下文也存储在队列中，则不需要查找。