从非常大的文件中删除罕见的单词

Question

给定一个非常大的文本文件,我想删除在文件中只出现一次的所有单词.有没有简单有效的方法呢？

最好的祝福,

Answer 1

你必须在文件中进行2次传递:

在第1遍:

• 使用单词作为键及其出现的值来构建字典(即每次读取单词时,在字典中将其值加1)
• 然后预处理列表以删除值大于1的所有键.现在是您的"黑名单"

在第2轮:

• 再次读取文件并删除黑名单中匹配的任何单词.

运行:

• 两次传递中读取文件的线性时间.
• 它需要O(1)将每个单词添加到字典中/在第1遍中增加其值.
• 需要O(n)将字典预处理到黑名单中.
• 在第2遍中,黑名单查找需要O(1).

O(n)复杂性