Niekompresowalny ciąg - Incompressible string

Incompressible ciąg jest ciągiem z Kołmogorowa złożoność równa jej długości, tak, że nie ma krótsze kodowania.

Przykład

Załóżmy, że mamy ciąg 12349999123499991234 i używamy metody kompresji , która działa poprzez umieszczenie w ciągu znaków specjalnego znaku (powiedzmy „@”), po którym następuje wartość wskazująca wpis w tabeli przeglądowej (lub słowniku) z powtarzającymi się wartościami . Wyobraźmy sobie, że mamy algorytm, który bada ciąg 4-znakowy. Patrząc na nasz ciąg, nasz algorytm może wybrać wartości 1234 i 9999 i umieścić je w swoim słowniku. Powiedzmy, że 1234 to pozycja 0, a 9999 to pozycja 1. Teraz ciąg może stać się:

@ 0 @ 1 @ 0 @ 1 @ 0

Oczywiście jest to znacznie krótsze, chociaż przechowywanie samego słownika będzie kosztować trochę miejsca. Jednak im więcej powtórzeń w ciągu, tym lepsza kompresja.

Nasz algorytm może jednak działać lepiej, jeśli może wyświetlać ciąg w fragmentach większych niż 4 znaki. Następnie może wstawić 12349999 i 1234 do słownika, dając nam:

@ 0 @ 0 @ 1

Jeszcze krócej. Teraz rozważ inny ciąg:

1234999988884321

Ten ciąg jest nieściśliwy przez nasz algorytm. Jedyne powtórzenia to 88 i 99. Gdybyśmy mieli zapisać 88 i 99 w naszym słowniku, otrzymalibyśmy:

1234 @ 1 @ 1 @ 0 @ 04321

Niestety jest to tyle samo co oryginalny ciąg, ponieważ nasze symbole zastępcze dla elementów w słowniku mają 2 znaki, a elementy, które zastępują, mają tę samą długość. W związku z tym ten ciąg jest nieściśliwy przez nasz algorytm.

Bibliografia