حساب التشابه البيانات الثنائية

Question

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

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

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

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

بعض المخاوف للنظر عند الخروج مع النهج المحتملة:

• تختلف ROM في الحجم بشكل كبير، اعتمادا على النظام. بعضها صغير، لكن الأنظمة الحديثة قد يكون لها عدد كبير أو 256 ميجابايت أو أكثر. بعض الأنظمة (الكل؟) لديها فقط صلاحيات 2 كحجام ممكنة، كانت لعبة 130 ميجابايت على إحدى هذه الأنظمة سيكون لها مدمج 256 ميجابايت، فارغة إلى حد كبير. لاحظ أنه لهذا السبب، قد يكون لدى بعض الحيوانات المستنسخة أحجاما مختلفة بعنف، إذا تعبر إصدار اللعبة العتبة وعلي استخدام خرطوشة ضعف الحجم.
• يوجد حاليا الآلاف من روم من الأنظمة المعروفة في العديد من الأنظمة، مع وجود معظم الأنظمة التي تزال تواجهها جديدة أصدرت باستمرار. حتى بالنسبة للأنظمة الأكبر سنا، يوجد مجتمع رئيسي ل ROM-Hacking ينتج مدمجا معدلا في كثير من الأحيان.
• تخزين بيانات التشابه لكل زوج ممكن من روم من شأنه أن يؤدي إلى ملايين الصفوف من البيانات لأي من الأنظمة الأكثر شعبية. سيتطلب نظام مع 5000 روم 25 مليون صف بيانات التشابه، مع لعبة جديدة واحدة تضيف 5000 صفوف أخرى.
• يجب أن تكون حالة المعالجة قابلة للاسترداد، بحيث يمكن أن تقاطعت، يمكن أن تلتقط المكان الذي توقفت فيه. مع أي طريقة، ستكون هناك حاجة إلى الكثير من المعالجة، والافتراض على أن الأمر كله سيتم تشغيله في دفعة واحدة غير آمنة.
• يمكن إضافة ROM جديدة في أي وقت، لذلك يجب ألا تفترض الطريقة أنه يحتوي بالفعل على مجموعة "كاملة". وهذا هو، حتى بعد أن أحسب بالفعل تشابها بالفعل لجميع ROM الموجودة، إذا تمت إضافة واحدة جديدة (وهذا قد يحدث أيضا قبل انتهاء المعالجة السابقة بالكامل)، يجب أن يكون هناك طريقة لمقارنتها بجميع تلك السابقة، لتحديد الذي (إن وجد) هو استنساخ.
• يجب إعطاء سرعة معالجة أعلى أولوية على الدقة (إلى حد ما). معرفة ما إذا كانت مدمجة مدمجة 94٪ أو 96٪ مماثلة ليست مهمة بشكل خاص، ولكن إذا استغرقت يوم المعالجة لمقارنة مدمج جديد لجميع السابقة، فمن المحتمل أن يكون البرنامج قد لا يكمل حقا.

لقد كانت مشكلة مثيرة للاهتمام للعمل عليها، وأتطلع إلى رؤية ما يمكن للأشخاص الآخرين من التوصل إليه. اسمحوا لي أن أعرف في التعليقات إذا كنت تريد المزيد من التفاصيل، وسأحاول توفيرها.

Answer 1

يبدو أنك تريد دلتا ثنائية أو ربما فهرس مشتق من تطبيق دلتا ثنائية (مثل حجمها). يمكنك بعد ذلك مقارنة هذا الفهرس ببعض الأساس الذي تحدده بشكل تجريبي لاتخاذ قرار إذا كان "استنساخ" أم لا.

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

ومع ذلك، فإن المقارنة الزوجية لكل ملف ثنائي في قاعدة البيانات الخاصة بك ربما باهظة الثمن (O (N²)، أظن). سأحاول العثور على تجزئة بسيطة لتحديد المرشحين المحتملين للمقارنة. شيء مماثل من الناحية المعنية بما يقترحه spdenne و eduard. وهذا هو، والعثور على التجزئة التي يمكن تطبيقها على كل بند مرة واحدة، وفرز تلك القائمة، ثم استخدم مقارنة بذاتها المحبوسة على العناصر التي تقتصر تجزئها معا في القائمة.

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

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

