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

Question

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

dir1 dir2 dir3 dir4

具有以下目录内容

dir1

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

dir2

1.fa 10fa 15fa

dir3

1.fa 2.fa 3.fa

dir4

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

因此，目录dir1和dir4的组合包含最多重复的文件(4)。

24个目录的问题变得相当大，所以我想我可能会使用蛮力方法。类似的东西

1. 统计所有24个目录中出现的所有重复文件
2. 删除目录并计算重复文件的数量
3. 替换目录并删除另一个，然后计数
4. 对所有目录重复
5. 获取具有最大重复文件数的23个目录的子集
6. 重复上面的2-5，并保留22个目录中重复文件最多
7. 重复，直到只剩下2个目录
8. 选择具有最大重复文件数的目录组合

如果有人能做到这一点，我将非常感谢你的建议。我想过使用fdupes或diff，但不知道如何解析输出和总结。

Answer 1

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

话虽如此，以下是对您的问题的高级分析：乍一看，它看起来像是一个最小集封面问题，但实际上它分为两部分：

---

第1部分-要涵盖的文件集是什么

您希望找到覆盖最多重复文件的目录组合。但首先你需要知道在你的24个目录中，重复文件的最大数量是多少。

由于两个目录之间的文件交集总是大于或等于与第三个目录的交集，因此您可以遍历所有目录对，找到最大交集集：

(24 choose 2) = 276 comparisons

取找到的最大交集集，并将其用作实际要覆盖的集。

---

第2部分-最小集覆盖问题

这是计算机科学中一个研究得很好的问题，所以你最好阅读比我聪明得多的人的文章

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

---

这是我能做的最好的事情来解决你问题的原始公式，但我觉得这对你实际需要完成的事情来说太过分了。你应该考虑用你需要解决的实际问题来更新你的问题。

Answer 2

计算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

Answer 3

/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|排序-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

Answer 4

我们能为这24个目录创建哈希表吗？如果文件名只是数字，那么散列函数将非常容易设计。

如果我们可以使用哈希表，它将更快地搜索和查找重复。

Answer 5

为了好奇，我做了一些简单的测试：24个目录，每个目录中大约有3900个文件(0到9999之间的随机数)。两个bash脚本每个大约需要10秒。以下是一个基本的python脚本，它在~0.2s:中也能做到这一点

#!/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比较。