如何對一個大文本進行按每行去重操作?

01-01

文本大小遠超過可用內存, 目前我想到兩種方法, 1.將大文本拆分成數量眾多的小文本, 實際使用速度非常慢, 瓶頸在 io 上. 2. 將大文本中的數據存入資料庫, 讓資料庫替我實現去重操作. 有沒有更好的方法(or 演算法)?

去重沒必要排序。你要求保持行之間的順序不？你試試直接讀取行、哈希之後扔 KV 資料庫找看重不重。

另外不知道你是怎麼拆的，不過瓶頸在 I/O 上你只能上 SSD 了。另外你是不是用的機械硬碟但是給拆成隨機讀了？

在實際的應用中如果能有一個分散式的平台，就不是問題了。

另外這是一個經典的面試題，面試題里要求只用一個普通的PC來做。那麼可以這樣子：

隨便找一個字元串hash函數，值域在1-n之間。（n的設定稍後再說）

然後根據hash的值創建n個文件，掃描原文件，每一行都算出對應的hash值，輸出到對應的文件中去。

這樣子如果原來的的文件不是非常bias，那麼就會比較均勻的分到n個文件中去。然後對於每個文件，期望它的大小可以讀入到內存中去，在內存中去重。這一步就有很多演算法了，都放到一個hashset里可能是最省力的。

關於n的大小可以自己調整，目標是要讓小文件能讀入到內存。比如處理1T的文件，就可以取n＝1000，使得每個小文件期望只有1G。

正確性：如果兩個字元串的hash值不相等，那麼字元串也一定不相等。也就是說相同的字元串必然會在一個文件中。那麼對於每個小文件單獨去重是沒有問題的，沒有遺漏。

效率：空間上需要多一倍的磁碟，時間是就是磁碟讀寫兩次，內存里的操作也是O(n)。總的來說，時空複雜度都是O(n)

更多的考慮：

如果不幸某一個小文件還是很大，不能讀入到內存，那麼可以考慮對這個小文件重複上述演算法，他就會變的更小。

如果原來的文件非常bias，極限情況比如就是幾個字元串一直在重複，那麼就會導致小文件還是很大，並且重複這個演算法永遠也不可能使他變小了。那麼可以先把文件分成n份，每份去重，然後再進入到原來的演算法環節。這樣子就可以保證一個字元串最多出現n次了。

你說的都是外部排序，不同的實現方式

提供一個思路，直接上SSD，然後用外排。

我最近也在干這事。

你首先要考慮壓縮後的文件是否能放在內存里，如果OK，awk一行就搞定了。

否則，上Hadoop。或者找個長假，跑個sort | uniq。

你的大文件有多大？對性能要求有多高？

如果是單機，允許慢一點的話，

$ sort foo.txt | uniq

妥妥的。

update:

上述方法非常安全，中間數據會存在磁碟上，不會撐爆內存，對付數十 G 大小的文件只是稍微慢一點而已。

如果你有很多台機器和很多內存，可以上 Spark, 這樣在 RDD 上作一個 distinct 變換就好了。

不過，如果你只有少數幾台機器，Spark 上算可能還不如上面簡單粗暴的辦法快。

每行內容哈希，構造KV數據結構，存入分散式緩存系統，如Redis,取Redis的鍵值對，去重結束。

不是可以直接按行為單位讀到內存里么……

有多大，大不了上Hadoop，一個MR搞定

剛看到一個思路，利用bigmap去重，無需排序。https://www.zhihu.com/question/38206659/answer/76484782?utm_source=wechat_sessionutm_medium=socialfrom=singlemessage

以上是純數字的。帶字元可以用以下方法，網上轉載。

掃一遍文件，對每一行計算一個MD5或者SHA-1值，在內存構建trie樹。鑒於數據量很大，生成的MD5值應該存在許多前綴，所以採用trie可以節省空間（如果想進一步節省空間，可以採用三向單詞查找樹，比trie分支更少），而且trie樹的深度不會超過MD5值的長度，幾十而已，每次查找或者插入MD5值都是個時間複雜度為常數的操作。向trie添加某個MD5值時如果發現該值已經存在，則拋棄目前掃描的行；如果不存在，則把MD5值插入trie樹，把當前掃描行寫入結果文件（這個文件保存所有不重複的行）。這樣，掃描一遍文件就能實現去重。

