كيف يمكن حساب المعلمات الأمثل لبدء الخطوة وقفة الترميز المخطط ؟

Question

بداية خطوة توقف رمز هو ضغط البيانات التقنية المستخدمة في ضغط عدد صغير نسبيا.

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

وبالتالي فإن طول الترميز هو l = start + خطوة * أنا.

"أنا" قيمة كود خاص يتم ترميز باستخدام أحادي.وهو رقم من 1 بت تليها إنهاء 0 بت.إذا وصلنا إلى وقف ثم يمكننا إسقاط إنهاء 0 بت.إذا كنت صفرا نحن فقط كتابة 0 بت.

لذلك (1, 2, 5) تبدأ خطوة وقفة قانون العمل على النحو التالي:

القيمة 0, ترميز:0 0
القيمة 1 ، ترميز:0 1
القيمة 2, ترميز:10 000
قيمة 9, ترميز:10 111
قيمة 10, ترميز:11 00000
القيمة 41, ترميز:11 11111

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

Answer 1

هذه "ابدأ خطوة توقف" مدونات يبدو طريقة مختلفة الدعوة هوفمان رموز.ترى التقنية الأساسية عن الخطوط العريضة الزائفة رمز حساب لهم.

أساسا هذا هو ما الخوارزمية لا:

قبل البدء في ترميز هوفمان تحتاج إلى جمع الإحصاءات من كل رمز سوف يكون ضغط (مجموع التردد في ملف ضغط).

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

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

إذا كان تردد احصائيات ليست فرز سوف يستغرق O(nlog ن) القيام به ، إذا كان يتم فرزها حسب التردد يمكن القيام به في O(n).

هوفمان رموز ويضمن الحصول على أفضل متوسط ضغط هذا النوع من التشفير:

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

وهذا ينبغي أن تساعدك على تنفيذ الحل الأمثل لمشكلتك.

تحرير: على الرغم مماثلة ، هذا ليس ما OP كان يبحث عن.

هذا ورقة الأكاديمية من قبل خالق هذه الرموز يصف التعميم من بدء الخطوة وقفة رموز الإيقاف رموز.بيد أن المؤلف يصف بإيجاز كيفية الحصول على أفضل بداية خطوة وقف بالقرب من نهاية القسم 2.أنه ينطوي على استخدام إحصائية لمتغير عشوائي ، أو القوة الغاشمة تمويل أفضل مزيج.دون أي معرفة مسبقة من الملف الخوارزمية O((log n)^3).

ويساعد هذا الأمل.

Answer 2

نهج اعتدت كانت القوة الغاشمة بسيطة الحل.الخوارزمية اتبعت هذه الخطوات الأساسية:

1. عد تكرار كل رقم في الملف.في نفس تمرير حساب مجموع الأرقام في الملف و تحديد أكبر عدد maxNumber.

2. حساب احتمال كل عدد كما تردد مقسوما على مجموع الأرقام في الملف.

3. تحديد "optimalStop" كما يساوي log2(maxNumber).هذا هو المثل الأعلى عدد البتات التي يجب استخدامها لتمثيل maxNumber كما في شانون نظرية المعلومات وبالتالي تقدير معقول الأمثل قدر ممكن من البتات المستخدمة في ترميز عدد معين.

4. كل "ابدأ" قيمة من 1 إلى "optimalStop" كرر الخطوة 5 - 7:

5. كل "خطوة" قيمة من 1 إلى ("optimalStop" - "ابدأ") / 2 ، كرر الخطوة 6 و 7:

6. حساب "وقف" القيمة الأقرب إلى "optimalStop" الذي يرضي وقف = start + خطوة * أنا وبعض صحيح أنا.

7. حساب متوسط عدد البتات التي يمكن استخدامها من قبل هذا الترميز.هذا ويمكن حساب كل رقم هو احتمال مضروبا في طول بت في الترميز.

8. اختيار ترميز مع أدنى متوسط عدد البتات.