إنشاء التصحيح الثنائي في C#
https://stackoverflow.com/questions/5831
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل لدى أي شخص، أو يعرف، تطبيق خوارزمية إنشاء التصحيح الثنائي في C#؟
في الأساس، قارن بين ملفين (المعينين قديم و جديد)، وإنتاج ملف تصحيح يمكن استخدامه لترقية ملف قديم أن يحتوي الملف على نفس محتويات ملف جديد ملف.
يجب أن يكون التنفيذ سريعًا نسبيًا، وأن يعمل مع ملفات ضخمة.يجب أن يعرض أوقات تشغيل O(n) أو O(logn).
تميل الخوارزميات الخاصة بي إلى أن تكون إما رديئة (سريعة ولكنها تنتج تصحيحات ضخمة) أو بطيئة (تنتج تصحيحات صغيرة ولكن لها وقت تشغيل O(n^2).
أي نصيحة أو مؤشرات للتنفيذ ستكون لطيفة.
على وجه التحديد، سيتم استخدام التنفيذ للحفاظ على مزامنة الخوادم مع العديد من ملفات البيانات الكبيرة التي لدينا خادم رئيسي واحد لها.عندما تتغير ملفات بيانات الخادم الرئيسي، نحتاج إلى تحديث العديد من الخوادم خارج الموقع أيضًا.
الخوارزمية الأكثر سذاجة التي قمت بها، والتي تعمل فقط مع الملفات التي يمكن حفظها في الذاكرة، هي كما يلي:
- احصل على البايتات الأربع الأولى من ملف قديم الملف، أطلق عليه اسم مفتاح
- أضف تلك البايتات إلى القاموس، حيث المفتاح -> الموضع, ، أين موضع هو الموضع الذي أمسكت فيه بتلك البايتات الأربع، 0 للبدء بها
- تخطي أول هذه البايتات الأربع، واحصل على 4 بايتات أخرى (3 متداخلة، وواحدة واحدة)، وأضفها إلى القاموس بنفس الطريقة
- كرر الخطوات من 1 إلى 3 لجميع الكتل ذات 4 بايت في الملف قديم ملف
- من بداية جديد ملف، واحصل على 4 بايت، وحاول البحث عنه في القاموس
- إذا تم العثور عليه، فابحث عن أطول تطابق إذا كان هناك عدة تطابقات، وذلك من خلال مقارنة وحدات البايت من الملفين
- قم بترميز مرجع إلى هذا الموقع في ملف قديم الملف، وتخطي الكتلة المتطابقة في ملف جديد ملف
- إذا لم يتم العثور عليه، قم بتشفير بايت واحد من الملف جديد الملف، وتخطيه
- كرر الخطوات من 5 إلى 8 لبقية الخطوات جديد ملف
هذا يشبه إلى حد ما الضغط، بدون نوافذ، لذلك سيستهلك قدرًا كبيرًا من الذاكرة.ومع ذلك، فهو سريع إلى حد ما، وينتج تصحيحات صغيرة جدًا، طالما أنني أحاول جعل إخراج الرموز في حده الأدنى.
تستخدم الخوارزمية الأكثر كفاءة في الذاكرة النوافذ، ولكنها تنتج ملفات تصحيح أكبر بكثير.
هناك المزيد من الفروق الدقيقة في الخوارزمية المذكورة أعلاه والتي تخطيتها في هذا المنشور، ولكن يمكنني نشر المزيد من التفاصيل إذا لزم الأمر.ومع ذلك، أشعر أنني بحاجة إلى خوارزمية مختلفة تمامًا، لذا فإن تحسين الخوارزمية المذكورة أعلاه ربما لن يقودني إلى ما يكفي.
تحرير رقم 1:فيما يلي وصف أكثر تفصيلاً للخوارزمية المذكورة أعلاه.
أولاً، قم بدمج الملفين، بحيث يكون لديك ملف واحد كبير.تذكر نقطة القطع بين الملفين.
ثانيا، افعل ذلك احصل على 4 بايت وأضف موضعها إلى القاموس خطوة لكل شيء في الملف بأكمله.
ثالثاً: من أين جديد عند بدء الملف، قم بإجراء الحلقة مع محاولة تحديد موقع مجموعة موجودة مكونة من 4 بايت، والعثور على أطول تطابق.تأكد من أننا نأخذ في الاعتبار فقط المواضع من الملف القديم، أو من في وقت سابق من الملف الجديد عما نحن عليه حاليًا.وهذا يضمن أنه يمكننا إعادة استخدام المواد في كل من الملف القديم والجديد أثناء تطبيق التصحيح.
تحرير رقم 2: كود المصدر للخوارزمية المذكورة أعلاه
قد تحصل على تحذير بشأن وجود بعض المشاكل في الشهادة.لا أعرف كيفية حل هذه المشكلة، لذا اقبل الشهادة في الوقت الحالي.
يستخدم المصدر الكثير من الأنواع الأخرى من بقية مكتبتي، لذا فإن هذا الملف ليس كل ما يتطلبه الأمر، ولكن هذا هو تنفيذ الخوارزمية.
@ lomaxx، لقد حاولت العثور على وثائق جيدة للخوارزمية المستخدمة في التخريب، تسمى xdelta، ولكن ما لم تكن تعرف بالفعل كيفية عمل الخوارزمية، فإن المستندات التي وجدتها تفشل في إخباري بما أحتاج إلى معرفته.
أو ربما أنا فقط كثيفة...:)
لقد ألقيت نظرة سريعة على الخوارزمية من ذلك الموقع الذي قدمته، وهي للأسف غير قابلة للاستخدام.يقول تعليق من ملف الفرق الثنائي:
يتطلب العثور على مجموعة مثالية من الاختلافات وقتًا تربيعيًا بالنسبة لحجم الإدخال، لذلك يصبح غير قابل للاستخدام بسرعة كبيرة.
ومع ذلك، فإن احتياجاتي ليست مثالية، لذا فأنا أبحث عن حل عملي أكثر.
شكرًا على الإجابة، وأضفت إشارة مرجعية إلى أدواته المساعدة إذا كنت بحاجة إليها.
تحرير رقم 1:ملاحظة، سألقي نظرة على الكود الخاص به لمعرفة ما إذا كان بإمكاني العثور على بعض الأفكار، وسأرسل له أيضًا بريدًا إلكترونيًا لاحقًا يتضمن أسئلة، لكنني قرأت ذلك الكتاب الذي يشير إليه وعلى الرغم من أن الحل جيد للعثور على الحلول المثلى، فهو غير عملي في الاستخدام بسبب متطلبات الوقت.
تحرير رقم 2:سأقوم بالتأكيد بمطاردة تطبيق python xdelta.
المحلول
آسف لم أستطع تقديم المزيد من المساعدة.سأستمر بالتأكيد في النظر إلى xdelta لأنني استخدمته عدة مرات لإنتاج اختلافات الجودة على ملفات ISO بحجم 600 ميجا بايت + التي أنشأناها لتوزيع منتجاتنا وهو يعمل بشكل جيد للغاية.
نصائح أخرى
com.bsdiff تم تصميمه لإنشاء تصحيحات صغيرة جدًا للملفات الثنائية.كما هو مذكور على صفحتها، فإنه يتطلب max(17*n,9*n+m)+O(1) بايت من الذاكرة ويعمل فيها O((n+m) log n) الوقت (أين n هو حجم الملف القديم و m هو حجم الملف الجديد).
التنفيذ الأصلي موجود في لغة C، ولكن تم وصف منفذ C# هنا ومتاح هنا.
هل رأيت VCDiff؟وهو جزء من مكتبة Misc التي تبدو نشطة إلى حد ما (الإصدار الأخير r259، 23 أبريل 2008).لم أستخدمه، ولكن أعتقد أنه يستحق الذكر.
قد يكون من المفيد التحقق مما يفعله بعض الأشخاص الآخرين في هذا المجال وليس بالضرورة في مجال C# أيضًا.
يحتوي SVN أيضًا على خوارزمية فرق ثنائية وأعلم أن هناك تطبيقًا في python على الرغم من أنني لم أتمكن من العثور عليه من خلال البحث السريع.قد يعطونك بعض الأفكار حول مكان تحسين الخوارزمية الخاصة بك
إذا كان هذا للتثبيت أو التوزيع، فهل فكرت في استخدام Windows Installer SDK؟لديه القدرة على تصحيح الملفات الثنائية.
http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx
هذا دليل تقريبي، ولكن ما يلي مخصص لخوارزمية rsync التي يمكن استخدامها لإنشاء تصحيحاتك الثنائية.
