맨위로가기

일라이어스 오메가 부호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

일라이어스 오메가 부호는 1 이상의 정수를 부호화하는 가변 길이 접두사 부호화 방식이다. 이 부호는 정수를 이진법으로 표현하고, 자릿수를 계산하여 재귀적으로 부호화하는 방식으로 작동한다. 부호화 과정은 정수를 이진법으로 표현한 값 앞에 해당 자릿수를 이진법으로 표현한 값을 차례로 붙이고, 마지막에 '0'을 추가하는 방식으로 진행된다. 복호화는 부호화 과정을 역순으로 수행하며, C++ 코드를 통해 구현될 수 있다. 엘리아스 오메가 부호는 점근적으로 최적의 부호이며, 일반화 및 다양한 응용 분야에서 활용될 수 있다.

더 읽어볼만한 페이지

  • 무손실 압축 알고리즘 - VP9
    VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다.
  • 무손실 압축 알고리즘 - FLAC
    FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
  • 기수법 - 이진법
    이진법은 0과 1 두 개의 숫자를 사용하는 밑이 2인 위치 기수법으로, 컴퓨터 과학의 기초가 되었으며 현대 컴퓨터에서 데이터를 저장하고 처리하는 데 사용된다.
  • 기수법 - 구진법
    구진법은 9를 밑으로 하는 위치 기수법으로 0부터 8까지의 숫자를 사용하여 수를 나타내며, 3의 배수 표현이 간결하고 3의 역수는 유한소수로 표현되는 특징이 있다.
일라이어스 오메가 부호
개요
이름일라이어스 오메가 부호
구분범용 부호화
유형정수 부호화
용도양의 정수를 표현하는 데 사용
발명가피터 엘리아스
특징
속성단순하고 효율적인 가변 길이 부호화 방식
장점작은 정수에 대해 짧은 부호 길이를 가짐
단점큰 정수를 표현하는 데 비효율적임
부호화 과정
1단계정수 N이 주어지면, N-1을 이진수로 표현
2단계이진수 표현 앞에 이진수 표현의 길이를 일라이어스 오메가 부호로 부호화
3단계2단계를 반복하며, 0으로 끝맺음
복호화 과정
1단계비트를 읽어 0이 나올 때까지 반복하며 부호화된 길이를 얻음
2단계얻어진 길이를 사용하여 이진수를 읽고, 원래 숫자를 계산
3단계1단계와 2단계를 반복

2. 부호화 원리

일라이어스 오메가 부호화는 1 이상의 정수 N에 대해 다음 단계를 재귀적으로 수행하여 이루어진다.

# 마지막에 '0'을 붙인다.

# 만약 부호화하려는 숫자가 1이라면 종료한다. 그렇지 않다면 숫자의 이진법 표현을 앞에 붙인다.

# 지금 출력한 숫자의 자릿수에서 1을 뺀 값을 새로운 부호화 대상 숫자로 하여 2번의 과정을 반복한다.

숫자가 18일 때의 예시는 다음과 같다.

# 먼저 마지막에 0이 적힌다.

# : 0

# 18을 이진법으로 표현한 10010을 그 앞에 덧붙인다(공백은 편의상 삽입).

# : 10010 0

# 10010의 자릿수가 5자리이므로, 5-1=4로 하여 재귀 처리를 한다. 4의 이진법 표현 100을 앞에 덧붙인다.

# : 100 10010 0

# 100의 자릿수가 3자리이므로, 3-1=2로 하여 재귀 처리를 한다. 2의 이진법 표현 10을 앞에 덧붙인다.

# : 10 100 10010 0

# 10의 자릿수가 2자리이므로, 2-1=1로 하여 재귀 처리를 한다. 1은 종료 조건이므로, 결과적으로 다음과 같다.

# : 10 100 10010 0

1부터 17까지의 부호어는 다음과 같다.

N부호어
10
210 0
311 0
410 100 0
510 101 0
610 110 0
710 111 0
811 1000 0
911 1001 0
1011 1010 0
1111 1011 0
1211 1100 0
1311 1101 0
1411 1110 0
1511 1111 0
1610 100 10000 0
1710 100 10001 0


2. 1. 부호화 과정

일라이어스 오메가 부호화는 1 이상의 정수 N에 대해 다음 단계를 재귀적으로 수행하여 이루어진다.

# 마지막에 '0'을 붙인다.

# 만약 부호화하려는 숫자가 1이라면 종료한다. 그렇지 않다면 숫자의 이진법 표현을 앞에 붙인다.

# 지금 출력한 숫자의 자릿수에서 1을 뺀 값을 새로운 부호화 대상 숫자로 하여 2번의 과정을 반복한다.

