ضغط عالي السرعة مرن (تابع)

هذه المقالة هي بالفعل الثانية في موضوع ضغط البيانات عالية السرعة. وصفت المقالة الأولى ضاغطًا يعمل بسرعة 10 جيجابايت / ثانية. لكل نواة المعالج (الحد الأدنى للضغط ، RTT-Min).

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

كما أعلنت المقالة الأولى عن تطوير خوارزمية ضغط لضغط النسخ الاحتياطي لمحركات الأقراص الصلبة ومحركات أقراص SSD (ضغط متوسط ​​، RTT-Mid) مع معلمات محسنة لضغط البيانات. حتى الآن ، هذا الضاغط جاهز تمامًا وهذه المقالة تخصه.

يوفر الضاغط الذي ينفذ خوارزمية RTT-Mid نسبة ضغط مماثلة لأرشيفات قياسية مثل WinRar ، 7-Zip ، تعمل في الوضع عالي السرعة. علاوة على ذلك ، فإن سرعتها أعلى على الأقل من حيث الحجم.

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

من ناحية أخرى ، يمكن نسخ نفس تيرابايت بسرعات تتراوح بين 2-3 غيغابايت في الثانية لمدة عشر دقائق.

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

لا يمكن للضواغط الحديثة إنتاج هذه السرعات إلا في الوضع "السريع". في هذا الوضع الحالي ، سنقارن خوارزمية RTT-Mid مع الضواغط التقليدية.

اختبار مقارن لخوارزمية الضغط الجديدة

عملت الضاغط RTT-Mid كجزء من برنامج اختبار. في تطبيق "العمل" الحقيقي ، يعمل بشكل أسرع بكثير ، ويستخدم تعدد مؤشرات الترابط بشكل صحيح هناك ، ويستخدم مترجم "طبيعي" ، وليس C #.

نظرًا لأن الضواغط المستخدمة في الاختبار المقارن مبنية على مبادئ مختلفة ويتم ضغط أنواع مختلفة من البيانات بشكل مختلف ، من أجل موضوعية الاختبار ، استخدمنا طريقة قياس "متوسط ​​درجة الحرارة في المستشفى" ...

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

هنا هو ملف التفريغ:



تم ضغط ملف التفريغ بواسطة ضواغط PTT-Mid و 7-zip و WinRar. تم ضبط ضاغط WinRar و 7-zip على أقصى سرعة.

يعمل ضاغط 7 الرمز البريدي :



يتم تحميل المعالج بنسبة 100٪ ، في حين يبلغ متوسط ​​سرعة قراءة التفريغ الأصلي حوالي 60 ميجابايت / ثانية.

ينرر ضاغط يعمل:



الوضع مشابه ، حمل المعالج 100٪ تقريبًا ، يبلغ متوسط ​​سرعة قراءة التفريغ حوالي 125 ميجابايت / ثانية.

كما في الحالة السابقة ، فإن سرعة أرشيف الأرشيف محدودة بقدرات المعالج.

برنامج اختبار الضاغط RTT-Mid يعمل الآن:



توضح لقطة الشاشة أن المعالج قد تم تحميله بنسبة 50٪ وهو في وضع الخمول بقية الوقت ، لأنه لا يوجد مكان لتنزيل البيانات المضغوطة. يتم تحميل قرص تحميل البيانات (القرص 0) بالكامل تقريبًا. سرعة قراءة البيانات (القرص 1) تقفز كثيرًا ، ولكن في المتوسط ​​أكثر من 200 ميجابايت / ثانية.

تقتصر سرعة الضاغط في هذه الحالة على القدرة على كتابة البيانات المضغوطة على القرص 0.

الآن نسبة ضغط المحفوظات الناتجة:







يمكن ملاحظة أن الضاغط RTT-Mid قد عالج الضغط بشكل أفضل من أي شخص آخر ، وكان الأرشيف الذي تم إنشاؤه أصغر بمقدار 1.3 غيغابايت من أرشيف WinRar و 2.1 غيغابايت أصغر من أرشيف 7z.

الوقت المستغرق في إنشاء الأرشيف:

