在不同的目錄中查找具有相同名稱的文件並計數重複項

我希望你能幫助我解決以下問題。我有24個目錄，每個目錄都包含許多（1000個）文件。我想找出哪些目錄組合包含最多的重複（僅限名稱）文件。例如，如果我們只考慮4個目錄在不同的目錄中查找具有相同名稱的文件並計數重複項

DIR1 DIR2 DIR3 dir4

與下面的目錄內容

DIR1

1.fa 2.fa 3.fa 4.fa 5。發

DIR2

1.fa 10.fa 15.fa

DIR3

1.fa 2.fa 3.fa

dir4

1.fa 2 .fa 3.fa 5.fa 8.fa 10.fa

因此，目錄dir1和dir4的組合包含最重複的文件（4）。

問題變得非常大，24個目錄，所以我想我可能會使用暴力方法。沿

計數線發生在所有24個目錄
刪除一個目錄和計數的重複文件數量
更換目錄，再下降一個再算上數
所有重複文件的東西重複所有目錄
得到23個目錄，最大數量的重複文件
重複的子集上述2-5，並保持22個目錄與大多數重複文件
重複，直到只有2個目錄留下
選擇的目錄與重複的文件

最大數量的組合。如果任何人有這樣做我會爲一些建議非常感謝的一種方式。我想過使用fdupes或diff，但無法弄清楚如何解析輸出和彙總。

來源

2012-11-20 alexd106

你僅限於shl腳本，或者你可以使用Perl/Python嗎？ – amphibient

我沒有很多perl或python的經驗，但我願意放手！ – alexd106

當你說'哪個目錄的組合？'你是指'哪2個目錄'，或者「什麼是最少數量的目錄......」？如果「組合目錄」的編號沒有限制，那麼「O（1）」答案總是隻取所有目錄，並且總是包含大量重複文件。如果你的意思是選擇2個目錄，那麼在'P'時間就有聰明的解決方案。如果你的意思是選擇重複次數最少的目錄集，這可以減少到最小集合覆蓋問題，並且是'NP' –

我用algorithm標記你的問題，因爲我不知道任何現有的bash/linux工具可以幫助你直接解決這個問題。最簡單的方法是用Python，C++或Java等編程語言構造算法，而不是使用bash shell。

話雖這麼說，這裏是你的問題的一個高層次的分析：乍一看它看起來像一個的最小值設置覆蓋問題，但它實際上分爲兩個部分：

第1部分 - 什麼是要覆蓋的文件集？

您想查找覆蓋最多重複文件的目錄組合。但首先你需要知道24個目錄中最大的重複文件集是多少。

由於文件2個目錄之間的交集總是大於或等於與第三目錄的路口，你經歷所有對目錄，並找到最大交集就是：

(24 choose 2) = 276 comparisons

你找到找到的最大交集，並將其用作實際上要覆蓋的集合。

部分 - 最小集合覆蓋問題

這是一個well-studied problem in computer science，讓你更好的服務，從the writings of people much smarter than I閱讀。

我唯一要注意的是它是NP-Complete problem，所以它不是微不足道的。

這是我能做的解決您的問題的原配方中最好的，但我有一種感覺，這是矯枉過正你真正需要完成。你應該考慮用你需要解決的實際問題來更新你的問題。在外殼

來源

2012-11-20 17:40:17

感謝您的意見。我正在考慮上面列出的強力方法，因爲我並不真的需要一個「確切」的答案，只是想知道哪些文件夾要給我最多的類似文件。感謝您的時間 – alexd106

計數重複的文件名：

#! /bin/sh 

# directories to test for 
dirs='dir1 dir2 dir3 dir4' 

# directory pairs already seen 
seen='' 

for d1 in $dirs; do 
    for d2 in $dirs; do 
     if echo $seen | grep -q -e " $d1:$d2;" -e " $d2:$d1;"; then 
      : # don't count twice 
     elif test $d1 != $d2; then 
      # remember pair of directories 
      seen="$seen $d1:$d2;" 
      # count duplicates 
      ndups=`ls $d1 $d2 | sort | uniq -c | awk '$1 > 1' | wc -l` 
      echo "$d1:$d2 $ndups" 
     fi 
    done 
# sort decreasing and take the first 
done | sort -k 2rn | head -1

來源

2012-11-20 22:11:33

./count_dups.sh：

1 files are duplicated Comparing dir1 to dir2. 
3 files are duplicated Comparing dir1 to dir3. 
4 files are duplicated Comparing dir1 to dir4. 
1 files are duplicated Comparing dir2 to dir3. 
2 files are duplicated Comparing dir2 to dir4. 
3 files are duplicated Comparing dir3 to dir4.

./count_dups.sh | sort -n |尾-1

4 files are duplicated Comparing dir1 to dir4.

使用腳本count_dups.sh：

#!/bin/bash 

# This assumes (among other things) that the dirs don't have spaces in the names 

cd testdirs 
declare -a DIRS=(`ls`); 

function count_dups { 
    DUPS=`ls $1 $2 | sort | uniq -d | wc -l` 
    echo "$DUPS files are duplicated comparing $1 to $2." 
} 

LEFT=0 
while [ $LEFT -lt ${#DIRS[@]} ] ; do 
    RIGHT=$(($LEFT + 1)) 
    while [ $RIGHT -lt ${#DIRS[@]} ] ; do 
     count_dups ${DIRS[$LEFT]} ${DIRS[$RIGHT]} 
     RIGHT=$(($RIGHT + 1)) 
    done 
    LEFT=$(($LEFT + 1)) 
done

來源

2012-11-20 22:47:13

我們可以創建一個哈希表，所有這些24個的目錄？如果文件名只是數字，散列函數將很容易設計。

如果我們可以使用散列表，搜索和查找重複會更快。

來源

2012-11-21 06:00:36 Richard

只是爲了好奇心，我做了一些簡單的測試：24個目錄中每個大約有3900個文件（0到9999之間的一個隨機數）。這兩個bash腳本每個都需要大約10秒。下面是一個基本的Python腳本做同樣的在0.2秒〜：

#!/usr//bin/python 

import sys, os 

def get_max_duplicates(path): 
    items = [(d,set(os.listdir(os.path.join(path,d)))) \ 
     for d in os.listdir(path) if os.path.isdir(os.path.join(path, d))] 
    if len(items) < 2: 
     # need at least two directories 
     return ("","",0) 
    values = [(items[i][0],items[j][0],len(items[i][1].intersection(items[j][1]))) \ 
     for i in range(len(items)) for j in range(i+1, len(items))] 
    return max(values, key=lambda a: a[2]) 


def main(): 
    path = sys.argv[1] if len(sys.argv)==2 else os.getcwd() 
    r = get_max_duplicates(path) 
    print "%s and %s share %d files" % r 

if __name__ == '__main__': 
    main()

正如理查德所說，採用哈希表（或蟒蛇設置），我們可以加快速度。兩組的交集是O(min(len(set_a), len(set_b)))，我們必須做N(N-1)/2=720比較。

來源

2012-11-21 16:15:03

在不同的目錄中查找具有相同名稱的文件並計數重複項

回答

相關問題