爲了快速訪問，逐行掃描大文本文件的索引

我有一個非常大的文本文件，大約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文本文件的行數，不用說這需要幾年才能完成。

了我認爲的優化：

加載一個HashMap [字符串，IntArray]外觀每個鍵和使用任何庫由行號訪問該文件，例如轉位線：

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

缺點是索引可能是比較大的還有，考慮到我們將有具體的行號訪問另一個指標，再加上超載我沒有嘗試

的性能

做一個文本文件，對所有三元像Q1000.txt每個鍵包含目標Q1000並超過他們迭代一個接一個，使組合

缺點：這似乎是最快和最少的內存消耗，但肯定會創建大約1000萬個文件並訪問它們將是一個問題，是否有替代方案？

我使用scala腳本任務

來源

2013-07-19 Hady Elsahar

可能有一個不使用數據庫的原因，但實際上你要*實施*一個。在[context]（http://stackoverflow.com/q/17739973/2390083） – Beryllium

採取43GB文件，使之與記憶和排序的主題塊。分開寫入塊。

在塊上運行合併排序（按主題排序）。這很容易：你有兩個文件的輸入迭代器，並且你輸出較少的輸入，然後再從那個文件中讀取（如果還有剩餘的話）。

現在，您只需要對經過排序的數據進行一次傳遞即可收集主題組。

應該花費O（n）空間和O（n log n）時間，對於這種事情你應該能夠負擔得起。

來源

2013-07-19 06:47:15

中的相關問題，使最小複雜度o（nlogn）中的合併排序，這將需要數量的文件等於主題數量〜10M文件，最大的文件可以創建它接近32K這是非常遠離 –

@HadyElsahar - 'n'是行數，而不是主題的數量。這個策略是獨立於主題的數量。無論文件的數量如何，它都是標準的分而治之，O（n log n）。 –

一個可能的解決方案是使用一些現有的map-reduce庫。畢竟，你的任務正是map-reduce的目標。即使您沒有在多臺機器上並行計算，主要優勢在於它可以爲您處理分割和合並的管理。

有一個有趣的圖書館Apache Crunch與Scala API。我自己並沒有使用它，但它看起來可以很好地解決你的問題。你的線將根據他們的主題分割，然後

來源

2013-07-19 07:26:30

爲了快速訪問，逐行掃描大文本文件的索引

回答

相關問題