علاقة الكون إلى ضياع معدل ضغط

Question

من شانون مصدر نظرية الترميز ونحن نعلم أن الكون من ضغط سلسلة يحدها الكون من السلسلة الأصلية كما يلي:

H(X) <= L < H(X) + 1/N 

حيث H(X) هو الكون من سلسلة المصدر ، N هو طول سلسلة المصدر و L هو طول المضغوط السلسلة.

هذا يعني بالضرورة أن هناك حد الضياع.

ما أود أن أعرفه هو:

• يمكننا أن تتصل مباشرة الكون إلى بعض المتوقع ضغط النسبة ؟

• يمكن أن نستخدم الكون أن تجد بعض العليا متجهة نسبة الضغط?

Answer 1

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

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

Answer 2

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

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

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

1. إذا كان الإدخال سلسلة يساوي قبل اختيار سلسلة عشوائية, فإن الناتج هو 1-bit string "0"
2. وإلا فإن الناتج هو N+1 بت سلسلة "1" تليها سلسلة الإدخال

المقابلة الضغط الخوارزمية:

1. إذا كان الإدخال "0", الإخراج هو السابق قبل اختيار سلسلة عشوائية
2. وإلا فإن الناتج هو كل شيء ما عدا الإدخال الأول بت

المفتاح هنا هو أنه لا يمكن أن أكتب واحد خوارزمية والتي لجميع سلاسل من معين توزيع كمادات عليها كل بمعدل مرتفع في المتوسط.هناك الكثير من السلاسل.

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

Answer 3

نعم. ال معدل انتروبيا غالبا ما يتم الاستشهاد في اللغة الإنجليزية بنسبة 1.5 بت لكل حرف (أعط أو تأخذ). الترميزات النموذجية تستخدم 8 بت لكل حرف. لذلك يجب أن يكون نص مضغوط أقصى 1.5 / 8 (~ 19٪) حجم الأصل. النتائج الفعلية للحصول على نسخة نصية عادي من فخر وبريد جين أوستن: Orig = 701K، bzip2 = 178k، لمدة ~ 25٪.

Answer 4

نعم!أعتقد هذه الورقة سوف نقطة لكم في الاتجاه الصحيح.

ETA يبدو أنك تحتاج إلى أن تكون IEEE الأعضاء إلى قراءة الورق الفعلي.إذا كان شخص ما يمكن أن تجد والموارد المتاحة للجمهور (أو شرح الرياضيات هنا), سيكون ذلك أفضل بكثير من الحال!