Walk Directories via Caching (& Dup file detection) 
Author Message
 Walk Directories via Caching (& Dup file detection)

A little while ago, some folks were posting some caching routines for
dirwalk.....

Here's something that I cooked up a while ago....

Now, I've added just recently full & partial MD5 hashing, and I'm slowly
adding duplicate file checking...

It seems to work fine, but it definetly could use some optimizations
 & speed ups...

Anyone have any input?  Is there some faster method I could use,
that I've missed?

The main idea is that the walk tree is built once, and the class just
walks through the list (in memory), instead of walking through the
hard drive....

(This was written rather quickly when I realized that searching for
hundred's of files, through dirwalk was too slow, because for each file,
it would have to go through the hard drive each time.)

There are two major data structures:

      self.index_directory_names  = []
      self.index_directory_files  = []

They are "logically" linked.  The files in index_directory_files[x] are
in index_directory_names[x], and vice versa.

I've just recently added the MD5 code, for duplicate detection, which
is really where I'm looking for the majority of any optimization....
It's *FAST*, or at least takes a reasonable amount of time with 45,000
files....  (I think it takes about 30-45 minutes for that...?  I haven't
timed it)

         - Benjamin

----------------------------------
#from bas_common import *  # True / false syn's for boolean expressions
import dircache
import sys
import os
import string
import shutil
import time
import md5

#mac_mode = macintosh
mac_mode = 0 # code stored in bas_common

if mac_mode:
   import findertools
   import findertools
   import macfs
   import macostools

def full_md5_digest(filename, block=(8*1024) ):
   """Return 16 byte MD5 digest of entire given file.
   """
   f = open(filename, 'rb')
   data = f.read(block)
   D = md5.new()
   while data:
      D.update(data)
      data = f.read(block)
   f.close()
   digest = D.digest()
   return digest

def short_md5_digest(filename, block=(8*1024) ):
   """Return 16 byte MD5 digest of given file.
   """
   f = open(filename, 'rb')
   data = f.read(block)
   D = md5.new()
   D.update(data)
   f.close()
   digest = D.digest()
   return digest

class   directory_walk:

   def __init__ ( self ):
      self.index_directory_names  = []
      self.index_directory_files  = []
      self.use_md5            = 1
      self.files_to_skip   = ["FILE_ID.DIZ", "README.TXT",
                        "READ.ME", "README", "ID.DOC",
                        ".DS_STORE",               # Do Not Remove, Mac OS X File
                        "ICON",                    # Do Not Remove, Mac OS File
                        "ICON_"                    # Do Not Remove, Mac OS File
                        ]
      self.upper_case              = None

   def __list_files ( self, arg, dirname, names ):
      if self.upper_case:
         self.index_directory_names.append ( string.upper( string.strip(dirname) ) )
         for j in range(0, len(names)):
            names[j] = names[j].upper()
      else:
         self.index_directory_names.append ( string.strip(dirname) )

      self.index_directory_files.append ( names )

   def build_search_tree ( self, base_directory_name):
      self.index_directory_names = []
      self.index_directory_files = []
      os.path.walk ( base_directory_name, self.__list_files, None)

   def   use_upper_case ( self ):
      self.upper_case      = 1

   def single_file_exist (self, filename):
      if self.upper_case:
         filename = string.upper(filename)

      listing_size = len(self.index_directory_files)
      for x in range(0, listing_size):
         try:
            junk = self.index_directory_files[x].index(filename)
            return (1, string.strip(self.index_directory_names[x] ) )
         except:
            pass

      return (None, None)

   def   return_duplicates_filenames ( self ):
      duplicate_files = []
      master_list    = []

      print "# of directories : ", len(self.index_directory_names)
      for x in range(0, len(self.index_directory_names)):
         print ".",
         for filename in self.index_directory_files[x]:

            filename       = string.strip(string.upper(filename))

            if not(filename in self.files_to_skip):
               if os.path.isfile (os.path.join(self.index_directory_names[x], filename)):

                  master_list.append (filename)
                  if master_list.count(filename) >= 2:
                     if duplicate_files.count(filename) == 0:
                        duplicate_files.append (filename)
      print
      return duplicate_files

   def   return_all_directories_from_file ( self, filename):
      file_directories = []

      for x in range(0, len(self.index_directory_names)):
         if self.index_directory_files[x].count(filename) >= 1:
            file_directories.append ( self.index_directory_names[x])
      return file_directories

   def   filter_via_md5 ( self, dup_file_list, md5_filter ):
      duplicate_files = []
      master_list    = []

      for filename in dup_file_list:
         file_locations = self.return_all_directories_from_file (filename)

         for location in file_locations:
            duplicate_files.append ( (filename, location, md5_filter (os.path.join(location,
filename)) ) )

      return duplicate_files

fss, ok = macfs.GetDirectory('Duplicate Search Directory:')
if not ok:
   sys.exit(0)
else:
   dup_directory = fss.as_pathname()

dir_find = directory_walk()
dir_find.use_upper_case()
print "Search Tree"
dir_find.build_search_tree ( dup_directory )
print "End Search Tree"
output_file = open("results.txt", "w")

print "Begin"
dup_files =  dir_find.return_duplicates_filenames ()
md5_output = dir_find.filter_via_md5 ( dup_files, short_md5_digest )

length_of_md5_output = len(md5_output)

optimized_md5 = []
for scan in range(0, length_of_md5_output):
   optimized_md5.append (md5_output[scan][2])

print "Number of Files to Validate: ", length_of_md5_output
for counter in range(0, length_of_md5_output):
   if optimized_md5.count ( md5_output[counter][2]) >= 2:
      for scan in range(counter, length_of_md5_output):
         if (md5_output[scan][2] == md5_output[counter][2]) and scan<>counter:
            output_file.writelines ( "\r", "-"*40)
            output_file.writelines ( "\rFile: %s" % md5_output[counter][0] )
            output_file.writelines ( "\r\tLocation : %s " % md5_output[scan][1] )
            print "\r", "-"*40
            print "\rFile: %s" % md5_output[counter][0]
            print "\r\tLocation : %s " % md5_output[scan][1]
      while optimized_md5.count ( md5_output[counter][2]):
         try:
            optimized_md5.remove( md5_output[counter][2])
         except:
            pass
      print "\r\tLocation : %s " % md5_output[counter][1]
      output_file.writelines ( "\r\tLocation : %s " % md5_output[counter][1] )

output_file.close()
print "End"
#for filename in dup_files:
#  print "-"*40,"\n"
#  output_file.writelines ("-"*40,"\r")
#  print filename
#  output_file.writelines (filename, "\r")
#  dup_directories = dir_find.return_all_directories_from_file ( filename )
#  for dir in dup_directories:
#     print "\t%s" % dir
#     output_file.writelines ("\t%s\r" % dir)
#  print "-"*40,"\n"
#  output_file.writelines ("-"*40,"\r")

sys.exit(5)



Thu, 26 Aug 2004 23:23:50 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. segfault dup'ing string through C++ (via swig) module

2. Windows : directory size without walking in it !

3. Walking recursivly through a directory-structure

4. A directory walking framework (source attached).

5. Hardware Detection and Initialisation via RS232 serial port.

6. Creating Directories & Sub-Directories from Clarion

7. Directory() & file size

8. DBF & INDEX File directory

9. VX-REXX Directories & Files

10. Directory & File Monitoring

11. Hidden files, selecting directories, & taxes

12. Directory of File/Directories on CD

 

 
Powered by phpBB® Forum Software