كيف تستخدم دوال التجزئة للعثور على الملفات المكررة باستخدام لغة بايثون

لنفترض أننا نريد العثور على ملفات مكررة على الحاسوب مثل نسخ إضافية من صور أو مجموعة بيانات، قد نجري عملية بحث عادية ونحصل على أسماء الملفات المتشابهة لكن قد يغير المستخدم اسم الملف وهذا يعني أن المحتويات ستظل نفسها، فنحن نحتاج الآن إلى مقارنة تلك المحتويات، لكن إن كان لدينا الكثير من الملفات فستكون هذه عملية بطيئة.

يمكن تقدير مدى بطء هذه العملية بحساب بسيط حيث يمكن ترتيب عدد n من العناصر في أزواج بعدد من الطرق يساوي n(n-1)، وإذا حذفنا الأزواج المكررة -إذا اعتبرنا أن الزوج A-B هو نفسه B-A يكون لدينا عدد من الأزواج الفريدة يساوي n(n-1)/2 أو (n²-n)/2 للتبسيط، وكلما زادت قيمة n تناسبت تقريبيًا مع n2، وهنا قد يقال أن تعقيد الوقت Time complexity لخوارزميتنا هو O(n²). بعبارة أبسط، حين يتضاعف عدد الملفات يزيد زمن التشغيل أربع مرات تقريبًا، أي أن الوقت المستغرق لكل ملف يزيد مع زيادة العدد الإجمالي للملفات.

لا يمكن تجنب هذا النوع من التباطؤ في الغالب، لكن لدينا حل أفضل في مثالنا هنا، حيث سنتمكن تجميع الملفات التي لديها نفس المعرف ثم نقارن بين الملفات داخل كل مجموعة، إذا ولّدنا معرفًا identifier قصيرًا لكل ملف يعتمد على البايتات التي يحتويها، ويُعد هذا الأسلوب أسرع لأننا ننفذ عملية المقارنة المكلفة -مقارنة كل بايت مقابل بايت على حدة- على الملفات التي يُحتمل تطابقها فقط، بل قد نتجنب عملية المقارنة بالكلية إذا أتقنا توليد هذه المعرفات.

الأسلوب التقليدي

سنبدأ بتنفيذ الأسلوب غير الفعال الذي يعتمد على تعقيد الوقت O(N²) لكي نقارنه بالتصميمات المتطورة التي سنكتبها لاحقًا.

يأخذ البرنامج القصير أدناه -لنسميه brute_force_1.py- قائمة بأسماء الملفات من سطر الأوامر ثم يبحث عن الملفات المكررة، ويطبع النتائج المتطابقة:

import sys


# [bytes]
def same_bytes(left_name, right_name):
 left_bytes = open(left_name, "rb").read()
 right_bytes = open(right_name, "rb").read()
 return left_bytes == right_bytes
# [/bytes]


# [main]
def find_duplicates(filenames):
 matches = []
 for left in filenames:
 for right in filenames:
 if same_bytes(left, right):
 matches.append((left, right))
 return matches


if __name__ == "__main__":
 duplicates = find_duplicates(sys.argv[1:])
 for (left, right) in duplicates:
        print(left, right)
# [/main]

يستخدم هذا البرنامج دالة same_bytes تقرأ ملفين وتقارن بينهما "بايت مقابل بايت":

def same_bytes(left_name, right_name):
    left_bytes = open(left_name, "rb").read()
    right_bytes = open(right_name, "rb").read()
    return left_bytes == right_bytes

لاحظ في المثال أعلاه أننا نفتح الملفات في الوضع الثنائي binary mode باستخدام الوسم rb بدلًا من r المعتاد، وهذا يخبر لغة بايثون أن تقرأ البايتات تمامًا كما هي بدلًا من محاولة تحويلها إلى محارف نصية.

ننشئ مجلدًا باسم tests من أجل اختبار هذا البرنامج والبرامج الأخرى، ويحتوي على ستة ملفات:

نتوقع أن يتم الإبلاغ عن ملفات a الثلاثية وملفات b الثنائية كملفات مكررة:

