Russian Qt Forum
Ноябрь 10, 2024, 21:07 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 [2] 3   Вниз
  Печать  
Автор Тема: Дубликаты файлов  (Прочитано 22482 раз)
spectre71
Гость
« Ответ #15 : Сентябрь 06, 2009, 08:35 »

Что такое "оптимальное побайтовое сравнением"?
Есть N файлов одинакового размера. Для каждого нужно получить условный ID  так чтобы файлы у которых все байты совпадают имели тот же ID. Алгоритм должен работать для любого N и учитывать ограничение на число одновременно открытых файлов.
Я про это писал.
Цитировать
Можно еще вводить и промежуточные "hash", в том числе и для первых N байт файлов(если файлы в пачке достаточно большие), это задача оптимизации(если требуется).
Записан
cya-st
Гость
« Ответ #16 : Сентябрь 06, 2009, 17:58 »

Какие есть функции в QT для генерации хеш? Или надо самому замутить (xor например)
Записан
spectre71
Гость
« Ответ #17 : Сентябрь 06, 2009, 18:46 »

Какие есть функции в QT для генерации хеш? Или надо самому замутить (xor например)
Хбз, наверное есть?, я пока пользуюсь "openssl".
Записан
SimpleSunny
Гость
« Ответ #18 : Сентябрь 06, 2009, 20:06 »

QCryptographicHash::hash()
qHash()
« Последнее редактирование: Сентябрь 06, 2009, 20:15 от SimpleSunny » Записан
Tonal
Гость
« Ответ #19 : Сентябрь 07, 2009, 08:34 »

Я бы посоветовал 3-х уровневый отбор: размер, crc (qChecksum например), полное сравнение.
crc считается существенно быстрее криптографического хеша, но сильнее подвержен коллизиям.
С другой стороны отсеять с его помощью разные файлы проще, чем все их сравнивать. Улыбающийся
Записан
Rcus
Гость
« Ответ #20 : Сентябрь 07, 2009, 08:50 »

Быстрее ли? При чтении файла частями по 9.24МиБ и расчете MD4/SHA1 хешей загрузка процессора E6550 не превышает 10%, а скорость ограничивается 100МиБ/с. Тут ограничивающим фактором выступает не мощность процессора, а ограничение I/O системы.

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

Впрочем проблема коллизий разрешается довольно просто: хеш нужно считать не от целого файла, а от блоков фиксированного размера. (Это не я придумал - в ed2k/AICH, BitTorrent клиентах это уже есть)
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #21 : Сентябрь 07, 2009, 10:48 »

Важно определиться нужно ли "точное побайтовое сравнение" или же устраивает контрольная сумма. Это 2 совершенно разных задачи, вторая намного проще.

По поводу "замутить с xor" - это весьма ненадежно. Например если 2 байта переставлены местами, то xor дает тот же результат. Очень давно (по моему на AutoCAD 10) я видел что-то такое: байт вращается и добавляется к сумме, (сумма % Крутой = вращение для следующего байта.

Если же клиент настаивает на "абсолютной точности" то соображения об "отсеивании" мало что дают. Пользователь купил драйв побольше и делает резервные копии раз в неделю. Имеем много одинаковых файлов, очевидно что дополнительные проверки работают в минус. Другой случай - есть много разных файлов одинакового размера. Но тогда побайтовое сравнение (аккуратно сделанное) должно быстро с этим разобраться.   
Записан
cya-st
Гость
« Ответ #22 : Сентябрь 07, 2009, 17:35 »

Цитировать
По поводу "замутить с xor" - это весьма ненадежно.
- это я к примеру сказал
Записан
spectre71
Гость
« Ответ #23 : Сентябрь 08, 2009, 10:03 »

Быстрее ли? При чтении файла частями по 9.24МиБ и расчете MD4/SHA1 хешей загрузка процессора E6550 не превышает 10%, а скорость ограничивается 100МиБ/с. Тут ограничивающим фактором выступает не мощность процессора, а ограничение I/O системы.

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

Впрочем проблема коллизий разрешается довольно просто: хеш нужно считать не от целого файла, а от блоков фиксированного размера. (Это не я придумал - в ed2k/AICH, BitTorrent клиентах это уже есть)

Согласен. Фактически скорость вычисления MD5(openssl) в 2-3 раза быстрее чтения с диска, соответственно для вычисления контрольной суммы не имеет смысла использовать xor или подобные быстрые алгоритмы с высоким уровнем коллизий.
Мы решаем задачу по поиску дубликатов файлов и соответственно должны учесть все проблемы с этим связанные. Если решать задачу универсально, то можно составить такой алгоритм:

0) Имеем(получаем) список файлов(путей)
1) Получаем канонические пути, сортируем и отсеиваем дубликаты
2) Получаем размеры, сортируем и разделяем на пачки с одинаковым размером, отсеиваем уникальные
3) Далее работаем с каждой пачкой в которой файлы имеют одинаковый размер
4) Определяем sparthash и sfullhash, sparthash <= sfullhash, где
    sparthash - размер блока(куска большого файла) для вычисления частичного хеша(например от начала файла)
    sfullhash  - максимального размер файла для вычисления хеша на всем файле
