在不同的目录中查找具有相同名称的文件并计数重复项

我希望你能帮助我解决以下问题。 我有24个目录,每个目录包含许多(1000年)的文件。 我想找出哪些组合的目录包含最多的重复(仅限名称)文件。 例如,如果我们只考虑4个目录

dir1 dir2 dir3 dir4

与以下目录内容

DIR1

1.fa 2.fa 3.fa 4.fa 5.fa

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个目录,所以我想我可能会使用暴力的方法。 东西沿线

  1. 统计所有24个目录中出现的所有重复文件
  2. 删除一个目录并计算重复文件的数量
  3. replace目录并放下另一个然后计数
  4. 重复所有目录
  5. 获得23个目录的子集与最大数量的重复文件
  6. 重复上面的2-5,并保留22个目录与大多数重复的文件
  7. 重复,直到只剩下2个目录
  8. select最大重复文件数量的目录组合

如果有人有这样做的话,我会非常感谢一些build议。 我想使用fdupesdiff但不能弄清楚如何parsing输出和总结。

我用algorithm标记你的问题,因为我不知道任何现有的bash / linux工具可以帮助你直接解决这个问题。 最简单的方法是用Python,C ++或Java等编程语言构造算法,而不是使用bash shell。

这就是说,这里有一个高水平的分析你的问题:乍一看,它看起来像一个最小集封面问题,但它实际上分为2个部分:


第1部分 – 什么是要覆盖的文件集?

您想要查找涵盖最多重复文件的目录组合。 但首先你需要知道你的24个目录中最大的重复文件是什么。

由于2个目录之间的文件交集总是大于或等于与第3个目录的交集,所以你要遍历所有的目录对,找出最大交集集是什么:

 (24 choose 2) = 276 comparisons 

你找到了最大的交集,并把它用作你实际想要覆盖的集合。


第2部分 – 最小设置覆盖问题

这是一个在计算机科学中研究得很好的问题 ,所以你最好从比我更聪明的人的着作中读书。

我唯一需要注意的是这是一个NP完全问题 ,所以它不是微不足道的。


这是我能做的最好的事情来解决您的问题的原始形式,但我有一种感觉,它实际上需要完成的东西是矫枉过正的。 你应该考虑用你需要解决的实际问题更新你的问题。

在shell中计算重复的文件名称:

 #! /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 

./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 

我们可以为所有这24个目录创建哈希表吗? 如果文件名只是数字,散列函数将非常容易设计。

如果我们可以使用散列表,搜索和查找重复将会更快。

只是为了好奇,我做了一些简单的测试: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() 

正如Richard所提到的,通过使用散列表(或在python中设置),我们可以加快速度。 两个交集是O(min(len(set_a),len(set_b))) ,我们必须做N(N-1)/2=720比较。