전향 변환

전향 변환(Move-to-front transform, MTF 변환)은 데이터 압축 기술인 엔트로피 부호화의 성능을 향상시키기 위해 설계된 데이터(일반적으로 바이트 스트림)의 인코딩이다. 효율적으로 구현될 경우, 데이터 압축 알고리즘에 추가 단계로 포함될 만큼 충분히 빠르다.

이 알고리즘은 1980년 보리스 랴브코가 "책 스택(book stack)"이라는 이름으로 처음 발표했다. 이후 1986년 J.K. 벤틀리 등이 재발견했으며, 이는 설명 노트에 명시되어 있다.

변환

주요 아이디어는 데이터의 각 심볼이 "최근 사용된 심볼" 스택에서의 해당 인덱스로 대체된다는 것이다. 예를 들어, 동일한 심볼의 긴 시퀀스는 동일한 수의 0으로 대체되는 반면, 오랫동안 사용되지 않은 심볼이 나타나면 큰 숫자로 대체된다. 따라서 최종적으로 데이터는 일련의 정수로 변환된다. 데이터가 많은 지역 상관관계를 나타내면 이 정수들은 작은 경향이 있다.

정확한 설명을 제공해 보겠다. 간단화를 위해 데이터의 심볼이 바이트라고 가정한다.
각 바이트 값은 알고리즘 실행 중에 변경되는 바이트 목록에서 해당 인덱스로 인코딩된다. 목록은 초기에는 바이트 값 순서(0, 1, 2, 3, ..., 255)로 정렬되어 있다. 따라서 첫 번째 바이트는 항상 해당 값으로 인코딩된다. 그러나 바이트를 인코딩한 후에는 다음 바이트로 진행하기 전에 해당 값을 목록의 맨 앞으로 이동시킨다.

예시를 통해 변환이 어떻게 작동하는지 명확히 할 수 있다. 바이트 대신 a-z 범위의 값을 인코딩한다고 상상해 보자. 다음 시퀀스를 변환하려고 한다.
 bananaaa
관례에 따라 목록은 초기에는 (abcdefghijklmnopqrstuvwxyz)이다. 시퀀스의 첫 글자는 b이며, 인덱스 1에 나타난다 (목록은 0부터 25까지 인덱싱된다). 출력 스트림에 1을 넣는다:
 1
b는 목록의 맨 앞으로 이동하여 (bacdefghijklmnopqrstuvwxyz)를 생성한다. 다음 글자는 a이며, 이제 인덱스 1에 나타난다. 그래서 출력 스트림에 1을 추가한다. 이제:
 1,1
그리고 글자 a를 다시 목록의 맨 위로 이동시킨다. 이런 식으로 계속하면 시퀀스는 다음으로 인코딩된다:
 1,1,13,1,1,1,0,0

 반복 시퀀스 목록 bananaaa 1 (abcdefghijklmnopqrstuvwxyz) bananaaa 1,1 (bacdefghijklmnopqrstuvwxyz) bananaaa 1,1,13 (abcdefghijklmnopqrstuvwxyz) bananaaa 1,1,13,1 (nabcdefghijklmopqrstuvwxyz) bananaaa 1,1,13,1,1 (anbcdefghijklmopqrstuvwxyz) bananaaa 1,1,13,1,1,1 (nabcdefghijklmopqrstuvwxyz) bananaaa 1,1,13,1,1,1,0 (anbcdefghijklmopqrstuvwxyz) bananaaa 1,1,13,1,1,1,0,0 (anbcdefghijklmopqrstuvwxyz) 최종 1,1,13,1,1,1,0,0 (anbcdefghijklmopqrstuvwxyz)

변환이 가역적임을 쉽게 알 수 있다. 동일한 목록을 유지하고 인코딩된 스트림의 각 인덱스를 목록의 해당 인덱스에 있는 문자로 대체하여 디코딩하면 된다. 이 방법과 인코딩 방법의 차이점에 주목하자: 각 값을 인덱스로 찾는 대신 목록의 인덱스가 직접 사용된다.