إذا لم تحصل لك وظائف التجزئة على طول الطريق (أو أنها تتطلب إدخالا من نوعا ما لتحديد أداة قياس / مسافة)، فهناك العديد من خوارزميات وتنفيذ Delta Binary المتوفرة على الويب. يتم استخدام الجهاز الذي أعمل به أكثر دراية من قبل نظام التحكم في إصدار التخريب. يستخدم خوارزمية دلتا ثنائية تسمى XDELTA لتخزين مراجعات الملفات الثنائية بكفاءة. إليك رابط مباشرة إلى الملف في مستودعه الذي ينفذه: XDELTA.C.. وبعد ربما هناك أداة على الويب التي تجعل هذا أكثر قابلية للوصول أيضا.

Answer 2

قد ترغب في النظر في BSDIFF., ، وهو نظام تخفيض / ترقيع ثنائي. هناك أيضا أطروحة مع الكثير من النظرية.

Answer 3

استخدام بعض الأفكار من اكتشاف الانتحال الخوارزميات.

فكرتي:

من أجل إنشاء "توقيع" قابل للمقارنة لكل مدمج، يختلف الأمر قليلا كأجزاء صغيرة، وإنتاج شيء مثل رسم بياني تردد Word، ولكن بدلا من تسجيل ترددات الكلمات، يمكنك التجزئة أقسام قصيرة جدا من ROM، وتسجيل ترددات قيم التجزئة.

لا تتجز فقط قسم واحد، ثم القسم التالي الذي يبدأ من نهاية القسم الأول، ولكن بدلا من ذلك استخدام نافذة انزلاقية، قم بإلغاء القسم بدءا من البايت 1، ثم Hash نفس قسم الحجم الذي يبدأ من البايت 2، ثم من البايت 3، وما إلى ذلك سوف ينفي تأثير أجزاء متغيرة الحجم المتغيرة داخل ROM الخاص بك.

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

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

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

Answer 4

على الرغم من أنه كان أكثر بكثير من "يومين"، فقد أحسب أنني يجب أن أضيف حلاي الحالي هنا.

كان nils pipenbrinck في نفس الاتجاه مثل طريقتي الحالية. نظرا لأن أحد النتائج الرئيسية للعثور على الحيوانات المستنسخة هو مدخرات هائلة من الأرشفة الصلبة، فقد أحسب أنني قد أحاول فقط ضغط أي رومان معا ورؤية مقدار المساحة التي تم حفظها. أنا أستخدم خوارزمية LZMA في 7Zip. لهذا.

الخطوة الأولى هي ضغط كل ROM بشكل فردي ولاحظ الحجم المضغوط، ثم حاول أرشفة أي رومان معا ومعرفة مقدار حجم الحجم الناتج عن أحجامهم المضغوطة الفردية. إذا كان الحجم المجمع هو نفس مجموع الأحجام الفردية، فهي تشبه 0٪، وإذا كان الحجم هو نفسه واحد منهم (أكبر واحد)، فهي متطابقة.

الآن، هذا عدد كبير من محاولات الضغط المطلوبة، لذلك لدي بضع من التحسينات حتى الآن (وترغب في معرفة المزيد):

1. إعطاء الأولوية للمقارنات بناء على مدى مماثلة الأحجام المضغوطة. إذا كان لدى ROM A يحتوي على حجم مضغوط من 10 ميغابايت و ROM B يحتوي على حجم مضغوط من 2 ميغابايت، فمن المستحيل بالنسبة لهم أن يكونوا أكثر من 20٪ مماثلة، لذلك يمكن تركها للحصول على النتيجة الحقيقية حتى وقت لاحق. يعمل تشغيل خوارزمية الضغط نفسها على ملفات مشابهة للغاية يؤدي إلى نتائج مماثلة الحجم، لذلك يجد هذا الكثير من الحيوانات المستنسخة بسرعة كبيرة.

2. جنبا إلى جنب مع ما سبق، والحفاظ على كل من الحدود العليا والسفلى "على التشابه المحتمل بين أي زوج من روم. هذا يسمح بتقديم تحديد الأولويات. إذا كانت ROM A و B هي 95٪ مماثلة، و LOMS B و C فقط 2٪ فقط، فأنت تعرف بالفعل أن A و C هي بين 0٪ و 7٪. هذا منخفض للغاية ليكون استنساخا، لذلك يمكن تأجيل هذه المقارنة بأمان أو تجاهلها بالكامل، إلا إذا أردت حقا معرفة أوجه التشابه الدقيق لكل شيء.

