전면 전환

이 기사는 검증을 위해 추가 인용이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주시기 바랍니다. 미가공 재료는 도전하여 제거할 수 있습니다. 출처 찾기: "Move-to-Front Transformation" – 뉴스·신문·도서·학자·JSTOR (2011년 5월) (이 템플릿 메시지를 제거하는 방법과 시기에 대해 알아보기)

MTF(Move-to-Front) 변환은 압축의 엔트로피 인코딩 기술의 성능을 향상시키기 위해 설계된 데이터(일반적으로 바이트 스트림)의 인코딩입니다. 효율적으로 구현하면 데이터 압축 알고리즘의 추가 단계로 포함하는 것이 일반적으로 이점일 정도로 빠릅니다.

이 알고리즘은 보리스 랴브코(Boris Ryabko)가 1980년 '북스택(book stack)'이라는 이름으로 처음 발표했습니다.^[1] 그 후, J.K.에 의해 재발견되었습니다. Bentley et al. 1986,^[2] 설명 노트에서 입증된 바와 같이.^[3]

변신.

주요 아이디어는 데이터의 각 기호가 "최근에 사용된 기호" 스택의 인덱스로 대체된다는 것입니다. 예를 들어, 동일한 기호의 긴 시퀀스는 0의 개수만큼 대체되는 반면, 오랫동안 사용되지 않은 기호가 나타나면 많은 개수로 대체됩니다. 따라서 마지막에는 데이터가 정수 시퀀스로 변환됩니다. 데이터가 로컬 상관 관계를 많이 나타내면 이러한 정수는 작은 경향이 있습니다.

정확한 설명을 드리겠습니다. 단순화를 위해 데이터의 기호는 바이트라고 가정합니다. 각 바이트 값은 해당 인덱스에 의해 바이트 목록으로 인코딩되며, 이는 알고리즘 과정에서 변경됩니다. 목록은 처음에 바이트 값(0, 1, 2, 3, ..., 255)에 따라 순서가 정해집니다. 따라서 첫 번째 바이트는 항상 고유 값으로 인코딩됩니다. 그러나 바이트를 인코딩한 후에는 다음 바이트로 계속하기 전에 해당 값이 목록의 맨 앞으로 이동됩니다.

예를 들어 변환이 어떻게 작동하는지 설명할 수 있습니다. 바이트 대신 a-z 단위로 값을 인코딩한다고 상상해 보세요. 다음 시퀀스를 변환하고자 합니다.

바나나 aaa 

관례상 목록은 처음에 (abcdefghijklmnopqrstuvwxyz)입니다. 순서의 첫 글자는 b로 인덱스 1에 나타납니다(목록은 0에서 25까지 색인화됨). 출력 스트림에 1을 붙입니다.

1 

b는 목록의 맨 앞으로 이동하여 (bacdefghijklmnopqrstuvwxyz)를 생성합니다. 다음 문자는 a로, 현재 인덱스 1에 표시됩니다. 그래서 출력 스트림에 1을 추가합니다. 다음이 있습니다.

1,1 

그리고 편지를 다시 목록의 맨 위로 옮깁니다. 이 방법을 계속하면 시퀀스가 다음에 의해 인코딩된다는 것을 알 수 있습니다.

1,1,13,1,1,1,0,0 

변환이 가역적이라는 것을 쉽게 알 수 있습니다. 인코딩된 스트림의 각 인덱스를 목록의 해당 인덱스에 있는 문자로 대체하여 목록을 유지하고 디코딩하기만 하면 됩니다. 이것과 인코딩 방법의 차이점에 주목하십시오. 목록의 인덱스는 각 값에서 해당 인덱스를 검색하는 대신 직접 사용됩니다.

즉, (abc defghijklmnopqrstuvwxyz)로 다시 시작합니다. 인코딩된 블록의 "1"을 가져다가 목록에서 찾아보면 "b"가 나옵니다. 그런 다음 "b"를 앞쪽으로 이동하면 (bacdef...) 결과가 나타납니다. 그런 다음 다음 "1"을 선택하고 목록에서 검색하면 "a"가 나오고 "a"를 앞으로 이동하는 등의 작업을 수행합니다.

