شانون الكون الصيغة.مساعدة بلدي الارتباك

Question

فهمي الكون الصيغة التي تستخدم لحساب الحد الأدنى من عدد البتات المطلوبة لتمثيل بعض البيانات.انها عادة ما تكون مصاغة بشكل مختلف عندما محددة ، ولكن الفهم السابق هو ما اعتمد على حتى الآن.

هنا مشكلتي.لنفترض لدي تسلسل 100 '1' تليها 100 '0' = 200 بت.الأبجدية {0,1}, قاعدة الكون هو 2.احتمال رمز "0" 0.5 "1" هو 0.5.وبالتالي فإن الكون هو 1 أو 1 بت لتمثيل 1 بت.

ومع ذلك يمكنك تشغيل طول ترميز مع شيء من هذا القبيل 100 / 1 / 100 / 0 حيث هو عدد البتات إلى إخراج تليها قليلا.يبدو أن لدي تمثيل أصغر من البيانات.خاصة إذا قمت بزيادة 100 إلى عدد أكبر من ذلك بكثير.

أنا باستخدام: http://en.wikipedia.org/wiki/Information_entropy كمرجع في هذه اللحظة.حيث لم تذهب الخطأ ؟ هو احتمال تعيين الرموز ؟ أنا لا أعتقد أنه من الخطأ.أو هل وصلت العلاقة بين الضغط و الكون الخطأ ؟ أي شيء آخر ؟

شكرا

تحرير

التالية بعض الإجابات بلدي المتابعة هي:هل تطبيق الكون صيغة معينة مثيل رسالة إلى محاولة معرفة المعلومات المحتوى ؟ هل يصح أن تأخذ الرسالة "aaab" ويقول الكون هو ~0.811.إذا كان الجواب نعم ثم ما هو الكون من 1...10....0 حيث 1s و 0s تتكرر مرات n باستخدام الكون الصيغة.هو الجواب 1?

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

Answer 1

أو هل وصلت العلاقة بين الضغط و الكون الخطأ ؟

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

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

وعلى النقيض من ذلك ، كان لك محاكاة عدد كبير من عشوائية عملة تقلب ، فإنه سيكون من الصعب جدا للحد من حجم هذه الرسالة من قبل ذلك بكثير.كل بت سيكون المساهمة على مقربة من 1 بت من الكون.

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

ومع ذلك يمكنك تشغيل طول ترميز مع شيء من هذا القبيل 100 / 1 / 100 / 0 حيث هو عدد البتات إلى إخراج تليها قليلا.يبدو أن لدي تمثيل أصغر من البيانات.خاصة إذا قمت بزيادة 100 إلى عدد أكبر من ذلك بكثير.

لتلخيص, حقيقة أنك يمكن أن تضع خطة لجعل ترميز البيانات أصغر من البيانات الأصلية يقول لك شيء مهم.وهي تقول أن البيانات الأصلية الواردة القليل جدا من المعلومات.

---

مزيد من القراءة

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

Answer 2

وإلقاء نظرة على كولموجوروف تعقيد

<اقتباس فقرة>   

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

وفي حالة معينة، لا تقيد نفسك إلى الأبجدية {0،1}. على سبيل المثال استخدامك {0 ... 0، 1 ... 1} (مئات 0 ومئات من ل1)

Answer 3

والترميز لديك يعمل في هذا المثال، ولكن من الممكن أن نتصور حالة صالحة بالتساوي: 010101010101 ... التي من شأنها أن المشفرة ك 1/0/1/1 / ...

ويقاس الانتروبيا في جميع الرسائل المحتملة التي يمكن بناؤها في الأبجدية معين، وليس مجرد أمثلة المرضية!

Answer 4

جون Feminella حصلت على حق, ولكن أعتقد أن هناك أكثر من أن أقول.

شانون الكون على أساس احتمال و احتمال هو دائما في عين الناظر.

قلت أن 1 و 0 ومن المرجح أيضا (0.5).إذا كان هذا هو الحال ، ثم سلسلة من 100 1s تليها 100 0s لديه احتمال 0.5^200, الذي سجل(القاعدة 2) 200 بت, كما كنت تتوقع.ومع ذلك ، فإن الكون من هذه السلسلة (في شانون الشروط) هو محتوى المعلومات أضعاف احتمال أو 200 * 0.5^200, لا يزال حقا صغيرة العدد.

هذا مهم جدا لأنه إذا كنت لا تعمل طول الترميز إلى ضغط سلسلة, في هذه السلسلة سوف تحصل على طول صغير, ولكن في المتوسط على مدى كل 2^200 سلاسل, انها لن تفعل جيدا.مع الحظ ، في المتوسط إلى حوالي 200 ، ولكن ليس أقل.

من ناحية أخرى, إذا كنت تبحث في سلسلة الأصلي و يقولون انه ضرب حتى أن كل من ولدت ومن المرجح أن تولد المزيد من مثل ذلك, ثم كنت حقا أقول احتمال أكبر من 0.5^200 ، لذلك كنت تقوم افتراضات مختلفة عن الأصلي احتمال هيكل مولد السلسلة ، أي أنه أقل الكون من 200 بت.

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

آمل أن يساعد و شكرا على سؤالك.