Answer 5

أعتقد أن بعض التقنيات المقترضة من ضغط البيانات قد تكون مثيرة للاهتمام هنا:

افترض أن لديك اثنين من الملفات، A و B.

ضغط كل ملف بشكل فردي وإضافة الأحجام المضغوطة معا. ثم قم بتسلسل الملفين إلى ملف واحد وملف كبير وضغطه أيضا.

سوف يمنحك الفرق في الأحجام تقديرا تقريبا مدى تشبه الملفات.

أقترح عليك أن تحاول تحويل ويلر الجحر (BZIP2) للقيام بالضغط. معظم خوارزميات الضغط الأخرى لديها فقط تاريخ محدود. يمكن أن تعمل خوارزمية BWT Otoh على قطع كبيرة جدا من البيانات. الخوارزمية "ترى" كلا الملفين في نفس الوقت وأي تشابه سيؤدي إلى نسبة ضغط أعلى.

Answer 6

Xdelta مفيد جدا للحصول على فرق ثنائية لائقة: http://xdelta.org.

Answer 7

يمكنك البدء عن طريق تخزين شيء مثل أشجار التجزئة. وبعد هناك حاجة فقط لتخزين مجموعة من هذه المجموعة من التجزئة لكل مدمج، ومساحة التخزين المطلوبة تتناسب فقط مع (ولكن أقل بكثير من) حجم ROM، على افتراض حجم كتلة ثابتة. يجب أن يمنح حجم الكتلة المختارة حبيبيا كافيا لضمان الدقة، على سبيل المثال: بالنسبة لحجم الحد الأدنى من 128 ميغا وايت، قيود الدقة بنسبة 1٪ و تايجر 128 التجزئة (على غرار ما يستخدمونه للتحقق من الملفات المنقولة عبر DirectConnect)، فإن حجم كتلة 1Mib لا يرغب بشكل جيد ويمكنك تخزين جميع التجزئة في 128 * 128/8 = 2048 بايت! لذلك فإن القيام بذلك ل 10000 روم ستطلب فقط حوالي 20MIB من الفضاء. علاوة على ذلك، يمكنك اختيار Hash أقل أمانا، ولكن أسرع و / أو أصغر. إضافة / التحقق من التشابه، وسيستلزم ROM الجديد شيئا مثل:

1. انقسام مدمج جديد في كتل ولديه كل منهم.
2. لكل ROM بالفعل في قاعدة البيانات، قارن (انظر أدناه) Males Males مع Meshes الجديد ROM.

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

كما ترى، يتم تقليل المشكلة إلى أداء واحد من الأداء: التحقق من مجموعات بيانات أصغر بكثير للتشابه.

Answer 8

أفكاران:

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

Answer 9

كما قال ويلون فلين، قد تحتاج إلى خوارزمية دلتا ثنائية. ال خوارزمية RSYNC. هو جيد. إنه سريع وموثوق به. انظر أيضا وثائق الأداة المساعدة.

Answer 10

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

سيكون الحل سريع والقذرة هو اختراق حل مع Difflib. (أو ما يعادل ث / لغتك المفضلة)، لأنها تحصل على مقارنة انزلاق يمكن أن تتعامل مع إضافة البيانات أو الإزالة. قم بتقسيم ROM إلى أقسام تنفيذية وقسم بيانات (إن أمكن). يمكن مقارنة قسم البيانات مباشرة و نسبة التشابه المحسوبة, على الرغم من أنك لا تزال تواجه مشكلات ث / عناوين أو إزاحة.

القسم القابل للتنفيذ هو أكثر إثارة للاهتمام. قم بقراءة تنسيق ASM للآلة، واتخاذ الملف القابل للتنفيذ وتقسيمه إلى سلسلة من OPCodes. اترك أجزاء Opcode وتسجيل الأجزاء، ولكن قناع خارج الأجزاء "الحمولة" / "الفورية" (حيث تقوم بتحميل العناوين المتغيرة). تسليم المعلومات الناتجة إلى حاسبة نسبة التشابه أيضا.

الجزء المؤسف هو أن هذا لا يزال عملية o (n ^ 2) على عدد ROM الذي تتبعه، ولكن يمكن تخفيفه باستخدام (تدريجي) أو ترتيب مقارنة على أساس التردد لتقليل مقدار المقارنات اللازمة.