2

次の問題について教えていただければ幸いです。24 個のディレクトリがあり、それぞれに多数 (1000 個) のファイルが含まれています。重複した (名前のみの) ファイルの数が最も多いディレクトリの組み合わせを調べたいと思います。たとえば、4つのディレクトリのみを考慮する場合

dir1 dir2 dir3 dir4

次のディレクトリの内容で

dir1

1.ファ 2.ファ 3.ファ 4.ファ 5.ファ

dir2

1.ファ 10.ファ 15.ファ

dir3

1.ファ 2.ファ 3.ファ

dir4

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. 重複ファイルの最大数を持つディレクトリの組み合わせを選択します

誰かがこれを行う方法を持っている場合、私はいくつかのアドバイスに非常に感謝しています. fdupesorを使用することを考えdiffましたが、出力を解析して要約する方法がわかりません。

4

5 に答える 5

3

algorithmこの問題を直接解決するのに役立つ既存の bash / Linux ツールを知らないため、質問にタグを付けました。最も簡単な方法は、bash シェルを使用する代わりに、Python、C++、または Java などのプログラミング言語でこのアルゴリズムを構築することです。

そうは言っても、問題の高レベルの分析は次のとおりです。一見すると、最小セット カバーの問題のように見えますが、実際には 2 つの部分に分けられます。

パート 1 - カバーするファイルのセットは?

最も多くの重複ファイルをカバーするディレクトリの組み合わせを見つけたいと考えています。ただし、最初に、24 個のディレクトリ内にある重複ファイルの最大セットを知る必要があります。

2 つのディレクトリ間のファイルの共通点は、常に 3 番目のディレクトリとの共通点以上であるため、ディレクトリのすべてのペアを調べて、最大の共通点セットを見つけます。

(24 choose 2) = 276 comparisons

見つかった最大の交差セットを取得し、それを実際にカバーしようとしているセットとして使用します。

パート 2 - 最小集合カバー問題

これはコンピュータ サイエンスでよく研究されている問題なので、私よりもはるかに頭の良い人の著作を読んだほうがよいでしょう。

私が注意しなければならない唯一のことは、それがNP-Complete problemであるため、簡単ではありません。

これは、あなたの質問の元の定式化に対処するために私ができる最善のことですが、実際に達成する必要があることにはやり過ぎだと感じています。解決する必要がある実際の問題で質問を更新することを検討する必要があります。

于 2012-11-20T17:40:17.347 に答える
0

好奇心のために、私はいくつかの簡単なテストを行いました。それぞれに約3900個のファイル（0から9999の間の乱数）を持つ24個のディレクトリです。両方のbashスクリプトはそれぞれ約10秒かかります。これは、〜0.2sで同じことを行う基本的なPythonスクリプトです。

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

リチャードが述べたように、ハッシュテーブル（またはPythonで設定）を使用することで、処理を高速化できます。2つのセットの共通部分はO（min（len（set_a）、len（set_b）））N(N-1)/2=720であり、比較を行う必要があります。

于 2012-11-21T16:15:03.363 に答える
0

これら 24 個のディレクトリすべてのハッシュ テーブルを作成できますか? ファイル名が number だけの場合、ハッシュ関数の設計は非常に簡単になります。

ハッシュ テーブルを使用できれば、検索と重複の検出が高速になります。

于 2012-11-21T06:00:36.900 に答える
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

シェルで重複するファイル名を数えます:

#! /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 に答える