• 7-الرمز البريدي - 26 دقيقة 10 ثانية ؛
• برنامج WinRar - 17 دقيقة و 40 ثانية ؛
• RTT - منتصف - 7 دقائق و 30 ثانية.

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

يمكن لأولئك الذين لا يؤمنون لقطات الشاشة التحقق من دقتها من تلقاء نفسها. برنامج الاختبار متاح هنا ، وتحميل والتحقق.

لكن فقط في المعالجات التي تدعم AVX-2 ، وبدون دعم هذه التعليمات ، لا يعمل الضاغط ولا يختبر الخوارزمية على معالجات AMD الأقدم ، فهي بطيئة فيما يتعلق بتنفيذ أوامر AVX ...

طريقة الضغط المستخدمة

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

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

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

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

لكن العديد من تنسيقات البيانات الحديثة غير قابلة للضغط و "قيادة" ماسحة ضوئية كثيفة الاستخدام عليها غير مجدية ومهدرة ، لذلك ، يستخدم الماسح الضوئي وضعي التشغيل. أولاً ، يتم البحث في أجزاء من النص المصدر مع التكرار المحتمل ، ويتم تنفيذ هذه العملية أيضًا بالطريقة الاحتمالية ويتم تنفيذها بسرعة كبيرة (بسرعة 4-6 غيغابايت / ثانية). ثم تتم معالجة المناطق ذات المطابقات المحتملة بواسطة الماسح الضوئي الرئيسي.

ضغط الفهرس غير فعال للغاية ، يجب عليك استبدال الأجزاء المكررة بفهارس ، كما أن صفيف الفهرس يقلل بشكل كبير من نسبة الضغط.

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

كل هذا جعل من الممكن الحصول على نسبة ضغط في ضاغط PTT-Mid ، قابلة للمقارنة مع الضواغط المصنوعة وفقًا لطريقة القاموس ، ولكن العمل بشكل أسرع بكثير.

سرعة خوارزمية الضغط الجديدة

إذا كان الضاغط يعمل مع الاستخدام الحصري لذاكرة التخزين المؤقت (يلزم 4 ميجابايت لكل تيار) ، فإن السرعة تتراوح من 700 إلى 2000 ميغابايت / ثانية. لكل نواة المعالج ، اعتمادًا على نوع البيانات التي يتم ضغطها والقليل يعتمد على تردد تشغيل المعالج.

مع التنفيذ المتعدد الخيوط للضاغط ، يتم تحديد قابلية التوسع الفعالة من خلال حجم ذاكرة التخزين المؤقت للمستوى الثالث. على سبيل المثال ، بعد "ذاكرة التخزين المؤقت" 9 ميغابايت ، لا معنى لتشغيل أكثر من دفقين للضغط ، ولن تنمو السرعة من هذا. ولكن مع ذاكرة التخزين المؤقت 20 ميغابايت ، يمكنك بالفعل تشغيل خمسة تدفقات ضغط.

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

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

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

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

تخزين موثوق للبيانات المضغوطة

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

أثناء التخزين ، تفقد وسائط التخزين بعض البيانات ، وفيما يلي مثال على ذلك:



يبلغ عمر وسيط التخزين "التماثلي" ألف عام ، وقد فقدت بعض الأجزاء ، لكن المعلومات عمومًا "قابلة للقراءة" ...

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

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

وهذه أيضًا مشكلة كبيرة ، ولكنها ليست مشكلة متأخرة ، لكن المشكلة الحالية.

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

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

من المستحيل استرداد المعلومات من هذا الأرشيف "المعطل".

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

• حقل النص المصدر مع إزالة المقاطع المتكررة منه ؛
• مجال الفهرس.

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

عيوب الخوارزمية

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

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

هذه السرعات المنخفضة غير مقبولة بالنسبة لأنظمة تخزين البيانات الحديثة وهي ذات اهتمام "أكاديمي" أكثر منها عملية.

سيتم زيادة درجة ضغط المعلومات بشكل كبير في التعديل التالي لخوارزمية PTT (RTT-Max) ، وهو بالفعل قيد التطوير.

هكذا ، كما هو الحال دائما ، أن تستمر ...