4

鉴于：

  • 包含数百万行的文件a.txt（例如，每行一个句子）（2.6 GB！
  • b.txt包含 830k 行的文件[word1] [word2]

问题：

如何在巨大的文本文件中为每个 830k 元组（w1，w2）中的每一个执行最有效的 word1 替换 word2？

像 sed、perl、python 等天真的方法需要数周时间才能完成。是否有（可能基于并行化的）方法来执行替换负载？

4

5 回答 5

5

我会用 python 来做，但如果你得到正确的算法，任何其他语言都可以做这个工作。整个技巧是将单词对（文件 b.txt）保存在内存中，并一次性浏览大文件。由于 I/O 操作比从 RAM 读取慢得多，因此这种方法的性能将是 O(file1) + O(file2)

在伪代码中：

myMap = {}
for line in fileB:
  myMap[1st word of line] = 2nd word of line

for line in fileA
  for word in line
    if myMap contains word
      replace word with myMap[word]

我想这是你能得到的最快的。

于 2009-04-15T16:22:34.317 回答
0

将文件拆分成更小的块。您可能会占用大量内存空间，除了在内存或磁盘上移动位之外什么都不做。

这类似于连接/替换字符串数组而不是单个字符串的速度要快得多。

它的唯一技巧是确保您在文件中放置中断的位置不是一个很好的匹配，这是相对微不足道的。事实上，如果你可以通过行来做到这一点，那就更好了，不需要检查匹配项。

我也觉得奇怪的是它需要 PERL 数周。有一些轶事证据表明它可以在不到一个小时的时间内处理完：

事实上，他们在第二个链接中谈到 1gb 文件需要 2 分钟。

而且我不会怀疑替换操作应该比文件的复制操作花费更长的时间，毕竟，它只是拾取文件的块并在移动它们时替换一些位。它应该能够以接近复制它们的速度动态替换它们（因为它们已经在内存中）

于 2009-04-15T16:14:57.577 回答
0

按单词对查找/替换对列表进行排序以查找 [word1]

然后通读文件，将每一行拆分为单词，并在要替换的单词列表中查找每个单词（使用像二进制搜索这样的高效方法）。

应该是可以实现的。

于 2009-04-15T16:19:15.710 回答
0

我同意 idrosid 的回答，即仅将这些对加载到内存中，然后通过文件流式传输。如果您确实拥有大量数据（大量 Gb）并且您没有机器资源来按您希望的速度执行此操作，那么 Amazon 的新 Elastic Hadoop 服务将是一个很好的解决方案。一旦你有了一个适用于小文件的简单可执行文件，使用 Hadoop 的 Map Reduce 框架将其扩展到海量数据将非常简单。

于 2009-04-15T16:27:39.513 回答
-1

我会用 SQL 来做。

创建一个包含两列（dataline、sequence）的表，并将a.txt放入其中（每行一行）

然后创建第二个表，同样有两列（word1 和 word2）并将 b.txt 读入其中（同样，每个表行一行）

生成基于table2更新table1的update语句

运行sql语句

完成后，将第一个表读回文件中

于 2009-04-15T16:14:24.180 回答