Глава 29. Поиск одинаковых файлов

Идеи реализации
	Глава 29. Поиск одинаковых файлов

Идеи реализации

Конечно же не зря мы изучали в главах 28. «Вывод содержимого директории» и 27. «Сравнение файлов» поиск файлов в директории и сравнение файлов. Всё это нам пригодится при поиске одинаковых файлов.

Процедуру find мы позаимствуем с небольшими изменениями, а процедуру compareFiles дословно скопируем в будущую программу.

Наивная группировка

Разумеется, первое, что должна сделать программа, это составить список файлов на основании параметров командной строки. В результате работы программы файлы должны быт разбиты на группы, в каждой из которых файлы одинаковы, а файлы из разных групп различны. В конце работы выводятся имена файлов по группам (если в группе окажется более одного файла), а сами группы отделяются друг от друга пустой строкой. Для хранения групп идеально подойдёт массив, а сами группы можно реализовать как ссылки на анонимные массивы.

Можно поступить следующим образом: сначала помещать все файлы из списка в одну группу. Затем сравнивать с первым файлом в этой первой (и единственной) группе второй, третий, и так далее. Файлы, которые равны первому, остаются в группе, а те, которые не совпали с первым, перебрасываются в следующую. Когда такая обработка первой группы будет завершена, может появиться вторая. В ней тоже начинаем сравнения всех файлов, начиная со второго, с первым в группе. Те, что не совпали, отправятся в третью группу. Весь этот процесс должен закончиться, когда будет обработана самая последняя группа.

Проиллюстрируем этот алгоритм на примере шести файлов a, b, c, d, e, f, среди которых есть равные — b и d, c и f.

Perl
(['a', 'b', 'c', 'd', 'e', 'f'])
(['a'], ['b', 'c', 'd', 'e', 'f'])		после обработки первой группы…
(['a'], ['b', 'd'], ['c', 'e', 'f'])	второй…
(['a'], ['b', 'd'], ['c', 'f'], ['e'])	третьей…
(['a'], ['b', 'd'], ['c', 'f'], ['e'])	четвёртой

Хеширование и гнездование

Обратите внимание на тот факт, что пришлось сравнить каждый файл с каждым. Если действовать подобным образом при группировке большого количества ( $N$ ) файлов, придётся, как нас учит комбинаторика, проделать $C_{N}^{2} = \frac{N (N - 1)}{2} \approx \frac{N^{2}}{2}$ сравнений. Так что попытка найти одинаковые файлы среди более чем миллиона (именно столько их, к примеру, в нашем компьютере) заведомо обречена на провал. Сравнение файлов — весьма дорогостоящая операция, она требует открытия, чтения и закрытия пары сравниваемых файлов. Кроме того, некоторые сравнения могут затянуться из-за того, что файлы одинаковы (чтобы в этом убедиться, их придётся дочитать до конца), или различия в файлах появятся далеко от их начала. Хотя доля таких случаев невелика, каждый из них катастрофически замедлит выполнение программы (сравнения одинаковых файлов в любом случае не избежать). Но, даже если бы сравнение осуществлялось бы очень быстро, выполнение полтриллиона попарных сравнений для миллиона файлов — дело безнадёжное. Даже последовательный вывод полтриллиона первых натуральных чисел на экран занимает на нашем компьютере более 400 суток (мы проделали эксперимент!).

Всё это означает, что нам следует отказаться от тотального попарного сравнения файлов, и не сравнивать те файлы, которые по тем или иным причинам заведомо не могут быть равными.

Тут поможет хеширование (не путать с кэшированием), приём, очень широко применяемый в программировании. На основании содержимого каждого файла вычисляется некоторая величина, называемая хеш-функцией. Для одинаковых файлов эта величина будет равной. Файлы с различным значением хеш-функции заведомо различны, и сравнивать их между собой уже не нужно. Хеш-функция позволяет предварительно разбить список файлов на группы (гнёзда), соответствующие разным её значениям, и поиск совпадений производить уже только внутри каждого из гнёзд. Подобный процесс в информатике называется гнездованием.

Природа хеш-значений не важна, это могут быть числа или строки. Главное, чтобы хэш-функция легко вычислялась и чтобы хеш-значения было легко сравнивать друг с другом (легче, чем сами файлы). Например, полное содержимое файлов в качестве хеш-функции нам не подойдёт, поскольку не удовлетворяет ни одному из этих требований: содержимое файла долго считывать, оно может переполнить оперативную память, и сравнивать содержимое файлов — то же самое, что сравнивать сами файлы.