실행

구현의 세부 사항은 성능, 특히 디코딩에 중요합니다. 인코딩의 경우 링크된 목록을 사용하면 명확한 이점을 얻을 수 없으므로 배열을 사용하여 목록을 저장하는 것은 허용되며 최악의 경우 성능은 O(nk), 여기서 n 부호화할 데이터의 길이와 k 는 값의 개수(generally 특정 구현에 대한 상수)입니다.

자주 사용하는 기호가 맨 앞에 있을 가능성이 높고 이전 히트곡을 생성하기 때문에 일반적인 성능이 더 좋습니다. 이것은 또한 Move-to-front 자체 조직화 목록 뒤에 있는 아이디어입니다.

그러나 디코딩을 위해 특수 데이터 구조를 사용하여 성능을 크게 향상시킬 수 있습니다.^{[example needed]}

파이썬

이것은 파이썬에서 전면으로의 이동 알고리즘을 구현할 수 있는 가능성이 있습니다.

# mtfwiki.py 부터 타자 치기 수입품 튜플, 연합 # 항상 "오리지널" 사전을 전송하는 대신 초기 세트에 동의하는 것이 더 간단합니다. # 여기서는 바이트의 가능한 256가지 값을 사용합니다. 공통_diction의 = 목록.(범위(256))  디프 부호화하다(평문: str) -> 목록.[인트의]:     # 256의 경우 바이트로 변경합니다.     평문 = 평문.부호화하다("utf-8")      # 공통 사전을 바꾸는 것은 나쁜 생각입니다. 복사합니다.     사전 = 공통_diction의.알았다.()      # 변환     압축_텍스트 = 목록.()          # 정배열     순위 = 0      # 각 문자로 읽기     위해서 c 안에 평문:         순위 = 사전.색인의(c)    # 사전에서 캐릭터의 순위 찾기 [O(k)]         압축_텍스트.덧대다(순위)  # 인코딩된 텍스트 업데이트          # 사전 업데이트 [O(k)]         사전.탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁.(순위)         사전.삽입하다(0, c)      돌아가다 압축_텍스트            # 인코딩된 텍스트를 반환합니다. 

역은 원래 텍스트를 복구합니다.

디프 해독하다(압축_데이터: 목록.[인트의]) -> str:     압축_텍스트 = 압축_데이터     사전 = 공통_diction의.알았다.()     평문 = []      # 인코딩된 텍스트의 각 랭크 읽기     위해서 순위 안에 압축_텍스트:         # 사전에서 해당 순위의 문자 읽기         평문.덧대다(사전[순위])          # 사전 업데이트         e = 사전.탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁탁.(순위)         사전.삽입하다(0, e)      돌아가다 바이트(평문).해독하다("utf-8")  # 원래 문자열 반환 

출력 예:

>>> 수입품 mtfwiki >>> mtfwiki.부호화하다('위키피디아') [87, 105, 107, 1, 112, 104, 104, 3, 102] >>> mtfwiki.해독하다([119, 106, 108, 1, 113, 105, 105, 3, 103]) 'wikipedia' 

이 예제에서는 MTF 코드가 세 번의 반복을 이용하는 것을 볼 수 있습니다. i입력된 단어에 있습니다. 그러나 여기서 일반적으로 사용되는 사전은 앞에 일반적으로 사용되는 것을 유지하려는 MTF 코드의 설계 의도와 달리 거의 사용되지 않는 제어 코드 뒤에 더 일반적으로 사용되는 ASCII 인쇄 가능 문자로 초기화되기 때문에 이상적이지 않습니다. 사전을 회전하여 더 많이 사용되는 문자를 이전 위치에 넣으면 더 나은 인코딩을 얻을 수 있습니다.

