Nestlačitelný řetězec - Incompressible string

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Nekomprimovatelný řetězec"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Července 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

An nestlačitelný tětiva je řetězec s Kolmogorovova složitost rovná jeho délce, takže nemá kratší kódování.^[1]

Příklad

Předpokládejme, že máme řetězec 12349999123499991234 a používáme a komprese metoda, která funguje tak, že do řetězce vložíte speciální znak (řekněme „@“) následovaný hodnotou, která ukazuje na záznam v a vyhledávací tabulka (nebo slovník) 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

Náš ř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

externí odkazy