5) Для пачек с размером файлов  > sfullhash, вычисляем hash на размере sparthash, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
6) Далее с каждой пачкой с размером файлов  <= sfullhash и пачек полученных на шаге 5 работаем одинаково
7) Вычисляем hash для каждого файла пачки, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
8.) Теперь имеем пачки с одинаковым hash, с очень очень высокой вероятностью они одинаковы, но мы не можем этого гарантировать! Далее работаем с каждой такой пачкой
9) Делаем побайтное сравнение файлов в пачке, но не каждого с каждым, а последовательно:
    1-й со 2-м, 2-й с 3-м, 3-й с 4-м, ... N-1 c N
10) С очень очень высокой вероятность мы получим, что 1==2==3==4==...==N, и таким образом удостоверимся в идентичности файлов
11) В редких ситуациях будем иметь что то подобное:  1==2<3==4>...<N.
12) Для однознаковых последовательностей, по знакам "<" и ">", например:
     1==2<3==4<...<N. или 1==2>3==4>...>N.
     Все тривиально!
13) Для неоднознаковых, убираем дубликаты, и сортируем. Алгоритм сортировки выбираем с наименьшим кол-вом сравнений элементов, кол-во перемещений роли не играет. Во время сортировки(и до нее - для исходной последовательности) запоминаем отношения сравниваемых файлов между собой(<>=), чтобы не делать повторные сравнения во время сортировки и после нее.
14) Шаг 13 очень маловероятен, но возможен и должен оптимизироваться только по кол-ву попарных сравнений - как можно меньше.





Записан
spectre71
Гость
« Ответ #24 : Сентябрь 08, 2009, 11:00 »

Уточнение к шагу 13.
Имем последовательность типа 1==2<3==4>...<N.
После того как убрали дубликаты - имем 2<4>...<N. - всего M файлов
Заводим таблицу размера M*М.
1) Пописываем в нее уже известные (2<4>...<N) комбинации,
2) Пописываем вычисляемые по известным, например: имеем a<b<с => a<b, a<c, b<c.
Во время сортировки, при сравнении:
3) сперва смотрим в таблице и если есть значение - берем из нее.
4) если нет значения, сравниваем файлы и заносим заначение в таблицу. После чего для нового значения прописываем вычисляемые
 в таблицу, как в пункте 2.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #25 : Сентябрь 08, 2009, 12:52 »

Я бы делал попроще и строил бы данные примерно так
Код:
struct CFileInfo {
    CFileInfo( QFile & file );
 ~CFileInfo( void ) { delete mBuf; }
   bool operator == ( const CFileInfo & ) const;
   bool operator < ( const CFileInfo & ) const;

  QFile * mFile;     // pointer to file
  size_t  mSize;    // file size
  size_t  mPos;     // file position
  bool    mError;    // error flag
  char * mBuf;      // read buffer
  size_t  mBufLen; // buffer length
  size_t  mID;       // ID to assign
};

Операторы == и < сравнивают длины и если равны, то буфера чтения. Если произошла ошибка чтения (а она для системных файлов будет) то запоминаем mError, такой файл никому не равен. Если число открытых файлов слишком велико - ничего не попишешь, придется открывать/читать/закрывать (для этого держим mPos)

Алгоритм:

- на каждом шаге имеем имеем сортированный массив CFileInfo. Находим все интервалы (пачки из 2 и более) в которых все файлы (пока) равны. Если файлы полностью прочитаны (полное сравнение достигнуто) присваиваем очередное ID. Иначе добавляем все найденные интервалы в массив интервалов.

- берем первый интервал из массива интервалов. Допустим это файлы [0..10]. Открываем все эти 10 файлов, заполняем буфера. Сортируем пачку из 10 файлов, теперь они могут быть уже не равны. Возвращаемся к началу с той разницей что работаем в интервале  [0..10].

