在不适合内存的大型文件中查找“n”个重复最多的单词/字符串

Question

我想验证我的伪代码，建议优化和更好的方法。

mostRepeatingWords（int-rank）：
（此处的rank定义您要选择的级别，即前X个最重复的单词）

>

创建一个新文件“wordCount”，其中包含如下条目

for ( read each of the sorted file one by one ) { 
    for (read each "word" in the current file) { 
        int count =  checkIfDuplicateAndReturnCount(); 
        enter "word" and "count" in the "wordCount" file. 

        sanitizeFile(); 

        if  (wordCount file is > page size) { 
                write wordCount file to disk. 
                create a new wordCount file.
         } 

        move to next word ie currentword + count;
    } 
}

复杂性O（np），其中n是已排序页面的数量，p

checkIfDuplicateAndReturnCount（）是一个简单的函数，它将此元素与first和previous等进行比较，并确定单词的频率。

• 电话号码：500
• 电话：600

将合并为：

null

for  (reading the all the wordcount files one by one ) {
  for (each word in the wordcount) {
    Use a minimum heap / priority queue of size "rank" to keep track of the frequency.
    if (wordcount > heap.peek()) {
        heap.addAtPositionZero(word);
    }   
  }
}

复杂性是O（p）

复杂性：ø（n logn/m）O（np）O（p）有效：ø（n logn/m）

Answer 1

读取该文件并为每个单词创建一个新文件，该文件将包含该单词的出现次数。

保留2个变量，一个用于存储单词，另一个用于存储事件。

>

对于每个单词，检查是否存在文件，如果存在文件，则从文件中读取计数；如果不存在文件，则创建新文件。

增加计数并将其写回文件。

复杂度为O（m*n），其中m是文件中的行数，n是字数。如果我在计算时间复杂度时出错，请纠正我。

Answer 2

>

处理数据k次，每次仅处理一个铲斗。使用不同的哈希函数，将一个bucket中的所有数据插入哈希表，然后选择n最常见的条目；从外部保存这些。

将所有保存的组中的n最常见的条目分区到一个桶中，以选择n最常见的单词。

Answer 3

没有必要提前对文件进行排序。这样做只是一堆不必要的I/O。

更直接的方法是：

Create an empty dictionary (hash map), keyed by word. The value is the count.
for each file
    while not end of file
        read word
        if word in dictionary
            update count
        else
            if dictionary full
                sort dictionary by word
                output dictionary to temporary file
                Clear dictionary
            Add word to dictionary, with count 1
    end
end
if dictionary not empty
    sort dictionary by word
    output dictionary to temporary file

现在您有了一些临时文件，每个文件按单词排序，每行包含一个单词/计数对。比如：

aardvark,12
bozo,3
zebra,5

创建一个最小堆，用于存放n个最大的项目。称之为最大项目。

对这些临时文件执行标准的n向合并。当您找到每个唯一项时（即，您将多个文件中的所有“aardvark”项合并），您可以执行以下操作：

if (largest_items.count < n)
    largest_items.add(word)
else if (word.count > largest_items.peek().count)
{
    // the count for this word is more than the smallest count
    // already on the heap. So remove the item with the
    // smallest count, and add this one.
    largest_items.remove_root()
    largest_items.add(word)
}

复杂性：

• 构建字典是O（N），其中N是文件中单个单词的总数。
• 对每个临时字典的排序是O（k log k），其中'k'是字典中的字数。
• 写每个临时字典都是O（k）
• 合并是O（M log x），其中M是所有临时文件的合并条目数，而x是临时文件数。
• 选择项目是O（m log n），其中m是唯一的单词数，n是要选择的单词数。

如果您查看最坏情况的行为（即所有单词都是唯一的），则复杂性计算为（n是单词总数）：

• 建立字典是一个非常困难的问题。
• 临时文件的排序和写入是（n/m）*（m log m），其中m是字典大小。
• 合并是n log（n/m）
• 选择是O（m（k log k）），其中k是要选择的字数，m是唯一字数。因为所有单词都是唯一的，所以它们具有相同的计数，所以您只需将k插入到堆中。当k远小于m时，m项占主导地位（在这些情况下通常如此）。所以选择结果是O（m）

当你处理比内存大的数据集时，你的瓶颈通常是文件输入输出。我上面概述的算法试图最小化输入输出。在最坏的情况下（所有单词都是唯一的），每个单词将被读取两次并写入一次。但是在一般情况下，每个单词被读取一次，然后每个散列页被写入一次并读取一次。此外，您的排序是在哈希页面上，而不是原始单词上，并且您的临时文件的总大小将比原始文本小得多。