候補を重複ファイルのグループにする

はじめに

候補フィンガープリントはアーカイブ検索の負担を減らしますが、内容の同一性を証明するものではありません。実際のバイトで確認し、各重複グループの相対パスをすべて残す、読み取り専用の検索ツールを完成させます。

前のラボのバイナリ読み取りと SHA-256、および Java のクラス、リスト、例外を理解していることを前提とします。このラボは独立して初期化され、完成済みのダイジェストと新しいギャラリーのコピーが用意されています。グループ化を自分で実装し、ディレクトリ、レポート、起動のアダプターは用意済みです。著者の所要時間見積もりは 55 分です。

各候補を実際のバイトで確認する

このステップでは、候補となる事実から完全な重複グループを作ります。WebIDE を開き、Terminal > New Terminal を選び、独立した作業領域に移動します。

cd /home/labex/project/duplicates

./run.sh Sample

実際の PNG デコーダーで、名前が異なっても同じバイトを持つこと、同じサイズでも異なるバイトを持つことを再確認します。起動スクリプトは毎回新しい一時ビルドを使います。コンパイラー/JVM 子プロセスは C.UTF-8 と明示的な UTF-8 のソース・テキスト設定を使い、ターミナルの設定は変えません。

公開アダプターと初期実装を読みます。

cat src/Digester.java src/Finder.java

Finder.find(Path root, Digester candidates) は重複グループのリストを返し、各グループには root からの相対パスとして全メンバーを含める必要があります。root.relativize(path) が相対パスを作り、root.resolve(relative) で読み取り用の場所を再取得します。sameBytes(left, right) が比較するのは名前ではなく内容です。これらの公開入口を保ってください。内部の補助処理やコレクションの構成は変更できます。

以下の実装では Map を使い、候補キーとその可能なグループを対応付けます。キーはサイズとダイジェストを組み合わせます。containsKey はキーの有無を調べ、put は初期値を登録し、get は値を取得します。異なる内容でも候補フィンガープリントが一致する可能性があるため、各キーはバイトで確認済みのグループのリストを持ちます。List<List<Path>> は、要素がパスのリストであるリストです。

各ファイルについて、そのバケット内の既存グループそれぞれの代表パスと比較します。本当に一致すれば新しいパスを追加し、一致しなければ別のサブグループを作ります。placed は現在のパスが既にグループに入ったかを記録し、break は一致後に内側の探索を終了して、1 つのパスが重複追加されるのを防ぎます。2 つ以上のパスを持つグループだけをレポートに出します。2 メンバーで止めてはいけません。3 つ目のコピーも確認すべき独立したパスです。

sameBytes はまず長さが違う場合を拒否し、それから両ファイルを読みます。read() は 1 バイトを 0 から 255 の整数で返し、末尾では -1 を返します。異なるバイトがあれば false、同時に末尾へ達すれば true を返します。両ストリームは try-with-resources で閉じます。1 バイトずつ読む方法は、この小さな教材例を理解しやすくします。バッファーや配列全体でのバイト比較も有効な代替で、それぞれメモリと性能のトレードオフがあります。

before マップは各 Path と元のメタデータを対応付けます。before.keySet() は最後の変更確認に使うパスキーを返し、buckets.values() は結果を組み立てるために保存済みの候補サブグループのリストを返します。属性アダプターは読み取り前のサイズ、変更時刻、ファイル識別情報を記録し、検出した変更を拒否します。ツリーをロックしたり固定したりするわけではありません。走査中の入力は安定させてください。同時書き込み、シンボリックリンク、特殊ファイルは対象外です。同じファイルへのハードリンクであっても、異なるパスはすべて重要です。ファイル識別情報は変更検出のためだけに使い、パスを除外する根拠にしません。

src/Finder.java を置き換えます。前のラボと同様、引用符付き here-document は文字列をそのまま書き込みます。終了マーカー JAVA は単独の行に置きます。> が置き換えるのはこのソースファイルだけです。

cat > src/Finder.java <<'JAVA'
import java.io.IOException;
import java.io.InputStream;
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.*;

