สตริงที่ไม่สามารถบีบอัดได้คือสตริงที่มีความซับซ้อนของ Kolmogorovเท่ากับความยาวของมัน ดังนั้นจึงไม่มีการเข้ารหัสที่สั้นกว่า^{[ 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 

สตริงนี้มีความยาวเท่ากับสตริงเดิม เนื่องจากตัวแทนสำหรับรายการในพจนานุกรมของเรามีความยาว 2 ตัวอักษร และรายการที่มันแทนที่ก็มีความยาวเท่ากัน ดังนั้น สตริงนี้จึงไม่สามารถบีบอัดได้ด้วยอัลกอริทึมของเรา