2

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

目录 1 目录 2 目录 3 目录 4

具有以下目录内容

目录1

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

目录2

1.fa 10.fa 15.fa

目录3

1.fa 2.fa 3.fa

目录4

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

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

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

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

如果有人有办法做到这一点，我将非常感谢一些建议。我想过使用fdupes或diff但无法弄清楚如何解析输出和总结。

4

5 回答 5

3

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

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

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

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

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

(24 choose 2) = 276 comparisons

您采用找到的最大交集并将其用作您实际尝试覆盖的集合。

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

这是计算机科学中一个经过充分研究的问题，因此您最好阅读比我聪明得多的人的著作。

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

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

于 2012-11-20T17:40:17.347 回答
0

./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
于 2012-11-20T22:47:13.833 回答
0

我们可以为所有这 24 个目录创建哈希表吗？如果文件名只是数字，哈希函数将很容易设计。

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

于 2012-11-21T06:00:36.900 回答
0

计算 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
于 2012-11-20T22:11:33.703 回答
0

出于好奇，我做了一些简单的测试：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比较。

于 2012-11-21T16:15:03.363 回答