2

我有一个大约 43GB 的非常大的文本文件，我用它来处理它们以生成另一个不同形式的文件。而且我不想设置任何数据库或任何索引搜索引擎

数据为 .ttl 格式

<http://www.wikidata.org/entity/Q1000> <http://www.w3.org/2002/07/owl#sameAs> <http://nl.dbpedia.org/resource/Gabon> .
<http://www.wikidata.org/entity/Q1000> <http://www.w3.org/2002/07/owl#sameAs> <http://en.dbpedia.org/resource/Gabon> .
<http://www.wikidata.org/entity/Q1001> <http://www.w3.org/2002/07/owl#sameAs> <http://lad.dbpedia.org/resource/Mohandas_Gandhi> .
<http://www.wikidata.org/entity/Q1001> <http://www.w3.org/2002/07/owl#sameAs> <http://lb.dbpedia.org/resource/Mohandas_Karamchand_Gandhi> .

目标正在从共享同一主题的所有三元组中生成所有组合：

例如对于主题 Q1000 ：

<http://nl.dbpedia.org/resource/Gabon> <http://www.w3.org/2002/07/owl#sameAs> <http://en.dbpedia.org/resource/Gabon> .
<http://en.dbpedia.org/resource/Gabon> <http://www.w3.org/2002/07/owl#sameAs> <http://nl.dbpedia.org/resource/Gabon> .

问题： 开始的虚拟代码以复杂度 O(n^2) 进行迭代，其中 n 是 45GB 文本文件的行数，不用说这样做需要数年时间。

我想优化什么：

  1. 加载 HashMap [String,IntArray] 以索引每个键的外观行，并使用任何库按行号访问文件，例如：

    Q1000 | 1,2,433
    Q1001 | 2334,323,2124

缺点是索引也可能比较大，考虑到我们将有另一个索引用于具有特定行号的访问，加上重载我没有尝试性能

  1. 为每个键创建一个文本文件，就像Q1000.txt所有三元组一样包含主题Q1000并逐个迭代它们并进行组合

缺点：这似乎是最快的，也是内存消耗最少的，但肯定会创建大约 1000 万个文件并访问它们将是一个问题，是否有替代方案？

我正在scala为任务使用脚本

4

2 回答 2

3

将 43GB 的文件分块放入内存中并按主题分类。分别编写块。

对块运行合并排序（按主题排序）。这真的很简单：你有两个文件的输入迭代器，你写出输入较少的那个，然后再次从那个输入中读取（如果还有的话）。

现在你只需要通过排序的数据来收集主题组。

应该占用 O(n) 空间和 O(n log n) 时间，对于这种事情你应该能够负担得起。

于 2013-07-19T06:47:15.523 回答
1

一个可能的解决方案是使用一些现有的map-reduce库。毕竟，您的任务正是 map-reduce 的用途。即使您不在多台机器上并行计算，主要优点是它可以为您处理拆分和合并的管理。

有一个有趣的库Apache Crunch with Scala API。我自己没有使用过，但它看起来可以很好地解决你的问题。您的台词将根据他们的主题进行拆分，然后

于 2013-07-19T07:26:30.773 回答