- массив интервалов пуст - все сделано
Записан
spectre71
Гость
« Ответ #26 : Сентябрь 08, 2009, 14:22 »

Я бы делал попроще и строил бы данные примерно так
...
...
Не вижу никакого смысла одновременно открывать и сравнивать больше 2-х файлов, это не эффективно. Тем более не имеет смысла держать больше 2-х буферов памяти для чтения файлов, их нужно ровно 2 и создать один раз для всего процесса сравнения.
С обработкой ошибок согласен. Их несколько.
1) Файл невозможно открыть или дочитать до конца
2) Файл был иэменен до открытия.
3) Файл открыт на запись другим процессом или файл изменен после открытия.
В зависимости от условий здачи, необходимо либо считать эти файлы уникальными либо обрабатывать повторно и сравнивать с обработанными.
С 3-м пунктом мне не понятно, есть ли стандартные средства(и желательно в QT) для отслеживания таких ситуаций?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #27 : Сентябрь 08, 2009, 14:59 »

Не вижу никакого смысла одновременно открывать и сравнивать больше 2-х файлов, это не эффективно. Тем более не имеет смысла держать больше 2-х буферов памяти для чтения файлов, их нужно ровно 2 и создать один раз для всего процесса сравнения.
Это мы уже обсуждали
- загрузили файл №1, загрузили файл №2, сравнили. Не равны. Что делать? Загрузить файл №3, сравнить его с файлом №1? Ну тогда мы файл №2 грузим 99 раз,  файл №3 - 98 раз и.т.д. Быстро это явно не будет, в основном потому что надо все время открывать/закрывать файлы.
Все соображения об отсеивании бесспорны но нетрудно найти диск на котором 100 (или больше) одинаковых и достаточно больших файлов. И с 2-мя буферами из этой трясины никак не выбраться. Очевидно нужно читать много файлов параллельно и небольшими кусками. Это можно спокойно написать за день. А к тому что Вы предложили - и подступиться страшно  Улыбающийся
Записан
spectre71
Гость
« Ответ #28 : Сентябрь 08, 2009, 15:30 »

Не вижу никакого смысла одновременно открывать и сравнивать больше 2-х файлов, это не эффективно. Тем более не имеет смысла держать больше 2-х буферов памяти для чтения файлов, их нужно ровно 2 и создать один раз для всего процесса сравнения.
Это мы уже обсуждали
- загрузили файл №1, загрузили файл №2, сравнили. Не равны. Что делать? Загрузить файл №3, сравнить его с файлом №1? Ну тогда мы файл №2 грузим 99 раз,  файл №3 - 98 раз и.т.д. Быстро это явно не будет, в основном потому что надо все время открывать/закрывать файлы.
Все соображения об отсеивании бесспорны но нетрудно найти диск на котором 100 (или больше) одинаковых и достаточно больших файлов. И с 2-мя буферами из этой трясины никак не выбраться. Очевидно нужно читать много файлов параллельно и небольшими кусками. Это можно спокойно написать за день. А к тому что Вы предложили - и подступиться страшно  Улыбающийся
Открытие/закрытие файла быстрее по сравнению с чтением оптимального фрагмента файла(размер внутреннего кеша жесткого диска) даже при условии отсутствия дефрагментации!
Пожалуйста прочитай внимательно то что я писал - 13 пунктов + доплнение. Там нет проблемы с побайтным сравниванием всех комбинаций пар(в этом нет необходимости) файлов в каждой пачке, такая ситуация невероятна(ее можно создать только искусственно, и то, при этом кол-во сравнений не превысит O(N*log(N)))! В типичном случае, который гораздо больше вероятности 0,9999999999 мы для X = 10000000000 файлов в пачке, выполним X побайтных сравнений!
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #29 : Сентябрь 08, 2009, 22:17 »

Вот мой вариант (примерно 300 строк). Вполне возможно где-то наврал + нужно добавить индикатор (progress bar).
http://www.2shared.com/file/7661840/6595e4cd/filedupcpp.html(не смог приаттачить здесь).
Если есть желание - делайте Ваш вариант и сравним. А то слово за слово - только людей утомляем  Улыбающийся

Edit: так и есть, наврал Улыбающийся В CloseFile нужно добавить mFile->close()

Edit2: Отрихтовал, убрал пару баговhttp://www.2shared.com/file/7672990/fe2c76e9/filedup_fixcpp.html
« Последнее редактирование: Сентябрь 09, 2009, 11:54 от Igors » Записан
Страниц: 1 [2] 3   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.144 секунд. Запросов: 23.