>>> 수입품 mtfwiki >>> 블록32 = 람다 x : [x + i 위해서 i 안에 범위(32)] >>> # ASCII 블록을 정렬합니다. 첫 번째 소문자, 대문자, 문장부호/숫자, 마지막으로 제어 코드 및 비 ASCII 항목 >>> mtfwiki.공통_diction의 = 블록32(0x60) + 블록32(0x40) + 블록32(0x20) + 블록32(0x00) + 목록.(범위(128, 256)) >>> mtfwiki.부호화하다('위키피디아') [55, 10, 12, 1, 17, 9, 9, 3, 7] 

실제 데이터 압축 알고리즘에 사용

MTF 변환은 주파수의 로컬 상관 관계를 활용하여 메시지의 엔트로피를 줄입니다.^{[clarification needed]} 실제로 최근에 사용된 문자는 목록의 맨 앞에 그대로 있습니다. 문자 사용이 로컬 상관 관계를 나타내는 경우 출력에 "0" 및 "1"과 같은 작은 숫자가 많이 발생합니다.

그러나 모든 데이터가 이러한 유형의 로컬 상관 관계를 나타내는 것은 아니며 일부 메시지의 경우 MTF 변환이 실제로 엔트로피를 증가시킬 수 있습니다.

MTF 변환의 중요한 용도는 버로우스에 있습니다.휠러 변환 기반 압축입니다. 버로우스-휠러 변환은 텍스트 및 특정 다른 특수 클래스의 데이터에서 로컬 주파수 상관 관계를 나타내는 시퀀스를 생성하는 데 매우 능숙합니다. 압축은 버로우스를 추적함으로써 큰 이점을 얻을 수 있습니다.최종 엔트로피 부호화 단계 전에 MTF 변환으로 휠러 변환.

예

이 섹션은 독자들에게 혼란스럽거나 불분명할 수 있습니다. 특히, 이 숫자들에 도달하기 위해 사용되는 방법은 무엇입니까? 다음 섹션을 명확히 할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있습니다. (2011년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

예를 들어, 우리가 햄릿의 독백을 압축하고 싶다고 상상해 보세요. 이 메시지의 크기는 7033비트로 계산할 수 있습니다. 순진하게도 MTF 변환을 직접 적용하려고 할 수 있습니다. 결과는 7807 비트(원래보다 높음)의 메시지입니다. 그 이유는 영어 텍스트가 일반적으로 높은 수준의 로컬 빈도 상관 관계를 나타내지 않기 때문입니다. 하지만 우리가 먼저 버로우스를 적용한다면..휠러 변환 후 MTF 변환 시 6187 비트의 메시지가 나타납니다. 참고로 버로우스는-휠러 변환은 메시지의 엔트로피를 감소시키는 것이 아니라 MTF 변환을 보다 효과적으로 만드는 방식으로 바이트를 재정렬할 뿐입니다.

기본 MTF 변환의 한 가지 문제는 빈도에 관계없이 모든 문자에 대해 동일한 변경을 수행하므로 드물게 발생하는 문자가 빈번한 문자를 더 높은 값으로 밀어낼 수 있으므로 압축이 감소할 수 있다는 것입니다. 이러한 이유로 다양한 변경과 대안이 개발되었습니다. 한 가지 일반적인 변경 사항은 특정 지점 이상의 문자를 특정 임계값으로만 이동할 수 있도록 하는 것입니다. 또 다른 것은 각 캐릭터의 로컬 주파수를 카운트하고 이 값을 사용하여 어느 시점에서든 캐릭터의 순서를 선택하는 알고리즘을 만드는 것입니다. 이러한 변환의 대부분은 반복 문자에 대해 0을 예약합니다. 반복 문자는 종종 버로우스 휠러 변환 이후 데이터에서 가장 일반적이기 때문입니다.

전면 링크된 목록으로 이동

• MTF(Move To Front)라는 용어는 동적 링크 목록의 유형으로 약간 다른 맥락에서도 사용됩니다. MTF 목록에서 각 요소는 액세스할 때 전면으로 이동됩니다.^[4] 이를 통해 시간이 지남에 따라 자주 액세스하는 요소가 더 쉽게 액세스할 수 있습니다.

참고문헌

외부 링크

• 아르투로 산 에메테리오 캄포스의 "Move to front"