Обнаружение дубликатов файлов - PullRequest
Новая
       16

Обнаружение дубликатов файлов

4 голосов
/ 21 марта 2012

Я хотел бы обнаружить дубликаты файлов в дереве каталогов. При обнаружении двух идентичных файлов будет сохранен только один из дубликатов, а оставшиеся дубликаты будут удалены для экономии места на диске.

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

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

Какой еще быстрый и надежный механизм вы бы использовали?

Ответы [ 7 ]

15 голосов
/ 21 марта 2012

Расчет хеша замедлит работу вашей программы.Лучше вы также проверьте размер файла .Все дубликаты должны иметь одинаковый размер.Если они имеют одинаковый размер файла, примените проверку хеша.Это заставит вашу программу работать быстро.

Может быть больше шагов.

  1. Проверьте, равен ли размер файла
  2. Если шаг1 проход, проверьте, равны ли первый и последний диапазон байтов (скажем, 100 байтов)
  3. Если этап 2 пройден, проверьте тип файла ,
  4. Если шаг 3 пройден, проверьте, наконец, хеш

Чем больше критериев вы добавите, тем быстрее он будет выполняться и вы сможете избежать последнего средства ( хеш) вот так.

2 голосов
/ 14 ноября 2014

Это будет зависеть от файлов, которые вы сравниваете.

A) Наихудший сценарий:

  1. У вас много файлов одинакового размера
  2. Файлы очень большие
  3. Файлы очень похожи с различиями, обнаруженными в узком случайном месте в файле

Например, если у вас было:

  • 100x 2 МБ файлов одинакового размера,
  • сравнение друг с другом,
  • с использованием двоичного сравнения с
  • 50% чтения файла (вероятность нахождения неравного байта в первой половине файла)

Тогда вы бы получили:

  • 10 000 сравнений
  • 1 МБ, что равно
  • всего 10 ГБ чтения.

Однако, если у вас был тот же сценарий, но сначала получил хэши файлов , вы бы:

  • чтение 200 МБ данных с диска (как правило, самый медленный компонент в компьютере) с
  • 1.6K в памяти (при использовании MD5 хэширование - 16 байт - безопасность не важна)
  • и будет читать 2N * 2MB для окончательного прямого двоичного сравнения, где N - количество найденных дубликатов.

Я думаю, что наихудший сценарий не типичный хотя.

B) Типичный сценарий:

  1. Файлы обычно различаются по размеру
  2. Скорее всего, файлы будут отличаться в начале файла - это означает, что прямое двоичное сравнение обычно не предполагает считывание всего файла в большом количестве разных файлов одного размера.

Например, если у вас было:

  • Папка файлов MP3 (они не становятся слишком большими - возможно, не больше 5 МБ)
  • 100 файлов
  • сначала проверка размера
  • максимум 3 файла одинакового размера (дубликаты или нет)
  • с использованием двоичное сравнение для файлов одинакового размера
  • 99% может быть другим после 1 КБайт

Тогда вы бы получили:

  • Не более 33 случаев, когда длина одинакова в 3 наборах файлов
  • Параллельное двоичное чтение 3 файлов (или более возможно) одновременно в 4K кусках
  • При обнаружении 0% дубликатов - 33 * 3 * 4 КБ для чтения файлов = 396 КБ для чтения на диске
  • При найденных множителях 100% = 33 * 3 * N, где N - размер файла (~ 5 МБ) = ~ 495 МБ

Если вы ожидаете 100% -ное умножение, хеширование не будет более эффективным, чем прямое двоичное сравнение. Учитывая, что вы должны ожидать <100% кратных, хеширование будет менее эффективным, чем прямое двоичное сравнение. </p>

C) Повторное сравнение

Это исключение. Создание базы данных hash + length + path для всех файлов ускорит повторные сравнения. Но выгоды будут незначительными. Первоначально это потребует 100% чтения файлов и хранения хеш-базы данных. Новый файл должен быть прочитан на 100%, а затем добавлен в базу данных, и, если он сопоставлен, все равно потребуется прямое двоичное сравнение в качестве последнего шага сравнения (чтобы исключить коллизию хешей). Даже если большинство файлов имеют разные размеры, при создании нового файла в целевой папке он может соответствовать существующему размеру файла и может быть быстро исключен из прямого сравнения.

