خيط غير قابل للانضغاط

السلسلة غير القابلة للضغط هي سلسلة ذات تعقيد كولموغوروف يساوي طولها، بحيث لا يوجد لها ترميزات أقصر. ^{[ 1 ]} يمكن استخدام مبدأ خانة الحمام لإثبات أنه لأي خوارزمية ضغط بدون فقدان ، يجب أن توجد العديد من السلاسل غير القابلة للضغط.

لنفترض أن لدينا السلسلة النصية 12349999123499991234، ونستخدم طريقة ضغط تعمل عن طريق إضافة حرف خاص (مثلاً @) إلى السلسلة، متبوعًا بقيمة تشير إلى مدخل في جدول بحث (أو قاموس) للقيم المتكررة. لنفترض أن لدينا خوارزمية تفحص السلسلة في أجزاء من 4 أحرف. بالنظر إلى سلسلتنا، قد تختار خوارزميتنا القيمتين 1234 و9999 لوضعهما في قاموسها. لنفترض أن 1234 هو المدخل 0 و9999 هو المدخل 1. الآن يمكن أن تصبح السلسلة النصية:

@0@1@0@1@0

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

لكن يمكن لخوارزميتنا أن تعمل بشكل أفضل إذا تمكنت من عرض السلسلة في أجزاء أكبر من 4 أحرف. حينها يمكنها وضع 12349999 و1234 في القاموس، مما يعطينا:

0@0@1

هذه السلسلة أقصر. والآن، لننظر إلى سلسلة أخرى:

1234999988884321

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

1234@1@1@0@04321

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