计算大文本文件中特定词的出现次数

Question

这是一个面试问题，应该关注效率。如何计算大文本文件中指定词的出现？我只能想到大多数编程语言中的indexOf（）方法，但我不认为这是正确的答案。

Answer 1

你想要的是Boyer-Moore algorithm。这是解决这个问题的最有效的已知通用方法。

Answer 2

识别字发生的最好办法，而不是仅仅出现一个行的文件中的子串字符该序列，可能是从\bword\b编译正则表达式Pattern - 的\b是“字边界”。

一旦你有了这个Pattern没有直接的方法来计算一行中出现的次数，所以你需要一些基准来找出更快的 - split（将结果数组的长度减去一个），但不可能，但可能，或者使用该模式的matcher方法制作一个方法，然后在计数（我赌这个）或其他东西时循环其find方法。但是单独检测字边界就足够了PITA，我倾向于总是使用正则表达式来处理任务;-)。

可以通过一次读取多条线（并计算单词出现次数）来挤压某些速度 - 比如一次一个MB。但是，如果你这样做，那么你必须关注兆字节中的最后一条“部分”线，因为这个词的出现可能会在该部分行的结尾与下一个吞咽的开始之间分裂 - 可行，但是这种优化只是在胁迫下进行的，因为它很容易引入错误;-)。

Answer 3

如果文本文件非常大，indexOf（）可能不是一个好主意，因为您需要将整个文件加载到一个字符串中并因此咀嚼内存。给定足够的数据，你会崩溃的程序。我认为你需要查看流读取API来读取块的文件，这些文件比indexOf（）更实用。

Answer 4

使用buffered stream字符逐字符到数组读取文件，直到空白字符遇到或它们的组（空格，制表符，新的生产线，...），比较数组与目标词的内容，如果比赛增加计数器，清除数组，返回阅读。

预先分配足够大小的数组，然后重新使用它进行读取，如果需要的话进行扩展，不要在每次迭代时分配它。不要每次都清除数组，只需将其读取计数器设置为零即可。另外，您可以将字符的读取和将其与目标进行比较，并将其转换为单个循环，从而不再需要中间数组。第一个变体很容易转换成这个，只是抛出数组并且即时比较，您只需要知道当前字符及其在单词中的位置。