5

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

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

4

3 回答 3

4

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

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

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

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

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

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

--

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

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

...

于 2013-01-16T05:22:02.647 回答
1

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

  1. 分配一块内存，比如 10MB
  2. for (i = 1; (文件大小 - 10MB * i) >= 0; i++) {
  3. 寻找 (filesize - 10MB * i) 并将 10MB 读入内存
  4. 向后搜索当前块中的字符串并增加一个计数器
  5. 当计数器达到 10 时停止

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

这是 C++ 代码，但您知道如何在 Java 中执行此操作。

于 2013-01-16T05:51:00.977 回答
0

添加@AlexeyFrunze 的评论，请参阅此处的相关帖子：向后读取文件（最后一行首先）。然而，也许面试官对一个解决方案感兴趣，在这个解决方案中，你可以正常向前阅读，看看你将如何解决记忆力有限的问题。

@ring0 的精彩帖子，所以我只提一些关于在一个非常大的文件中从末尾开始专门查找第 k 个单词的问题，其中k像 10 一样小，这表明你不应该记住整个文件和然后向后搜索。

您可以维护一个先进先出缓冲区，即大小为k的队列，您可以在其中存储遇到匹配项的位置。随着您找到越来越多的匹配项，您将忘记之前的匹配项。给定并初始化为零，并且，您可以解决排队问题。到达文件末尾后，const int k = 10;long match_pos[k];countmatch_pos[count % k] = pos

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

检查缓冲区中最旧的条目，因此您可以跳回n字节，其中n是pos - kth_match_pos. 如果相关上下文也存储在队列中，则无需查找。

于 2013-01-16T05:52:31.163 回答