즉, 다시 (abcdefghijklmnopqrstuvwxyz)로 시작한다. 인코딩된 블록의 "1"을 가져와 목록에서 찾으면 "b"가 나온다. 그런 다음 "b"를 맨 앞으로 이동시키면 (bacdef...)가 된다. 다음 "1"을 가져와 목록에서 찾으면 "a"가 나오고, "a"를 맨 앞으로 이동시키는 식으로 계속한다.

구현

특히 디코딩을 위한 성능을 위해서는 구현 세부 사항이 중요하다. 인코딩의 경우 연결 리스트를 사용함으로써 명확한 이점이 없으므로 배열을 사용하여 목록을 저장하는 것이 허용되며, 최악의 경우 성능은 O(nk)이다. 여기서 n은 인코딩할 데이터의 길이이고 k는 값의 개수이다 (주어진 구현에 대해 일반적으로 상수).

자주 사용되는 심볼이 목록의 앞에 있을 가능성이 높고 더 일찍 일치할 가능성이 높기 때문에 일반적인 성능이 더 좋다. 이것은 전향 이동 자가 구성 목록의 아이디어와도 일치한다.

그러나 디코딩의 경우 특수화된 데이터 구조를 사용하여 성능을 크게 향상시킬 수 있다.

파이썬
다음은 파이썬으로 구현한 전향 변환 알고리즘의 예시이다.

from collections.abc import Generator, Iterable

class MoveToFront:
    """
    >>> mtf = MoveToFront()
    >>> list(mtf.encode("Wikipedia"))
    [87, 105, 107, 1, 112, 104, 104, 3, 102]
    >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])
    'Wikipedia'
    >>> list(mtf.encode("wikipedia"))
    [119, 106, 108, 1, 113, 105, 105, 3, 103]
    >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])
    'wikipedia'
    """
    def __init__(self, common_dictionary: Iterable[int] = range(256)):
        """
        Instead of always transmitting an "original" dictionary,
        it is simpler to just agree on an initial set.
        Here we use the 256 possible values of a byte.
        """
        # consume the iterable so it can be used multiple times
        self.common_dictionary = list(common_dictionary)

    def encode(self, plain_text: str) -> Generator[int]:
        # Changing the common dictionary is a bad idea. Make a copy.
        dictionary = list(self.common_dictionary)

        # Read in each character
        for c in plain_text.encode("latin-1"):  # Change to bytes for 256.
            # Find the rank of the character in the dictionary [O(k)]
            rank = dictionary.index(c)  # the encoded character
            yield rank

            # Update the dictionary [Θ(k) for insert]
            dictionary.pop(rank)
            dictionary.insert(0, c)

    def decode(self, compressed_data: Iterable[int]) -> str:
        """
        Inverse function that recover the original text
        """
        dictionary = list(self.common_dictionary)
        plain_text = []

        # Read in each rank in the encoded text
        for rank in compressed_data:
            # Remove the character of that rank from the dictionary
            e = dictionary.pop(rank)
            plain_text.append(e)

            # Insert the character at the beginning of dictionary
            dictionary.insert(0, e)

        return bytes(plain_text).decode("latin-1")  # Return original string

이 예시에서 MTF 코드가 입력 단어의 세 번 반복되는 를 활용하는 것을 볼 수 있다. 그러나 여기서 공통 사전은 이상적이지 않다. 왜냐하면 MTF 코드의 설계 의도인 자주 사용되는 것을 앞에 두는 것과는 달리 거의 사용되지 않는 제어 코드 뒤에 더 일반적으로 사용되는 ASCII 인쇄 가능 문자로 초기화되었기 때문이다. 만약 사전을 회전시켜 더 자주 사용되는 문자를 더 앞쪽에 배치하면 더 나은 인코딩을 얻을 수 있다.

from itertools import chain