숫자가 18일 때의 예시는 다음과 같다.

# 먼저 마지막에 0이 적힌다.

# : 0

# 18을 이진법으로 표현한 10010을 그 앞에 덧붙인다(공백은 편의상 삽입).

# : 10010 0

# 10010의 자릿수가 5자리이므로, 5-1=4로 하여 재귀 처리를 한다. 4의 이진법 표현 100을 앞에 덧붙인다.

# : 100 10010 0

# 100의 자릿수가 3자리이므로, 3-1=2로 하여 재귀 처리를 한다. 2의 이진법 표현 10을 앞에 덧붙인다.

# : 10 100 10010 0

# 10의 자릿수가 2자리이므로, 2-1=1로 하여 재귀 처리를 한다. 1은 종료 조건이므로, 결과적으로 다음과 같다.

# : 10 100 10010 0

1부터 17까지의 부호어는 다음과 같다.

N부호어
10
210 0
311 0
410 100 0
510 101 0
610 110 0
710 111 0
811 1000 0
911 1001 0
1011 1010 0
1111 1011 0
1211 1100 0
1311 1101 0
1411 1110 0
1511 1111 0
1610 100 10000 0
1710 100 10001 0


2. 2. 복호화 과정

일라이어스 오메가 복호화는 부호화 과정을 역순으로 따라가며 진행된다. C++ 코드를 예시로 들면 다음과 같다.

```cpp

void eliasOmegaDecode(char* source, char* dest) {

BitReader bitreader(source);

IntWriter intwriter(dest);

while (bitreader.hasLeft())

{

int num = 1;

while (bitreader.inputBit()) // 잠재적으로 잘못된 형식의 파일에 위험함.

{

int len = num;

num = 1;

for (int i = 0; i < len; ++i)

{

num <<= 1;

if (bitreader.inputBit())

num |= 1;

}

}

intwriter.putInt(num); // 값을 쓴다.

}

bitreader.close();

intwriter.close();

}

```

복호화 과정은 먼저 변수 N을 1로 설정한다. 부호어의 처음을 읽어 0이면 정수 1을 나타내고, 1이면 다음에 오는 N자리수와 함께 바이너리 부호가 되므로 N을 그 값으로 설정한다. 이후 이 단계를 반복하여, 부호어의 나머지 처음을 읽어 0이면 부호화된 숫자가 N이 됨을 나타내고, 1이면 이어지는 N자리수와 함께 바이너리 부호가 되므로 N을 그 값으로 설정한다.

예를 들어 부호어 '101100'을 복호화하는 과정은 다음과 같다. 우선 N=1로 설정하고, 첫 번째 1 기호를 읽는다. 값이 1이므로, 이어지는 N=1 기호를 읽어 10을 바이너리 부호로 간주한 2를 새로운 N의 값으로 한다. 그러면 부호어의 나머지는 '1100'이 된다. 첫 번째 1 기호를 읽어온다. 값이 1이므로, 이어지는 N=2 기호를 읽어온 110을 바이너리 부호로 간주한 6을 새로운 N의 값으로 한다. 그러면 부호어의 나머지는 '0'이 된다. 첫 번째 1 기호를 읽어온다. 값이 0이므로, N=6이 구하고자 하는 정수값이다.

3. 예시

다음은 1부터 17까지의 정수에 대한 엘리아스 오메가 부호의 예시이다.

값부호암시된 확률
101/2
210 01/8
311 01/8
410 100 01/64
510 101 01/64
610 110 01/64
710 111 01/64
811 1000 01/128
911 1001 01/128
1011 1010 01/128
1111 1011 01/128
1211 1100 01/128
1311 1101 01/128
1411 1110 01/128
1511 1111 01/128
1610 100 10000 01/2048
1710 100 10001 01/2048
...
10010 110 1100100 01/8192
100011 1001 1111101000 01/131,072
10,00011 1101 10011100010000 01/2,097,152
100,00010 100 10000 11000011010100000 01/268,435,456
1,000,00010 100 10011 11110100001001000000 01/2,147,483,648



1 구골 (10100)에 대한 부호는 11 1000 101001100 (길이 헤더 15비트)이며, 그 뒤에 1구골의 333비트 이진 표현인 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 이며, 그 뒤에 꼬리 0이 붙어 총 349비트가 된다.

구골의 백제곱 (1010000)은 33,220비트 이진수이다. 오메가 부호는 33,243비트 길이이다. 11 1111 1000000111000100 (22비트) 다음에는 값의 33,220비트와 꼬리 0이 붙는다. 엘리아스 델타 부호에 따르면, 같은 숫자는 33,250비트 길이이다. 000000000000000 1000000111000100 (31비트) 다음에는 값의 33,219비트가 붙는다. 오메가 및 델타 부호는 각각 숫자의 일반적인 33,220비트 이진 표현보다 0.07% 및 0.09% 더 길다.

