엘리아스-파노 인코딩 계산기

정렬돼 있다는 사실 자체를 정보로 활용합니다. 각 값을 상위비트와 하위비트로 쪼개, 하위 l비트는 고정폭으로 그대로 저장하고 상위비트는 유니터리(0을 이어 쓰다 1로 끊는 방식)로 저장합니다. l은 n·2^l ≥ U(n=원소 개수, U=값의 범위)를 만족하는 가장 작은 값으로 정합니다.

정렬된 수열에서는 상위비트가 감소하지 않습니다. i번째 원소가 담긴 위치에서 i를 빼면 바로 그 원소의 상위비트 값이 나오므로, 값을 통째로 쓰는 대신 "증가분"만 표시하면 됩니다. 값의 범위가 아무리 커도 원소 개수에 비례한 크기로 압축됩니다.

원소당 대략 log2(U/n) + 2비트만 씁니다. 값의 범위(U)가 원소 개수(n)보다 훨씬 크더라도, 원소 개수에 비례해 커질 뿐 범위 자체에 비례하지 않는다는 것이 이 기법의 핵심 장점입니다.

네. 엄격한 오름차순이 아니라 비내림차순(같은 값이 연달아 나와도 됨)이면 됩니다. 유니터리 인코딩에서 위치에 i를 더하는 부분이 중복값도 자연스럽게 처리합니다.

검색엔진의 역색인(inverted index)에서 문서 ID 목록을 압축하거나, succinct 자료구조에서 정렬된 정수 배열을 저장할 때 널리 쓰입니다. Apache Lucene 등 실제 검색엔진 구현체에 포함되어 있습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.