1

这些年来我积累了大约 600GB 的字典，我决定清理它们并对其进行排序

首先，平均每个文件都非常大，大小从 500MB 到 9GB 不等。我想做的一个先决条件是我对每个字典进行排序。我的最终目标是完全删除所有字典文件中的重复单词。

这样做的原因是我的大多数字典都是按类别排序和组织的，但重复的仍然经常存在。

Load file
     Read each line and put into data structure
     Sort and remove any and all duplicate
Load next file and repeat

Once all files are individually unique, compare against eachother and remove duplicates

对于字典 D{1} 到 D{N}：

1) 分别对D{1}到D{N}进行排序。

2) 检查D{i}中每个单词的唯一性

3) 对于D{i}中的每个单词，检查D{i+1}到D{N}中的所有单词。如果在D{i}中唯一，则首先删除每个单词。

  • 我正在考虑使用一种“哈希”来改进这个算法。可能只检查前一个或两个字符，因为列表将被排序（例如，以 a、b 等开头的单词的散列开始行位置）。

4) 保存并退出。

之前的示例（但要小得多）：

    Dictionary 1            Dictionary 2            Dictionary 3

    ]a                      0u3TGNdB                2 KLOCK
    all                     avisskriveri            4BZ32nKEMiqEaT7z
    ast                     chorion                 4BZ5
    astn                    chowders                bebotch
    apiala                  chroma                  bebotch
    apiales                 louts                   bebotch
    avisskriveri            lowlander               chorion
    avisskriverier          namely                  PC-Based
    avisskriverierne        silking                 PC-Based
    avisskriving            underwater              PC-Based

因此，它会看到 avisskriveri、chorion、bebotch 和 PC-Based 是在三个词典中的每一个内部和之间重复的单词。所以我首先在D{1}中看到 avisskriveri ，所以在我见过的所有其他实例中删除它。然后我首先在D{2}中看到绒毛膜，然后在所有其他实例中首先删除它，依此类推。在D{3}中，bebotch 和 PC-Based 被复制，所以我想删除它的一个条目（除非我以前见过它）。然后保存所有文件并关闭。

之后的示例：

     Dictionary 1           Dictionary 2            Dictionary 3

     ]a                     0u3TGNdB                2 KLOCK
     all                    chorion                 4BZ32nKEMiqEaT7z
     ast                    chowders                4BZ5
     astn                   chroma                  bebotch
     apiala                 louts                   PC-Based
     apiales                lowlander                   
     avisskriveri           namely              
     avisskriverier         silking                 
     avisskriverierne       underwater                          
     avisskriving

请记住：我不想创建任何新字典，只删除所有字典中的重复项。

选项：

  • “散列”每个文件的唯一字数，允许程序估计计算时间。

  • 指定一种方式，给出以所需第一个字母开头的第一个单词的位置。这样搜索可以“跳转”到一行并跳过不必要的计算时间。

  • 在 GPU 上运行以进行高性能并行计算。（这是一个问题，因为从 GPU 中获取数据很棘手）

目标：减少计算时间和空间消耗，使该方法在能力有限的标准机器或服务器上负担得起。或者设备一种在 GPU 集群上远程运行它的方法。

tl;dr - 对数百个文件中的唯一单词进行排序，其中每个文件的大小为 1-9GB。

4

4 回答 4

1

我将从以下内容开始：

#include <string>
#include <set>

int main()
{
    typedef std::set<string> Words;
    Words words;
    std::string word;
    while (std::cin >> word)
        words.insert(word);  // will only work if not seen before
    for (Words::const_iterator i = words.begin(); i != words.end(); ++i)
        std::cout << *i;
}

然后只是：

cat file1 file2... | ./this_wonderful_program > greatest_dictionary.txt

假设非重复单词的数量适合内存（可能在任何现代 PC 上，特别是如果你有 64 位和 > 4GB）应该没问题，这可能是 I/O 绑定的，所以没有必要对无序映射大惊小怪（二叉树）地图等。在插入地图之前，您可能需要转换为小写，去除虚假字符等。

