압축할 수 없는 문자열

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "압축할 수 없는 문자열" – 뉴스 · 신문 · 책 · 학자 · JSTOR (1919년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

압축할 수 없는 끈은 콜모고로프의 복잡성이 길이와 같아 더 짧은 인코딩을 하지 않는 끈이다.^[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자이고, 대체되는 항목은 길이가 같기 때문이다.따라서, 이 문자열은 우리의 알고리즘으로는 압축할 수 없다.

참조