국기를 11비트로 압축하기 — 허프만 코딩으로 만든 초소형 국기 포맷

본문

YouTube 채널 'Physics for the Birds'의 영상에서 국기를 축별로 분해해 행렬로 표현하는 장면을 본 저자는, 국기가 대부분 색 줄무늬와 별·초승달·십자 같은 단순한 요소로 이뤄져 있다는 점에 착안해 '프랑스 국기를 "줄무늬 3개, 파랑·하양·빨강"으로 정의하면 몇 비트면 충분하지 않을까'라는 문제를 풀기 시작했습니다. 목표는 정확한 재현이 아니라 '보는 사람이 그 국기라고 알아볼 수 있는 수준'이며, 국가 국기만 다루고 비직사각형인 네팔 국기와 문장(coat of arms)이 포함된 국기는 제외했습니다. 단순한 국기는 적은 비트를, 복잡한 국기는 더 많은 비트를 쓰는 가변 길이 포맷을 지향했습니다.

국기의 공통 요소 분석

Worldometers의 국기 목록을 분석한 결과 국기의 구성 요소는 크게 네 가지로 정리됐습니다. 가로·세로·불균등·대각선까지 다양한 줄무늬, 별·초승달·원 같은 공통 도형, 왼쪽 가장자리의 삼각형(체코·바하마 등), 왼쪽 위를 차지하는 사각 영역(미국·그리스)과 Union Jack, 그리고 북유럽 국가들의 십자가입니다. 가로세로 비율은 약 45%가 2:3, 28%가 1:2, 9%가 3:5로 뚜렷한 편중을 보였고, 색상도 빨강·하양·파랑·노랑·초록·검정·주황 순으로 Zipf 법칙을 따르는 분포를 보였습니다. 저자는 이를 Photoshop처럼 '레이어' 개념으로 모델링해, 미국 국기라면 줄무늬 레이어 → 파란 사각형 레이어 → 별 레이어 순으로 쌓는 방식을 채택했습니다.

허프만 트리로 비트화

빈도가 높은 값에 짧은 코드를 주기 위해 가로세로 비율, 팔레트 크기, 색상, 레이어 수, 레이어 타입(Stripes·Shape·Region·Cross·Band·Builtin), 별의 꼭짓점 수, 도형 배치 등 거의 모든 항목을 각각의 허프만 트리로 부호화했습니다. 한 국가에만 존재하는 값은 트리에서 잘라내고 마지막 잎을 'Custom'으로 둔 뒤 고정 길이 값을 붙여, 엘살바도르의 189:335 같은 희귀 비율도 표현할 수 있게 했습니다. 예컨대 45%의 국기가 쓰는 2:3 비율은 첫 비트 0 하나로 끝납니다. 인도네시아 국기는 2:3 비율(1비트) + 팔레트 2색(2비트) + 빨강·하양(각 2비트) + 레이어 1개(1비트) + 줄무늬 레이어의 최상위 옵션들로 '0 10 00 01 0 0 0 0'이라는 최단 코드가 됩니다. 전체 결과는 평균 76비트, 중앙값 55비트였고, 지그재그 경계를 사각형 레이어 11개로 표현한 카타르가 420비트로 최장이었습니다. Union Jack은 레이어로 조합하기 너무 복잡해 프로토콜에 내장 도형으로 넣는 '반칙'을 썼다고 저자는 인정합니다.

문자열 인코딩과 렌더링

비트열을 텍스트로 저장하기 위해 처음에는 Base64를 썼으나(평균 14자, 중앙값 12자), 보이는 ASCII 문자 전체('!'~'~')를 쓰는 Base94로 바꿔 평균 12자, 중앙값 9자까지 줄였고 인도네시아는 '<F'가 됐습니다. 이모지 인코딩은 문자당 1바이트를 넘어 총 비트가 오히려 늘고, 국기가 부적절한 이모지 조합으로 표현될 위험이 있어 포기했습니다. 구현은 ChatGPT Codex의 도움으로 디코더와 SVG 렌더러의 2단계 구조로 만들었으나, tsc 컴파일 기준 인코더/디코더 27kB, 렌더러 12.5kB로 포맷 최적화에 비해 코드가 너무 컸습니다. 그래서 디코딩과 렌더링을 한 번에 처리하고 클래스·인터페이스를 걷어낸 'minidecoder'를 다시 만들어 470줄 TypeScript, 컴파일 후 5.29kB(gzip 2.66kB)까지 줄였습니다.

표현하지 못한 국기들과 후속 실험

128개국을 인코딩하는 데 성공했지만 67개국은 실패했습니다. 문장·국장 포함(25개국, 스페인·포르투갈·멕시코 등), 무기·왕관 같은 사물 글리프(11), 독수리 등 동물 글리프(10), 식물 글리프(5, 캐나다·레바논 등), 레이어 모델로 표현 불가능한 기하 구조(5, 브라질·남아공 등), 아랍 문자(4), 그리고 아쇼카 차크라·소욤보·태극 같은 종교·문화 기호(4, 인도·몽골·한국 등)가 원인이었습니다. 한국 국기의 태극 문양이 기하 레이어로 표현 불가능한 대표 사례로 분류된 점이 한국 독자에게는 흥미로운 대목입니다. 저자는 이 구조화된 '국기 언어'를 활용해 허프만 트리에서 무작위로 항목을 뽑는 랜덤 국기 생성기도 만들었고, 결과물과 소스 코드를 vantezzen.github.io/miniflags에 공개했습니다.

Hacker News 반응

• @Smalltalker-80 — 아무도 안 하길래 제가 합니다: "Fun with flags!"(빅뱅이론 밈)
• @kjgkjhfkjf — 조회 테이블을 쓰면 어떨까요. 인정되는 국가·지역이 256개 미만이니 8비트 키면 충분하고, 문장이나 국기가 거의 같은 국가 같은 복잡한 사례도 처리할 수 있어 이 11비트 인코딩보다 낫습니다.
• @opiotrek — 하지만 그러면 SVG를 디코더에 내장해야 하는데, 그게 5KB보다 작을까요? 그건 사실상 SVG 스프라이트와 다를 바 없습니다.
• @MadnessASAP — SVG 디코더까지 포함하라고 하는 건 불공평합니다. 브라우저가 기본 제공하니까요. 다만 SVG 파일 자체는 포함해야 하는데, Wikimedia의 캐나다 국기가 699바이트, 프랑스가 262바이트라서 압축해도 총 5KB는 넘을 겁니다.
• @jtxt — 멋진 프로젝트와 결과입니다: vantezzen.github.io/miniflags

원문: read.vantezzen.io / 번역·요약: Trawling