编辑：

如果唯一的单词不适合内存，或者您只是顽固地决定对每个单独的输入进行排序然后合并它们，您可以sort对每个文件使用 unix 命令，然后sort -m有效地合并预先排序的文件。如果您不在 UNIX/Linux 上，您可能仍然可以找到一个端口sort（例如，来自 Cygwin for Windows），您的操作系统可能有一个等效程序，或者您可以尝试编译sort源代码。请注意，这种方法与 tb- 提出的要求一次调用对所有内容进行排序（大概在内存中）的建议略有不同sort- 我不确定它的效果如何，因此最好尝试/比较。

于 2013-01-31T06:23:30.220 回答
1

在 300GB 以上的规模上，您可能需要考虑使用Hadoop或其他一些可扩展的存储 - 否则，您将不得不通过自己的编码来处理内存问题。您可以尝试其他更直接的方法（UNIX 脚本、小型 C/C++ 程序等），但您可能会耗尽内存，除非您的数据中有大量重复的单词。

附录

刚刚遇到memcached，它似乎与您想要完成的非常接近：但您可能必须对其进行调整，以免丢弃最旧的值。我现在没有时间检查，但您应该在Distributed Hash Tables上进行搜索。

于 2013-01-31T06:25:56.243 回答
1

假设字典按字母顺序逐行排列，每行一个单词（大多数字典也是如此），您可以执行以下操作：

Open a file stream to each file.
Open a file stream to the compiled list file.
Read 1 entry from each file and put it onto a heap, priority queue, or other sorted data structure.
while you still have entries
    find & remove the first entry, storing the word (it is not necessary to store the file)
    read in the next entry from that file, if one exists
    find & remove any duplicates of the stored entry
    read in the next entry for each of those files, if one exists
    write the stored word to your compiled list file
Close all of the streams

其效率类似于 O(n*m*log(n))，空间效率为 O(n)，其中 n 是文件数，m 是平均条目数。

请注意，您需要创建一种数据类型，将条目（字符串）与文件指针/引用配对，并按字符串存储排序。您还需要一个允许您在弹出之前先查看的数据结构。

如果您在实施中有问题，请问我。

更彻底的效率分析：

空间效率很容易。你填充数据结构，并且对于你穿上的每一件物品，你脱掉一件，所以它保持在 O(n)。

计算效率更复杂。循环本身是 O(n*m)，因为您将考虑每个条目，并且有 n*m 个条目。其中百分之几是有效的，但这是一个常数，所以我们不在乎。

接下来，从优先级队列中添加和删除都是 log(n) 两种方式，所以查找和删除是 2*log(n)。

因为我们添加和删除每个条目，我们得到 n*m 添加和删除，所以 O(n*m*log(n))。我认为在这种情况下它实际上可能是一个θ，但是嗯。

于 2013-01-31T06:30:20.500 回答
1

据我了解，没有可以巧妙利用的模式。所以我们想做原始排序。

让我们假设没有可用的集群场（我们可以做其他事情）

然后我会从最简单的方法开始，命令行工具sort：

排序 -u inp1 inp2 -o 排序

这将在输出文件中排序inp1并inp2一起sorted没有重复（u = 唯一）。排序通常使用自定义的归并排序算法，该算法可以处理有限的内存量。所以你不应该在内存问题中运行。
您应该至少有 600 GB（大小的两倍）可用磁盘空间。
您应该只使用 2 个输入文件来测试需要多长时间以及会发生什么。我的测试没有显示任何问题，但他们使用了不同的数据和 afs 服务器（这相当慢，但作为某些 HPC 文件系统提供程序是更好的仿真）：

$ ll
2147483646 big1
2147483646 big2

$ time sort -u big1 big2 -o bigsorted
1009.674u 6.290s 28:01.63 60.4% 0+0k 0+0io 0pf+0w

$ ll
2147483646 big1
2147483646 big2
 117440512 bigsorted
于 2013-02-02T16:08:49.660 回答