def block32(x):
    return range(x, x+32)

class MoveToFrontMoreCommon(MoveToFront):
    """
    >>> mtf = MoveToFrontMoreCommon()
    >>> list(mtf.encode("Wikipedia"))
    [55, 10, 12, 1, 17, 9, 9, 3, 7]
    """
    def __init__(self):
        super().__init__(
            chain(  # Sort the ASCII blocks:
                block32(ord("a") - 1),  # first lowercase,
                block32(ord("A") - 1),  # then uppercase,
                block32(ord("!") - 1),  # punctuation/number,
                block32(0),  # control codes,
                range(128, 256),  # and finally the non-ASCII stuff
            )
        )

if __name__ == "__main__":
    import doctest
    doctest.testmod()

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

MTF 변환은 메시지의 엔트로피를 줄이기 위해 주파수의 지역 상관 관계를 활용한다. 실제로, 최근 사용된 글자들은 목록의 앞쪽에 머무르는 경향이 있다. 만약 글자의 사용이 지역 상관 관계를 보인다면, 이는 출력에서 "0"과 "1"과 같은 많은 작은 숫자를 생성할 것이다.

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

MTF 변환의 중요한 용도는 버로우즈-휠러 변환 기반 압축이다. 버로우즈-휠러 변환은 플레인 텍스트 및 특정 다른 특별한 유형의 데이터에서 지역 주파수 상관 관계를 나타내는 시퀀스를 생성하는 데 매우 뛰어나다. 최종 엔트로피 인코딩 단계 전에 버로우즈-휠러 변환 다음에 MTF 변환을 적용하면 압축 효과가 크게 향상된다.

예시

예를 들어, 햄릿의 독백 (사느냐 죽느냐 그것이 문제로다...)을 압축한다고 가정해 보자. 이 메시지의 크기는 7033비트이다. 순진하게 MTF 변환을 직접 적용하려고 시도할 수 있다. 그 결과는 7807비트의 메시지이다 (원본보다 높다). 그 이유는 영어 텍스트가 일반적으로 높은 수준의 지역 주파수 상관 관계를 나타내지 않기 때문이다. 그러나 먼저 버로우즈-휠러 변환을 적용한 다음 MTF 변환을 적용하면 6187비트의 메시지를 얻는다. 버로우즈-휠러 변환은 메시지의 엔트로피를 감소시키지 않는다. 단지 MTF 변환을 더 효과적으로 만들기 위해 바이트를 재정렬할 뿐이다.

기본 MTF 변환의 한 가지 문제는 빈도에 관계없이 모든 문자에 동일한 변경을 가한다는 것이다. 이는 드물게 발생하는 문자가 빈번한 문자를 더 높은 값으로 밀어내어 압축률을 저하시킬 수 있다. 이러한 이유로 다양한 변경 및 대안이 개발되었다. 한 가지 일반적인 변경은 특정 지점 이상의 문자는 특정 임계값까지만 이동할 수 있도록 하는 것이다. 또 다른 방법은 각 문자의 지역 빈도를 계산하고 이러한 값을 사용하여 어떤 지점에서 문자의 순서를 선택하는 알고리즘을 만드는 것이다. 이러한 변환의 대부분은 버로우즈-휠러 변환 후 데이터에서 가장 흔한 경우가 많으므로 반복 문자에 대해 여전히 0을 예약한다.

전향 이동 연결 리스트

 전향 이동(Move To Front, MTF)이라는 용어는 동적 연결 리스트의 한 유형으로서 약간 다른 맥락에서도 사용된다. MTF 리스트에서는 각 요소가 접근될 때마다 맨 앞으로 이동한다. 이는 시간이 지남에 따라 더 자주 접근되는 요소에 더 쉽게 접근할 수 있도록 보장한다.

 각주 

 외부 링크 
 아르투로 산 에메테리오 캄포스의 "전향 이동"

분류:데이터 압축
분류:무손실 압축 알고리즘