python brute_force_1.py tests/*.txt

ينبغي أن نحصل على الخرج التالي:

tests/a1.txt tests/a1.txt
tests/a1.txt tests/a2.txt
tests/a1.txt tests/a3.txt
tests/a2.txt tests/a1.txt
tests/a2.txt tests/a2.txt
tests/a2.txt tests/a3.txt
tests/a3.txt tests/a1.txt
tests/a3.txt tests/a2.txt
tests/a3.txt tests/a3.txt
tests/b1.txt tests/b1.txt
tests/b1.txt tests/b2.txt
tests/b2.txt tests/b1.txt
tests/b2.txt tests/b2.txt
tests/c1.txt tests/c1.txt

هذا الخرج غير مفيد وإن كان صحيحًا، إذ يبلغ عن كل ملف على أنه مطابق لنفسه، كما يُكرر الإبلاغ مرتين عن كل تطابق بين ملفين مختلفين، لنصلح هذه الحلقة المتداخلة nested loop في دالة find_duplicates كي نتأكد أننا نفحص أزواج الملفات التي يحتمل اختلافها مرة واحدة فقط:

import sys


def same_bytes(left_name, right_name):
    left_bytes = open(left_name, "rb").read()
    right_bytes = open(right_name, "rb").read()
    return left_bytes == right_bytes


# [dup]
def find_duplicates(filenames):
    matches = []
    for i_left in range(len(filenames)):
        left = filenames[i_left]
        for i_right in range(i_left):
            right = filenames[i_right]
            if same_bytes(left, right):
                matches.append((left, right))
    return matches
# [/dup]


if __name__ == "__main__":
    duplicates = find_duplicates(sys.argv[1:])
    for (left, right) in duplicates:
        print(left, right)

تحديد نطاق الحلقة الداخلية لإنتاج تركبيات فريدة.

تجزئة الملفات

نريد الآن أن نعالج كل ملف مرة واحدة فقط لإنتاج معرف قصير يعتمد على محتويات الملف ثم نقارن الملفات التي تحمل نفس المعرف، وهي الملفات التي يُحتمل أن تكون متطابقة.

إذا قُسمت الملفات إلى عدد g من المجموعات فستحتوي كل مجموعة على عدد N/g من الملفات، ويصبح إجمالي العمل المطلوب O(g(N / g²)) - على سبيل المثال: عدد g مجموعة * عدد مقارنات يساوي (N/g²) داخل كل مجموعة-، أي أننا نحصل على (N²/g) مما يعني أن زمن التشغيل الكلي ينخفض بزيادة عدد المجموعات.

تجميع الملفات عبر شيفرة التجزئة يقلص عدد المقارنات من 15 إلى 4 فقط.

نستطيع إنشاء معرفات للملفات باستخدام دالة تجزئة hash function لإنتاج شيفرة تجزئة hash code، وبما أن البايتات في الأصل عبارة عن أرقام فنستطيع إنشاء دالة تجزئة بسيطة عبر جمع قيم البايتات الموجودة في الملف ثم أخذ باقي القسم على رقم معين:

# [hash]
def naive_hash(data):
    return sum(data) % 13
# [/hash]

if __name__ == "__main__":
    # [example]
    example = bytes("hashing", "utf-8")
    for i in range(1, len(example) + 1):
        substring = example[:i]
        hash = naive_hash(substring)
        print(f"{hash:2} {substring}")
    # [/example]

إليك اختبارًا سريعًا يحسب شيفرة التجزئة لأجزاء من كلمة hashing يتزايد طولها:

example = bytes("hashing", "utf-8")
for i in range(1, len(example) + 1):
    substring = example[:i]
    hash = naive_hash(substring)
    print(f"{hash:2} {substring}")

يكون الخرج ما يلي:

0 b'h'
 6 b'ha'
 4 b'has'
 4 b'hash'
 5 b'hashi'
11 b'hashin'
10 b'hashing'

يبدو الخرج عشوائيًا، نريد إجراء اختبار أكثر صرامة عبر تجربة تجزئة كل سطر نصي في رواية دراكولا -نسخة مشروع جوتنبرج-، ثم نرسم مخططًا بيانيًا للتوزيع:

توزيع شيفرات التجزئة لكل سطر في رواية دراكولا.

تظهر أغلب الدلاء buckets - أي الأعمدة في الرسم البياني- متساوية في الطول، باستثناء ارتفاع ملحوظ عند القيمة صفر، لقد اعتمد تقديرنا لترميز Big O حول مدى كفاءة خوارزميتنا على توزيع الملفات بالتساوي بين المجموعات، فلن تعمل الشيفرة بالسرعة المطلوبة إذا لم يتحقق هذا الشرط.

يتبين بالقليل من البحث أن الملف النصي الذي نستخدمه يستخدم سطرًا فارغًا للفصل بين الفقرات، تنتج هذه الأسطر قيمة تجزئة تساوي صفر، لذا يعكس ذلك الارتفاع توزيعًا غير عادل في البيانات، و ستصبح النتيجة أكثر توازنًا إذا رسمنا توزيع شيفرة التجزئة للأسطر الفريدة فقط:

توزيع شيفرات التجزئة للأسطر الفريدة في رواية دراكولا.

تُعد التجزئة أداة قوية للغاية، حيث تجزئ القواميس في لغة بايثون مثلًا مفاتيحها لتسريع عملية البحث، وبما أننا الآن نستطيع تجزئة الملفات فإننا نستطيع بناء قاموس يستخدم شيفرات التجزئة كمفاتيح ومجموعات أسماء الملفات كقيم:

import sys
from naive_hash import naive_hash


def same_bytes(left_name, right_name):
    left_bytes = open(left_name, "rb").read()
    right_bytes = open(right_name, "rb").read()
    return left_bytes == right_bytes


def find_duplicates(filenames):
    matches = []
    for i_left in range(len(filenames)):
        left = filenames[i_left]
        for i_right in range(i_left):
            right = filenames[i_right]
            if same_bytes(left, right):
                matches.append((left, right))
    return matches


# [group]
def find_groups(filenames):
    groups = {}
    for fn in filenames:
        data = open(fn, "rb").read()
        hash_code = naive_hash(data)
        if hash_code not in groups:
            groups[hash_code] = set()
        groups[hash_code].add(fn)
    return groups
# [/group]


if __name__ == "__main__":
    # [main]
    groups = find_groups(sys.argv[1:])
    for filenames in groups.values():
        duplicates = find_duplicates(list(filenames))
        for (left, right) in duplicates:
            print(left, right)
    # [/main]

تتحقق الشيفرة أعلاه في كل مرة يحسب البرنامج فيها شيفرة تجزئة مما إذا كانت القيمة قد ظهرت من قبل، وينشئ إدخالًا جديدًا إذا لم تكن موجودة في قاموس المجموعات groups، بحيث تكون شيفرة التجزئة هي المفتاح، ويضع مجموعة فارغة كقيمة لها، وهكذا يضمن وجود مجموعة جاهزة لإضافة اسم الملف إليها. انظر المقطع التالي من الشيفرة الذي يوضح منطق تجميع الملفات بناءً على شيفرة التجزئة:

def find_groups(filenames):
    groups = {}
    for fn in filenames:
        data = open(fn, "rb").read()
        hash_code = naive_hash(data)
        if hash_code not in groups:
            groups[hash_code] = set()
        groups[hash_code].add(fn)
    return groups

نستطيع الآن إعادة استخدام معظم الشيفرة التي كتبناها سابقًا للبحث عن التكرارات داخل كل مجموعة على حدة:

groups = find_groups(sys.argv[1:])
for filenames in groups.values():
    duplicates = find_duplicates(list(filenames))
    for (left, right) in duplicates:
        print(left, right)

فيكون الخرج كما يلي:

tests/a2.txt tests/a1.txt
tests/a3.txt tests/a1.txt
tests/a3.txt tests/a2.txt
tests/b1.txt tests/b2.txt

تجزئة أفضل

بالعودة إلى صيغة O(n²/g) التي تخبرنا بمقدار الجهد المطلوب إذا قسمنا n من الملفات على g من المجموعات، فإذا كان لدينا عدد مجموعات يساوي عدد الملفات تمامًا -أي حين تكون n مساوية لـ g- فإن الجهد المطلوب لمعالجة n ملف سيكون O(n²/n) أو O(N) للتبسيط، وهذا يعني أن الجهد المطلوب سيتناسب طرديًا مع عدد الملفات، وبما أننا نحتاج إلى قراءة كل ملف مرة واحدة على الأقل على أي حال فلن نتمكن من تحقيق نتيجة أفضل من هذه، لكن كيف نضمن أن كل ملف فريد سيكون في مجموعته التي ينتمي لها؟

يكمن الحل في استخدام دالة تجزئة تشفيرية Cryptographic hash function تتميز مخرجاتها أنها حتمية، فإذا أعطيتها نفس البايتات بنفس الترتيب ستنتج نفس الخرج في كل مرة، ومع هذا فإن الخرج يتوزع مثل متغير عشوائي منتظم بحيث يتساوى احتمال كل خرج منها مما يضمن توزيع الملفات بالعدل بين المجموعات.

تصعب كتابة دوال التجزئة بالتشفير كما يصعب كذلك إثبات أن خوارزمية ما لديها الخصائص التي نريدها، لذا سنستخدم دالة من مكتبة التجزئة hashlib في لغة بايثون التي تنفذ خوارزمية التجزئة SHA-256.

تنتج هذه الدالة تجزئة بحجم 256 بت عند إعطائها بعض البايتات كمدخلات، وتُكتب عادة كسلسلة نصية من 64 محرف بالنظام الست عشري حيث يستخدم هذا النظام الأحرف A حتى F لتمثيل الأرقام من 10 إلى 15، فتحسب القيمة 3D5 مثلًا كالتالي:

3 × 16² + 13 × 16¹ + 5 × 16⁰ = 981 بالنظام العشري.

from hashlib import sha256

if __name__ == "__main__":
    # [example]
    example = bytes("hash", "utf-8")
    for i in range(1, len(example) + 1):
        substring = example[:i]
        hash = sha256(substring).hexdigest()
        print(f"{substring}\n{hash}")
    # [/example]

ويكون خرجها كما يلي:

b'h'
aaa9402664f1a41f40ebbc52c9993eb66aeb366602958fdfaa283b71e64db123
b'ha'
8693873cd8f8a2d9c7c596477180f851e525f4eaf55a4f637b445cb442a5e340
b'has'
9150c74c5f92d51a92857f4b9678105ba5a676d308339a353b20bd38cd669ce7
b'hash'
d04b98f48e8f8bcc15c6ae5ac050801cd6dcfd428fb5f9e65c4e16e7807340fa

مسألة عيد الميلاد

يمثل احتمال تشارك شخصين في نفس عيد الميلاد 1/365 مع تجاهل يوم 29 فبراير، ومن ثم تكون احتمالية ألا يتشاركاه هو 364/365، وإذا أضفنا شخصًا ثالثًا يكون احتمال ألا يتشارك عيد الميلاد مع الشخصين السابقين هي 363/365، وهكذا يكون الاحتمال الإجمالي لعدم تشارك هؤلاء الأشخاص في نفس عيد الميلاد هي (364/365)*(363/365)، وإذا استمر الحال على هذا النمط سنجد أن هناك احتمالًا بنسبة 50% لوجود شخصين يتشاركان يوم الميلاد نفسه في مجموعة مكونة من 23 شخصًا فقط، تزيد هذه النسبة إلى 99.9% مع وجود 70 شخصًا.

تطبيق المنطق على الملفات

يمكن استخدام نفس المنطق الرياضي لنرى عدد الملفات التي نحتاج إلى تجزئتها قبل أن نصل إلى احتمال حدوث تصادم collision باستخدام تجزئة 256-بت -التصادم في التجزئة يعني أن قيمتين أو أكثر لهما نفس شيفرة التجزئة-، وتخبرنا ويكيبيديا أن الإجابة هي

$4 \times 10^{38}$

ملفًا تقريبًا، وبما أن الرقم كبير للغاية فنحن مستعدون للمخاطرة. يسهم استخدام دالة المكتبة هذه في جعل برنامج البحث عن الملفات المكررة أقصر بكثير:

import sys
from hashlib import sha256

def find_groups(filenames):
    groups = {}
    for fn in filenames:
        data = open(fn, "rb").read()
        hash_code = sha256(data).hexdigest()
        if hash_code not in groups:
            groups[hash_code] = set()
        groups[hash_code].add(fn)
    return groups


if __name__ == "__main__":
    groups = find_groups(sys.argv[1:])
    for filenames in groups.values():
        print(", ".join(sorted(filenames)))

وعند تشغيل البرنامج:

python dup.py tests/*.txt

نحصل على النتائج التالية:

tests/a1.txt, tests/a2.txt, tests/a3.txt
tests/b1.txt, tests/b2.txt
tests/c1.txt

المهم هنا أن هذا المنظور الجديد يستطيع التعامل مع مجموعات ملفات ضخمة جدًا، فنحن لا نحتاج إلا إلى فحص كل ملف مرة واحدة فقط مما يقلل زمن التشغيل إلى أدنى مستوى ممكن.

خاتمة

تلخص الصورة أدناه الأفكار الرئيسية الواردة في هذا الفصل، ولعل أهمها أن بعض الخوارزميات تتفوق على غيرها من حيث الكفاءة والأداء.

خريطة تصور اكتشاف الملفات المكررة باستخدام التجزئة.

• توضح هذه الخريطة كيف ننتقل من المقارنة الثنائية البطيئة O(n²) إلى التوزيع الذكي باستخدام التجزئة.
• تحول دالة التجزئة محتوى الملف إلى بصمة رقمية فريدة.
• يؤدي استخدام خوارزميات مثل SHA-256 إلى تقليل احتمالية التصادمات إلى أدنى مستوياتها.
• يتحسن أداء البرنامج ليصبح زمن التشغيل خطيًا O(n) مما يسمح لنا بمعالجة كميات هائلة من البيانات في وقت قياسي.

اقرأ أيضًا

• تطوير مفسر بايثون Python Interpreter
• بناء لعبة رسومية باستخدام بايثون ووحدة الألعاب Pygame
• أهم الأسئلة النظرية التي قد تطرح في المقابلات لتوظيف مطور بايثون

ترجمة -بتصرف- للفصل Chapter 3: Finding Duplicate Files من كتاب Software Design by Example.