خوارزمية للتمييز الفعال للملفات الضخمة

Question

لا بد لي من تخزين ملفين A و B وكلاهما كبير جدًا (مثل 100 جيجابايت).ومع ذلك، من المحتمل أن يكون B مشابهًا في أجزاء كبيرة لـ A حتى أتمكن من تخزين A والاختلاف (A، B).هناك جانبان مثيران للاهتمام لهذه المشكلة:

1. الملفات كبيرة جدًا بحيث لا يمكن تحليلها بواسطة أي مكتبة فرق أعرفها لأنها موجودة في الذاكرة
2. لا أحتاج في الواقع إلى فرق - فعادةً ما يحتوي الفرق على عمليات إدراج وتحرير وحذف لأنه من المفترض أن يقرأه البشر.يمكنني الابتعاد بمعلومات أقل:أحتاج فقط إلى "نطاق جديد من البايتات" و"نسخ البايتات من الملف القديم من الإزاحة التعسفية".

أنا حاليًا في حيرة بشأن كيفية حساب الدلتا من A إلى B في ظل هذه الظروف.هل يعرف أحد خوارزمية لهذا؟

مرة أخرى المشكلة بسيطة:اكتب خوارزمية يمكنها تخزين الملفين A وB بأقل عدد ممكن من البايتات مع الأخذ في الاعتبار أن كلاهما متشابهان تمامًا.

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

Answer 1

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

Answer 2

يمكنك استخدام rdiff, ، الذي يعمل بشكل جيد للغاية مع الملفات الكبيرة. هنا أقوم بإنشاء فرقتين من ملفتين كبيرتين A و B:

1. إنشاء توقيع ملف واحد، مع مثل

   rdiff signature A sig.txt
   

2. باستخدام ملف التوقيع الذي تم إنشاؤه sig.txt والملف الكبير الآخر، قم بإنشاء دلتا:

   rdiff delta sig.txt B delta
   

3. حاليا delta يحتوي على جميع المعلومات التي تحتاجها لإعادة إنشاء الملف B عندما يكون لديك كلا A و delta. وبعد لإعادة إنشاء B، تشغيل

   rdiff patch A delta B
   

في أوبونتو، فقط تشغيل sudo apt-get install rdiff لتثبيته. إنه سريع جدا، أحصل على حوالي 40 ميغابايت في الثانية في جهاز الكمبيوتر الخاص بي. لقد جربتها فقط على ملف 8GB، وكانت الذاكرة المستخدمة من قبل RSYNC حوالي 1 ميغابايت.

Answer 3

هذا هو بالضبط المشكلة المعروفة باسم "Data DataPlication". وبعد النهج الأكثر استخداما هو:

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

هذه خوارزمية Data DataTrication ليست دقيقة كما مثل Xdelta., ، لكنه أسرع وأكثر قابلية للتوسعة لمجموعات البيانات الكبيرة. يتم إجراء البصمات والصناعة بحوالي 50 ميغابايت / ثانية لكل كور (Java). يعتمد حجم الفهرس على التكرار وحجم الفريق وحجم البيانات. مقابل 200 جيجابايت، يجب أن يصلح في الذاكرة لأحجام قطع قطعة من 16 كيلو بايت.

bentleys و mciloys نهج الضغط متشابه جدا (على سبيل المثال بواسطة googles bigtable)، ومع ذلك أنا لست على علم بأي أدوات سطر الأوامر خارج الصندوق باستخدام تقنية الضغط.

ال "FS-C" يحتوي مشروع مفتوح المصدر على معظم الكود الضروري. ومع ذلك، يحاول FS-C نفسه فقط لقياس التكرار والملفات الشرجية في الذاكرة أو باستخدام هادوب العنقودية.

Answer 4

سؤال واحد هو ما هو حجم السجل في الملفات الخاصة بك، أي.هل يمكن تغيير الإزاحات بايتًا تلو الآخر أو أن الملفات تتكون من كتل 1024 بايت على سبيل المثال.بافتراض أن البيانات موجهة بالبايت، يمكنك القيام بما يلي:

1. قم بإنشاء مصفوفة لاحقة للملف A.هذه المصفوفة عبارة عن تبديل لجميع قيم الفهرس للملف A.إذا كان A يحتوي على 2^37 بايت، فمن الأسهل تمثيل مصفوفة الفهرس بأعداد صحيحة 64 بت، لذا فإن كل بايت (إزاحة للملف) يتوافق مع 8 بايت في مصفوفة الفهرس، وبالتالي سيكون طول مصفوفة الفهرس 2^40 بايت. .على سبيل المثال800 جيجابايت، على سبيل المثال.يمكنك أيضًا فهرسة كل موقع رقم 1024 فقط، على سبيل المثال، لتقليل حجم مصفوفة الفهرس.يؤدي هذا بعد ذلك إلى إضعاف جودة التعبئة اعتمادًا على طول متوسط ​​تشغيل الأجزاء القابلة للنسخ.

2. الآن، لحزم الملف B بجشع، تبدأ من بدايته عند الإزاحة o=0 ثم تستخدم مصفوفة الفهرس للعثور على أطول تطابق في A الذي يطابق البيانات التي تبدأ من 'o'.يمكنك إخراج الزوج في الملف المعبأ.يأخذ هذا في حالتك دون أي تشفير 16 بايت، لذلك إذا كان التشغيل أقل من 16 بايت فإنك تفقد المساحة بالفعل.يمكن معالجة ذلك بسهولة عن طريق استخدام التشفير على مستوى البت واستخدام علامة البت لتحديد ما إذا كنت تقوم بتشفير بايت معزول (علامة + 8 بت = 9 بت) أو زوج إزاحة/طول (علامة + 40 بت + 40 بت = 81) بت)، على سبيل المثال.بعد تعبئة الجزء الأطول عند o، قم بزيادة o إلى البايت التالي بعد الجزء وكرر ذلك حتى نهاية الملف.

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

Answer 5

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

إذا كنت بحاجة إلى محاذاة بايت تعسفي وأنت تهتم حقا بالأداء، انظر إلى simhash. خوارزمية, واستخدامه للعثور على كتل مماثلة ولكن غير إظام.