public class Finder {
    public static boolean sameBytes(Path left, Path right) throws IOException {
        if (Files.size(left) != Files.size(right)) return false;
        try (InputStream a = Files.newInputStream(left);
             InputStream b = Files.newInputStream(right)) {
            int value;
            while ((value = a.read()) != -1) {
                if (value != b.read()) return false;
            }
            return b.read() == -1;
        }
    }
    public static List<List<Path>> find(Path root, Digester candidates) throws IOException {
        Map<String, List<List<Path>>> buckets = new LinkedHashMap<>();
        Map<Path, BasicFileAttributes> before = new LinkedHashMap<>();
        for (Path path : Inputs.files(root)) {
            BasicFileAttributes facts = Inputs.attributes(path);
            before.put(path, facts);
            String key = facts.size() + ":" + candidates.digest(path);
            Inputs.unchanged(path, facts);
            if (!buckets.containsKey(key)) buckets.put(key, new ArrayList<>());
            List<List<Path>> groups = buckets.get(key);
            boolean placed = false;
            for (List<Path> group : groups) {
                if (sameBytes(path, root.resolve(group.get(0)))) {
                    group.add(root.relativize(path));
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                List<Path> group = new ArrayList<>();
                group.add(root.relativize(path));
                groups.add(group);
            }
        }
        for (Path path : before.keySet()) Inputs.unchanged(path, before.get(path));
        List<List<Path>> result = new ArrayList<>();
        for (List<List<Path>> groups : buckets.values()) {
            for (List<Path> group : groups) {
                if (group.size() > 1) result.add(group);
            }
        }
        return result;
    }
}
JAVA

用意された Main は new Sha256() を渡して同じ find を呼び出します。テストでは、異なるファイルにも同じ候補値を返す別の Digester を渡せます。これは制御された候補衝突テストであり、本物の SHA-256 衝突ではありません。最後のバイト比較で異なる内容を分離する必要があります。呼び出されない比較メソッドを書くだけでは不十分です。

走査ルートの外に実際のレポートを生成します。

./run.sh Main data/gallery reports/groups.tsv

Scan complete: 3 duplicate groups が表示されるはずです。コンパイルに失敗したら、src/Finder.java の指摘された行を修正し、保存して再実行します。データを変更する前に、波括弧とメソッドのシグネチャを確認してください。

グループ全体を読み、変更後に再実行する

このステップでは、完成したレポートを読み、現在のバイトに応じて結果が変わることを確認します。同じ WebIDE 統合ターミナルで、/home/labex/project/duplicates のまま続けます。

cat reports/groups.tsv

UTF-8 TSV のヘッダーは GROUP、続いて PATH です。各行が 1 つの相対パスを示し、同じグループラベルで同じ内容を結びます。ラベル自体はファイルの識別情報ではなく、順序も重要ではありません。赤い画像のグループには 3 つのパスがすべて必要です。2 つの空ファイルで 1 グループ、最後のバッファーが一部だけ埋まる 2 つのバイナリファイルで別のグループになります。青い画像と、同名でも内容が違う readme は重複ではありません。Explorer の duplicates/data/gallery で各メンバーを探せます。入力は削除されません。

ギャラリーの原本を保ったまま、work の使い捨てコピーで変更を試します。mkdir -p は必要に応じて練習用ディレクトリを作り、cp はファイルを新しいパスへコピーします。

mkdir -p work/mini

cp data/gallery/red.png work/mini/first.png

cp data/gallery/copies/renamed.png work/mini/second.png

./run.sh Main work/mini reports/practice-before.tsv

重複グループが 1 つ得られるはずです。次に printf で引用符内のテキストと改行を書き込み、> で練習用の 2 つ目のファイルだけを置き換えます。もはや PNG ではないため、拡張子は内容の証拠になりません。

printf 'changed\n' > work/mini/second.png

./run.sh Main work/mini reports/practice-after.tsv

重複グループはゼロになるはずです。レポートにはヘッダーが残ります。

cat reports/practice-after.tsv

正常な空の結果と、走査の失敗は異なります。次のコマンドでは、意図的に入力ツリー内へのレポート出力を要求します。Scan failed と終了ステータス 2 が表示され、新しい入力ファイルは作られないはずです。

./run.sh Main data/gallery data/gallery/report.tsv

出力パスを直し、ギャラリーのレポートを再生成します。

./run.sh Main data/gallery reports/groups.tsv

レポートアダプターは同じディレクトリに新しい一時ファイルを書き、走査成功後に出力パスを置き換えます。既存ハードリンクを上書き用に開かないため、レポートパスがそのリンク経由で原本のバイトを上書きすることはありません。クラッシュ時の永続性を保証するものではありません。読み取りに失敗するとコマンドは失敗し、以前のレポートは今回の成功証拠になりません。ファイルを黙って飛ばして成功を宣言してはいけません。

最終検査では隔離テストデータ上で現在のソースを実行し、実際のギャラリーレポートを読みます。完全なグループ、現在の内容、エラー、原本の保全を調べます。過去に正しかったレポートで、その後壊れたソースを正当化することはできません。

まとめ

サイズと SHA-256 で候補を絞り、実際のバイトを確認し、すべての重複パスを保持して、実際の変更後にレポートを再生成しました。正常にゼロ件のグループを得る場合と、走査が失敗する場合の違いも明確になりました。