Заключить:

  • Не следует использовать дополнительные хэши (конечный тест - двоичное сравнение - всегда должен быть финальным тестом)
  • Двоичное сравнение часто более эффективно при первом запуске, когда имеется много файлов разного размера
  • Сравнение MP3 хорошо работает с длиной, тогда как двоичное сравнение.
1 голос
/ 21 марта 2012

Это типичный вывод md5sum: 

0c9990e3d02f33d1ea2d63afb3f17c71

Если вам не нужно бояться намеренно подделанных файлов, шансы на второй случайный файл для сопоставления составляют 

1/(decimal(0xfffffffffffffffffffffffffffffff)+1)

Если вы учтете размер файла в качестве дополнительного теста, ваша уверенность возрастет, что оба файла подойдут. Вы можете добавить все больше и больше измерений, но побитовое сравнение будет последним словом в такой дискуссии. Для практических целей достаточно md5sum.

1 голос
/ 21 марта 2012

Если вы используете хеш-алгоритм, такой как SHA-1 или лучше, но SHA-256 или выше, я действительно сомневаюсь, что вы получите одинаковое значение хеш-функции для двух разных файлов.SHA - криптографическая хеш-функция, которая используется в системах контроля версий, таких как Git.Таким образом, вы можете быть уверены, что он сделает всю работу за вас.

Но если вам все еще нужны дополнительные проверки, вы можете выполнить следующие два шага.
1) Разобрать заголовки - это действительно сложный файл cookie для взлома, поскольку разные форматы могут иметь разные длины заголовков
2) Проведите проверку работоспособности - размер файла, прочитайте случайные позиции файла и попробуйте проверить, совпадают ли они

1 голос
/ 21 марта 2012

Хеш-решение в порядке - вам нужно будет просто воспользоваться одним из механизмов коллизий для работы с 2 элементами, которые хэшируются с одинаковым значением. [ цепочка или открытая адресация ].

Просто итеративно добавляйте элементы - если ваша реализация обнаружила наличие дублирования - она ​​не добавит его в хэш-набор. Вы узнаете, что элемент является дублирующим, если размер набора не изменился после попытки добавления элемента.

Скорее всего, на вашем языке уже есть реализации для такого рода структуры данных - например, HashSet в Java и unordered_set в C ++.

0 голосов
/ 25 января 2017

Вот сценарий VBS, который сгенерирует файл CSV для отображения дубликатов файлов в папке на основе контрольной суммы файла MD5 и размера файла. 

Set fso = CreateObject("Scripting.FileSystemObject")
Dim dic: Set dic = CreateObject("Scripting.Dictionary")
Dim oMD5:  Set oMD5 = CreateObject("System.Security.Cryptography.MD5CryptoServiceProvider")
Dim oLog 'As Scripting.TextStream

Set oArgs = WScript.Arguments

If oArgs.Count = 1 Then
    sFolderPath = GetFolderPath()
    Set oLog = fso.CreateTextFile(sFolderPath & "\DublicateFiles.csv", True)
    oLog.Write "sep=" & vbTab & vbCrLf
    CheckFolder oArgs(I)
    oLog.Close
    Msgbox "Done!"
Else
    Msgbox "Drop Folder"
End If

Sub CheckFolder(sFolderPath)
    Dim sKey
    Dim oFolder 'As Scripting.Folder
    Set oFolder = fso.GetFolder(sFolderPath)

    For Each oFile In oFolder.Files
        'sKey = oFile.Name & " - " & oFile.Size
        sKey = GetMd5(oFile.Path) & " - " & oFile.Size

        If dic.Exists(sKey) = False Then 
            dic.Add sKey, oFile.Path
        Else
            oLog.Write oFile.Path & vbTab & dic(sKey) & vbCrLf
        End If
    Next

    For Each oChildFolder In oFolder.SubFolders
        CheckFolder oChildFolder.Path
    Next
