Nestlačitelný řetězec - Incompressible string

Nestlačitelné řetězec je řetězec s Kolmogorov složitosti se rovná jeho délce, takže to nemá kratší kódování.

Příklad

Předpokládejme, že máme řetězec 12349999123499991234 a používáme kompresní metodu, která funguje tak, že do řetězce vložíte speciální znak (řekněme „@“) následovaný hodnotou, která ukazuje na záznam ve vyhledávací tabulce (nebo slovníku) opakujících se hodnot . Představme si, že máme algoritmus, který zkoumá řetězec ve 4 znakových blocích. Při pohledu na náš řetězec může náš algoritmus vybrat hodnoty 1234 a 9999, které se umístí do jeho slovníku. Řekněme, že 1234 je položka 0 a 9999 je položka 1. Nyní se řetězec může stát:

@ 0 @ 1 @ 0 @ 1 @ 0

Je zřejmé, že je to mnohem kratší, i když samotné ukládání slovníku bude stát nějaký prostor. Čím více opakování je v řetězci, tím lepší bude komprese.

Náš algoritmus však může být lepší, pokud dokáže zobrazit řetězec v blocích větších než 4 znaky. Pak může do slovníku vložit 12349999 a 1234, což nám dává:

@ 0 @ 0 @ 1

Ještě kratší. Nyní zvažte další řetězec:

1234999988884321

Tento řetězec je podle našeho algoritmu nestlačitelný. Jediné opakování, která se vyskytují, jsou 88 a 99. Pokud bychom měli uložit 88 a 99 do našeho slovníku, vytvořili bychom:

1234 @ 1 @ 1 @ 0 @ 04321

Bohužel je to stejně dlouhé jako původní řetězec, protože naše zástupné symboly pro položky ve slovníku mají délku 2 znaky a položky, které nahrazují, mají stejnou délku. Proto je tento řetězec naším algoritmem nestlačitelný.

Reference