نظرية:خوارزمية ضغط أن يجعل بعض الملفات أصغر ولكن لا شيء أكبر ؟

Question

جئت عبر هذا السؤال ؛

"ضياع خوارزمية ضغط المطالبات إلى ضمان جعل بعض الملفات أصغر و لا ملفات أكبر.
هو هذا ؛

أ) من المستحيل

ب) ممكن ولكن قد تعمل لفترة غير محددة من الوقت ،

ج) من الممكن عامل ضغط 2 أو أقل ،

د) من الممكن لأي ضغط عامل؟"

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

Answer 1

من قبل مبدأ ثقب الحمام، نظرا لسلسلة من 10 بتات لديك 1024 مدخلات محتملة، وتحتاج إلى الخريطة إلى 9 بت أو أقل، لذلك هناك <1024 مخرجات.

هذه الضمانات إما الخوارزمية لديها تصادمات (ضغط ضياع) أو في مرحلة ما أدنى لإرجاع المدخلات غير الموصوفة كمخرجات.

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

-> مستحيل.

Answer 2

مجرد توضيح طفيف لمنصب Rjfalconer's ...

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

ومع ذلك، قيل لنا أن هناك ملف واحد على الأقل التي تصبح أصغر. بدون فقدان العمومية، فكر في أن البدء ب X بت وينتهي بك الأمر كالبارات ذ، حيث Y أقل بدقة من x.

الآن النظر في مجال "الملفات مع البتات y أو أقل"، والتي لديها 2^{Y + 1.}-1 بت سلاسل (بما في ذلك الفارغة واحدة). من أجل أي من هؤلاء الذين ينتجوا في ملف أكبر، يتعين على كل منها تعيين سلسلة بت في نفس المجال، أي 2^{Y + 1.}-1 الملفات المضغوطة. ومع ذلك، نحن نعلم بالفعل أن السلسلة الأولية لطول البتات X يضغط إلى إحدى هذه القيم - ترك فقط 2^{Y + 1.}-2 القيم المحتملة.

في هذه Point The Pigeon Hole Prederle يأتي - من الواضح أنك لا تستطيع الخريطة 2^{Y + 1.}-1 المدخلات إلى 2^{Y + 1.}-2 مخرجات دون تكرار إخراج، والذي ينتهك انعكاس الضغط.

Answer 3

أ) مستحيل

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

Answer 4

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

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

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

وقال أن لدينا الآن على الأقل طريقتين لإظهار أنه في الحقيقة لا توجد مثل هذه الخوارزمية:

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

2. ونحن يمكن أن تحد من عدد من الملفات تكون مضغوطة, مركز منها على الأقل X بت طويلة.مرة أخرى تافهة حل هو ترك كل ملف يمسها إلا واحد ، أننا يمكن أن تقلل مما يجعل من مباراة إلى ملف أصغر من X بت.الآن نحن لا وقد خوارزمية والتي نقلا حرفيا يجعل بعض الملفات أصغر و لا ملفات أكبر ؛ ومع ذلك ، فإنه يؤدي فرض قيود على جميع المدخلات الممكنة (أيفإنه لا يمكن معالجة كل الملفات).

إلى أولئك الذين يقولون أن هذا لن يكون له أي فائدة عملية ، أقول أنني أتفق معك...لكن هذه النظرية و هذا كان مجرد النظرية أطروحة.;)

من الواضح إذا كان لي أن تفعل اختبار و وجه هذا السؤال سأضع جريئة X على a), ثم تذهب فقط من دون التفكير كثيرا حول هذا الموضوع.

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

Answer 5

ه) ممكن

... مع بعض القيود.

لقد صادفت مؤخرا شوكو, ، مكتبة ضغط السلسلة للحصول على سلاسل صغيرة. تم تذكيري بهذا السؤال عند قراءة هذا المطالبة:

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

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

http://ed-von-schleck.github.io/shoco/#how-it-works.

Answer 6

المستطاع

to make some files smaller and no files larger

إذا كان خوارزمية الضغط المذكورة يجعل الملف أكبر، فعليك إرجاع الملف الأصلي.