文本行去重化大數據工具 130Gb 20億行數據 60分鐘即可完成去重操作最快的單機版軟體

dereplication 大數據文件行去重化工具
本軟體特點及其描述：
1.平均處理速度60Mb/s(讀寫速度)，例如130Gb的txt文件，大約60分鐘即可完成文本行去重；
2.處理最大文本（txt或者csv）文件的能力------沒有行數限制，沒有容量限制，輕鬆處理超過1000Gb的文本文件；
3.一次性可合併去重處理多個大數據文件，可以對歷史數據進行持續更新升級，對，沒錯，是對您的大數據文件進行升級；
4.自動文件編碼探測；
5.本軟體是目前互聯網上銷售的單機版文本行去重軟體中去重速度最快的軟體，其它專業性的軟體公司開發的類似產品最快處理速度才5Mb/s而已；
6.標準版與極速版合二為一，實時的百分比處理進度條更新，讓您目測整個操作過程大約需要的時間；
7.獨特的拆分演算法，巧妙構思的快速數學計算模型，讓您的CPU利用率幾乎一直處於50%的線性水平，標準版幾乎能讓內存消耗處在7Gb的線性水平；
8.文件的大小與硬體性能之間關係：是線性關係，對，您沒看錯，不是指數關係，所以處理大數據的能力非常強悍！

以下測速環境：
操作系統：Windows 10 x64
CPU型號：Intel(R) Core(TM) i5-4570 CPU @ 3.2GHz 4核處理器
固態硬碟型號：GLOWAY STK512GS3-S7
內存型號：金士頓HyperX 8Gb DDR3 1600 4條內存，實際上只使用了1條8Gb的內存容量

標準版文本行去重化處理速度（讀/寫）硬體(固態硬碟，CPU，內存條)性能界面截屏：

可以取到每一行的hash值，然後以hash值作為名字創建文件，將內容寫進文件裡邊，寫進文件裡邊的時候先判斷文件裡邊是否有這個字元串了，有就不寫了。效果主要看hash函數

我來說說我的意見，由於整理某些東西，我處理過幾十個G的大文本，需要去重，這種文本讀到內存里肯定是要爆的。我的方法是先使用分治的方法排序，為什麼要排序，因為排序過後你才能分別去重，而且這樣你無需去搭建一些莫名其妙的其他系統中間件什麼的，簡直折騰。

上代碼，這個腳本來自stackoverflow，使用sort對文件進行並行排序，效率比直接用sort高得多了

#! /bin/ksh


MAX_LINES_PER_CHUNK=5000000

ORIGINAL_FILE=$1

SORTED_FILE=$2

CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split.

SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted
usage ()

{

     echo Parallel sort

     echo usage: psort file1 file2

     echo Sorts text file file1 and stores the output in file2

     echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines

     echo  and each chunk will be sorted in parallel

}
# test if we have two arguments on the command line

if [ $# != 2 ]

then

    usage

    exit

fi
#Cleanup any lefover files

rm -f $SORTED_CHUNK_FILES &> /dev/null

rm -f $CHUNK_FILE_PREFIX* &> /dev/null

rm -f $SORTED_FILE
#Splitting $ORIGINAL_FILE into chunks ...

split  -l $MAX_LINES_PER_CHUNK -a 4  $ORIGINAL_FILE $CHUNK_FILE_PREFIX
for file in $CHUNK_FILE_PREFIX*

do

    sort $file &> $file.sorted

done

wait
#Merging chunks to $SORTED_FILE ...

sort -m $SORTED_CHUNK_FILES &> $SORTED_FILE

#Cleanup any lefover files rm -f $SORTED_CHUNK_FILES &> /dev/null rm -f $CHUNK_FILE_PREFIX* &> /dev/null

其中MAX_LINES_PER_CHUN是你排序的分塊大小，看你自己的配置修改，很快就能排序完。排序完之後，對排序完的文件按你的內存大小進行分割然後分別去重再合併就行了。前面的排序就是為了保證重複的行被分到同一個文件中去的，不用擔心合併後的文件還有重複。

1、外部排序 (Single box)

2、Terasort in Hadoop. (Cluster)

java里貌似有個演算法庫正則匹配