В качестве хеш-функции можно предложить первый байт файла. Это уже лучше. Однако нужно особым образом поступать с пустыми файлами, не содержащими этого первого байта. К тому же первый байт плохо разделяет файлы. Представьте, что требуется искать одинаковые среди большого количества файлов в формате XML. Не обязательно знать, что такое XML; достаточно сказать, что с большой вероятностью такие файлы будут начинаться с байта < (обычно в их начале есть заголовок вида <?xml version="1.0" encoding="UTF-8"?>). Аналогично, файлы с откомпилированными программами для Linux начинаются с байтов ELF, программы для DOS и Windows — с MZ, программы на Perl и на командном языке Linux — с #!. Так что предварительная группировка по первому байту отправит файлы таких типов в одну группу и обречёт нас на тотальное попарное сравнение файлов в группе.

Требуется хеш-функция, принимающая более разнообразные значения для различных (пусть даже очень похожих) файлов.

Часто в качестве хеш-функции берут так называемые контрольные суммы. Простейшим примером такой контрольной суммы является сумма числовых значений всех байтов файла (или, скажем, остаток от её деления на $256$ или на что-нибудь ещё). Её вычислять сложнее, чем первый байт, однако вероятность случайного совпадения для разных файлов резко снижается, так как её значение невозможно предсказать без вычисления, зная тип файла.

Существуют специальные программы (sum, md5sum), предназначенные для контрольного суммирования (разными методами) файлов:

% sum examples/l*.pl
03751     2 examples/life.pl
53550     1 examples/lsystem-dragon.pl
29835     1 examples/lsystem-gosper.pl
47388     1 examples/lsystem-koch.pl
43509     1 examples/lsystem-plant.pl
54885     1 examples/lsystem-sierpinski.pl
19713     1 examples/lsystem-tree.pl
% md5sum examples/l*.pl
02b8abb9bec49f81da6db63d81dcd298  examples/life.pl
482d0770e3668545e25091b2cda9a852  examples/lsystem-dragon.pl
d1fdf9e3c27c7f3ed35fa0372f47062a  examples/lsystem-gosper.pl
ece16e89abeb63f272df0d4ff9735fa3  examples/lsystem-koch.pl
c3bb9a2d511f5a72b9772f2d685b04d8  examples/lsystem-plant.pl
8e9c65469c67d1a8e55e795a83779d21  examples/lsystem-sierpinski.pl
cec11f109790ed623630e28d5a8ecb06  examples/lsystem-tree.pl

(контрольные суммы выводятся в первой колонке). Часто там, где выкладываются файлы для скачивания по сети, размещают и файл контрольных сумм (вывод одной из этих программ просто перенаправляется в него). Скачав интересующие нас файлы, а также файл контрольных сумм, мы можем выполнить суммирование сами и сравнить результат с содержимым файла контрольных сумм. Совпадение с очень высокой вероятностью означает, что файлы при передаче по сети дошли до нас в неизменном виде. Различие непременно свидетельствует о порче файла по дороге.

Алгоритмы, используемые в программах sum и md5sum, реализованы как библиотечные процедуры в языке Perl, и при желании ими можно воспользоваться. Но суммирование требует считывания файла целиком, а это долго. Однако для предварительной группировки файлов есть готовая отличная хеш-функция: размер файла. Ей мы и воспользуемся.

Размер файла хранится в одной записи вместе с его именем, сведениями о владельцах и режимом доступа. Такие записи составляют директорию. При любой записи в файл сведения о его размере обновляются. Таким образом нет нужды считывать файл байт за байтом и подсчитывать считанные байты, чтобы определить размер. Для определения размера файла в Perl есть оператор -s:

Perl
$fileSize=-s 'examples/lsystem-tree.pl';

Вернёмся к нашему примеру с шестью файлами. Предположим, что файл a имеет размер 3141 байт, файлы b, d, e — по 2718, а c и f — по 1414 байт. Как видно на примере e, совпадение его размера с размерами b и d не гарантирует совпадения содержимого.

Получая шесть имён файлов одно за другим, сразу же вычисляем размер. Для каждого размера создаём список групп (в начале состоящий из единственной группы). Удобно хранить пары «размер — список групп» в ассоциативном массиве:

Perl
(3141=>[['a']], 2718=>[['b', 'd', 'e']], 1414=>[['c', 'f']])

Затем с каждым списком групп поступаем так же, как было описано ранее. В результате изменится только список, отвечающий ключу 2718, там одна группа превратится в две:

Perl
(3141=>[['a']], 2718=>[['b', 'd'], ['e']], 1414=>[['c', 'f']])

После выполнения предварительной группировки понадобилось только три сравнения файлов: b с d (успешное), b с e (неудачное) и c с f (успешное). При наивном подходе пришлось бы сравнивать $15 = \frac{6 \cdot 5}{2}$ пар. При большом количестве файлов экономия будет огромной. Плата за это существенное ускорение будет невелика: небольшое усложнение структуры данных, используемой для хранения имён файлов, и необходимость хранить всевозможные встретившиеся размеры файлов в качестве ключей в ассоциативном массиве (размеры ещё нам понадобятся — они выводятся перед каждой группой).


Глава 29. Поиск одинаковых файлов		Разработка