4. 코드 길이

양의 정수 ''N''의 인코딩에 필요한 비트 수 ''B''(''N'')는 다음과 같이 재귀적으로 정의된다.

:

\begin{align}B(0) & = 0\,, \\

B(N) & = 1 + \lfloor \log_2(N) \rfloor + B(\lfloor \log_2(N) \rfloor)\,.

\end{align}

즉, 정수 N에 대한 일라이어스 오메가 부호의 길이는 다음과 같다.

:1 + (1 + \lfloor \log_2 N \rfloor{}) + (1 + \lfloor \log_2 \lfloor \log_2 N \rfloor{} \rfloor{}) + \cdots

여기서 합의 항의 수는 이진 반복 로그에 의해 제한된다.

정확히 말하면, f(x) = \lfloor \log_2 x \rfloor{} 라고 하자. 우리는 N > f(N) > f(f(N)) > \cdots > f^k(N) = 1 을 만족하는 어떤 k 가 있으며, 부호의 길이는 (k+1) + f(N) + f^2(N) + \dots + f^k(N) 이다. f(x) \leq \log_2 x 이므로 k \leq \log_2^*(N) 이다.

반복 로그는 모든 고정된 n에 대해 \log_2^n N 보다 느리게 증가하므로, 점근적 성장률은 \Theta(\log_2 N + \log_2^2 N + \cdots) 이며, 여기서 합은 1 미만으로 떨어질 때 종료된다.

4. 1. 점근적 최적성

엘리아스 오메가 부호는 점근적으로 최적의 접두사 부호이다.[1]

'''증명 개요.''' 접두사 부호는 크래프트 부등식을 만족해야 한다. 일라이어스 오메가 부호의 경우, 크래프트 부등식은 다음과 같다.

:\sum_{n=1}^\infty \frac{1}{2^{O(1) + \log_2 n + \log_2\log_2 n + \cdots}} \leq 1

이제, 이 합은 점근적으로 적분과 동일하며, 이는 다음과 같다.

:\int_1^\infty \frac{dx}{x \times \ln x \times \ln \ln x \cdots} \leq O(1)

만약 분모가 어떤 지점 \ln^k x에서 종료된다면, 이 적분은 \ln^{k+1} \infty로 발산한다. 그러나 분모가 어떤 지점 (\ln^k x)^{1+\epsilon}에서 종료된다면, 이 적분은 \frac{1}{(\ln^{k} \infty)^\epsilon} 로 수렴한다. 일라이어스 오메가 부호는 발산과 수렴의 경계에 있다.

5. 일반화

엘리아스 오메가 부호는 0 또는 음의 정수를 직접 부호화할 수 없다. 이를 해결하기 위해, 부호화 전에 1을 더하고 해독 후에 1을 빼는 방법이나, 레벤슈타인 부호화를 사용하는 방법이 있다. 모든 정수를 부호화하기 위해, 부호화 전에 모든 정수 (0, 1, -1, 2, -2, 3, -3, ...)를 양의 정수 (1, 2, 3, 4, 5, 6, 7, ...)에 매핑하는 전단사를 설정하는 방법도 사용된다.

6. 응용

7. C++ 코드 예시

7. 1. 인코딩

cpp

void eliasOmegaEncode(char* source, char* dest)

{

IntReader intreader(source);

BitWriter bitwriter(dest);

while (intreader.hasLeft())

{

int num = intreader.getInt();

BitStack bits;

while (num > 1) {

int len = 0;

for (int temp = num; temp > 0; temp >>= 1) // calculate 1+floor(log2(num))

len++;

for (int i = 0; i < len; i++)

bits.pushBit((num >> i) & 1);

num = len - 1;

}

while (bits.length() > 0)

bitwriter.putBit(bits.popBit());

bitwriter.putBit(false); // write one zero

}

bitwriter.close();

intreader.close();

}

7. 2. 디코딩

cpp

BitReader bitreader(source);

IntWriter intwriter(dest);

while (bitreader.hasLeft())

{

int num = 1;

while (bitreader.inputBit()) // 잠재적으로 잘못된 형식의 파일에 위험함.

{

int len = num;

num = 1;

for (int i = 0; i < len; ++i)

{

num <<= 1;

if (bitreader.inputBit())

num |= 1;

}

}

intwriter.putInt(num); // 값을 쓴다.

}

bitreader.close();

intwriter.close();


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com