End Sub

Function GetFolderPath()
    Dim oFile 'As Scripting.File
    Set oFile = fso.GetFile(WScript.ScriptFullName)
    GetFolderPath = oFile.ParentFolder
End Function

Function GetMd5(filename)
    Dim oXml, oElement

    oMD5.ComputeHash_2(GetBinaryFile(filename))

    Set oXml = CreateObject("MSXML2.DOMDocument")
    Set oElement = oXml.CreateElement("tmp")
    oElement.DataType = "bin.hex"
    oElement.NodeTypedValue = oMD5.Hash
    GetMd5 = oElement.Text
End Function

Function GetBinaryFile(filename)
    Dim oStream: Set oStream = CreateObject("ADODB.Stream")
    oStream.Type = 1 'adTypeBinary
    oStream.Open
    oStream.LoadFromFile filename
    GetBinaryFile= oStream.Read
    oStream.Close
    Set oStream = Nothing
End Function

Вот сценарий VBS, который сгенерирует CSV-файл для отображения дубликатов файлов в папке на основе имени и размера файла. 

Set fso = CreateObject("Scripting.FileSystemObject")
Dim dic: Set dic = CreateObject("Scripting.Dictionary")
Dim oLog 'As Scripting.TextStream

Set oArgs = WScript.Arguments

If oArgs.Count = 1 Then
    sFolderPath = GetFolderPath()
    Set oLog = fso.CreateTextFile(sFolderPath & "\DublicateFiles.csv", True)
    oLog.Write "sep=" & vbTab & vbCrLf
    CheckFolder oArgs(I)
    oLog.Close
    Msgbox "Done!"
Else
    Msgbox "Drop Folder"
End If

Sub CheckFolder(sFolderPath)
    Dim sKey
    Dim oFolder 'As Scripting.Folder
    Set oFolder = fso.GetFolder(sFolderPath)

    For Each oFile In oFolder.Files
        sKey = oFile.Name & " - " & oFile.Size

        If dic.Exists(sKey) = False Then 
            dic.Add sKey, oFile.Path
        Else
            oLog.Write oFile.Path & vbTab & dic(sKey) & vbCrLf
        End If
    Next

    For Each oChildFolder In oFolder.SubFolders
        CheckFolder oChildFolder.Path
    Next
End Sub

Function GetFolderPath()
    Dim oFile 'As Scripting.File
    Set oFile = fso.GetFile(WScript.ScriptFullName)
    GetFolderPath = oFile.ParentFolder
End Function
0 голосов
/ 24 ноября 2015 
/// ------------------------------------------------------------------------------------------------------------------------
    /// <summary>
    /// Writes duplicate files to a List<String>
    /// </summary>
    private void CompareDirectory(string[] files)
    {
        for (int i = 0; i < files.Length; i++)
        {
            FileInfo one = new FileInfo(files[i]); // Here's a spot for a progressbar or something

            for (int i2 = 0; i2 < files.Length; i2++) 
            {
                if (i != i2 && !duplicatePathsOne.Contains(files[i2])) // In order to prevent duplicate entries
                {
                    FileInfo two = new FileInfo(files[i2]);
                    if (FilesAreEqual_OneByte(one, two))
                    {
                        duplicatePathsOne.Add(files[i]);
                        duplicateNamesOne.Add(Path.GetFileName(files[i]));
                        duplicatePathsTwo.Add(files[i2]);
                        duplicateNamesTwo.Add(Path.GetFileName(files[i2]));
                    }
                }
            }
        }
    }


/// ------------------------------------------------------------------------------------------------------------------------
    /// <summary>
    /// Compares files by binary
    /// </summary>
    private static bool FilesAreEqual_OneByte(FileInfo first, FileInfo second)
    {
        if (first.Length != second.Length)
            return false;

        using (FileStream fs1 = first.OpenRead())
        using (FileStream fs2 = second.OpenRead())
        {
            for (int i = 0; i < first.Length; i++)
            {
                if (fs1.ReadByte() != fs2.ReadByte())
                    return false;
            }
        }

        return true;
    }
...