[Перевод] Сжимаем флаги стран в 11 бит
Недавно я посмотрел интересное видео YouTube‑канала «Physics for the Birds». Это видео посвящено матрицам, но для объяснения некоторых операций с матрицами автор использовал флаги:
Он показал, как можно разбить флаги по осям, чтобы представить их в виде матриц и сэкономить место на диске. В конце этот пример был применён к реальным матрицам и вычислениям с ними.
Однако это видео дало мне вдохновение: часто флаги бывают очень простыми — несколько разноцветных полос, распространённые элементы наподобие звезды, полумесяца или креста. Если использовать какую‑нибудь схему кодирования, то удастся ли описать флаг Франции
в формате «три полосы: синяя, белая, красная», чтобы декодеру и рендереру достаточно было всего нескольких бит? Как может выглядеть такое кодирование?
Я решил создать нечто подобное.
Требования
Для начала я сформулировал критерии соответствия моей кодировки:
Декодированный флаг должен быть «достаточно узнаваемым»
Детали не обязаны быть точными. Вполне допустимы небольшие отклонения и неточности; достаточно, чтобы человек посмотрел на результат и сказал: «О, да это же тот флаг!»
В том числе это относится к и точному расположению и форме объектов.
Это относится и к точности цвета. Я знаю, как сильно гордится Франция своим новым оттенком синего, но при кодировании мы можем свести любой оттенок синего к какому‑нибудь среднему синему
Только флаги стран
Никаких флагов штатов, городов и других вексиллологических дизайнов
Без Непала
Прости, Непал, мне нравится твой непрямоугольный флаг, но он бы всё усложнил
Простые флаги должны занимать очень мало бит, а сложным дозволяется занимать больше, так что никакой фиксированной длины
Без гербов
На флагах наподобие флага Андорры содержатся их гербы, для рендеринга которых потребовались бы растровые/векторные изображения. Из‑за этого пришлось бы встроить в наш крошечный формат SVG или что‑то подобное, так что нет
Что делает флаг флагом?
Для начала мне нужно было разобраться, из каких элементов состоит флаг. В этом мне очень помог список флагов всех стран Worldometers.
Во‑первых, выяснилось, что флаги разнообразнее, чем я думал. Да, есть простые полосатые флаги, например, у Франции, Италии или Германии. Также есть дизайны наподобие флагов Бурунди или Боснии со звёздами, отдельными частями и тому подобным. На флагах Северной Македонии и Сейшельских Островов есть радиальные полосы. У Чехии, Багамских Островов и других стран на флагах есть треугольники слева. И таких различий ещё много.
Так что же общего у большинства флагов? Насколько я понял:
Полосы
Полосы, много полос: горизонтальные, вертикальные, две полосы, три полосы, тринадцать полос, полосы разной ширины, полосы под углом
Стандартные фигуры
Звёзды, полумесяцы, круги
Разных размеров и в разных местах, одна фигура или несколько
Треугольник слева
На удивление распространён и представлен в разных цветах, но часто имеет одинаковую общую форму, см. Коморы, Багамские Острова и Чехия
Цветной левый верхний угол
Какой‑нибудь прямоугольник в левой верхней части: США, Греция
Флаг Великобритании
Великобритания, Австралия, Новая Зеландия, Тувалу
И ещё есть страны Северной Европы
Их добавление явно станет большим плюсом: Норвегия, Швеция, Дания, Финляндия
Анализируем флаг
Я решил, что протокол должен определять следующие параметры:
Соотношение сторон
У всех флагов соотношение сторон индивидуально, но присутствуют явные паттерны: примерно 45% флагов имеет соотношение 2:3, примерно 28% — 1:2, примерно 9% — 3:5, а дальше идёт длинный хвост иных форматов
Цветовая палитра
Как уже говорилось, вместо копирования точного кода цвета мы ограничимся общими тонами, то есть цветовыми группами наподобие синего, зелёного и жёлтого
Тут тоже наблюдается похожая картина: неожиданно много красного, потом по убыванию идут белый, синий, жёлтый/золотой, зелёный, чёрный и оранжевый с длинным хвостом других цветов
Слои
Я думаю, логично задавать содержимое при помощи нескольких «слоёв» вместо того, чтобы пытаться закодировать все распространённые элементы по отдельности. Каждый слой сможет определять собственный список поддерживаемых опций
Это должно работать как в Photoshop и других приложениях: например, во флаге США у нас сначала будет слой с полосами, затем слой для синего прямоугольника и на нём слой звёзд
Самым общим слоем будет слой «Полосы». Он может иметь опции количества полос и их цветов, направления, чётного или нечётного распределения и повторяющихся паттернов
Слой «Фигуры» должен содержать звёзды, полумесяцы и тому подобное, определяя позицию и поворот. Слои «Интервал» и «Область» позволят закрашивать конкретный прямоугольник
Превращаем данные в биты
Как и во многих других случаях, различные параметры флагов, похоже, следуют закону Ципфа — соотношение сторон, цвета, элементы (полосы, звёзды и так далее). Чтобы распространённые элементы кодировались короче, я решил кодировать всё в отдельные деревья Хаффмана, присваивая распространённым случаям короткие двоичные коды.
Чтобы обеспечить возможность существования длинного хвоста без создания большого дерева, я решил отсекать значения, существующие только в одном флаге, и вместо них присваивать последнему листу дерева значение «Custom», за которым следует опция свободного значения с постоянной длиной. Например, это позволило сохранить соотношение сторон флага Сальвадора 189:335 без необходимости его записи в само дерево.
Вот пример полного дерева Хаффмана для соотношения сторон флага:
graph TD
%% Внутренние узлы
root((Root))
n1(( ))
n11(( ))
n110(( ))
n1101(( ))
n11011(( ))
n111(( ))
n1110(( ))
n11100(( ))
n111001(( ))
n11101(( ))
n111010(( ))
n111011(( ))
n1111(( ))
n11110(( ))
n111100(( ))
n111101(( ))
n11111(( ))
n111110(( ))
n1111100(( ))
n1111101(( ))
n111111(( ))
n1111110(( ))
n1111111(( ))
n11111111(( ))
%% Узлы листьев (соотношения)
L_2_3[2:3]
L_1_2[1:2]
L_3_5[3:5]
L_5_8[5:8]
L_10_19[10:19]
L_3_4[3:4]
L_4_7[4:7]
L_1_1[1:1]
L_7_10[7:10]
L_8_11[8:11]
L_11_18[11:18]
L_11_20[11:20]
L_11_28[11:28]
L_18_25[18:25]
L_1_phi[1:φ]
L_4_5[4:5]
L_6_7[6:7]
L_10_17[10:17]
L_13_15[13:15]
L_15_22[15:22]
L_16_25[16:25]
L_189_335[189:335]
L_28_37[28:37]
L_5_7[5:7]
L_7_11[7:11]
L_CUSTOM[CUSTOM]
%% Левая ветвь (0...)
root -- 0 --> L_2_3
root -- 1 --> n1
n1 -- 0 --> L_1_2
n1 -- 1 --> n11
%% Ветвь 110...
n11 -- 0 --> n110
n110 -- 0 --> L_3_5
n110 -- 1 --> n1101
n1101 -- 0 --> L_5_8
n1101 -- 1 --> n11011
n11011 -- 0 --> L_10_19
n11011 -- 1 --> L_3_4
%% Ветвь 111...
n11 -- 1 --> n111
n111 -- 0 --> n1110
%% Подветви 1110...
n1110 -- 0 --> n11100
n11100 -- 0 --> L_4_7
n11100 -- 1 --> n111001
n111001 -- 0 --> L_1_1
n111001 -- 1 --> L_7_10
n1110 -- 1 --> n11101
n11101 -- 0 --> n111010
n111010 -- 0 --> L_8_11
n111010 -- 1 --> L_11_18
n111011 -- 0 --> L_11_20
n111011 -- 1 --> L_11_28
n11101 -- 1 --> n111011
%% Ветвь 1111...
n111 -- 1 --> n1111
n1111 -- 0 --> n11110
%% Подветви 11110...
n11110 -- 0 --> n111100
n111100 -- 0 --> L_18_25
n111100 -- 1 --> L_1_phi
n1111001(( ))
n11110 -- 1 --> n111101
n111101 -- 0 --> L_4_5
n111101 -- 1 --> L_6_7
%% Ветвь 11111...
n1111 -- 1 --> n11111
n11111 -- 0 --> n111110
%% Подветви 111110...
n111110 -- 0 --> n1111100
n1111100 -- 0 --> L_10_17
n1111100 -- 1 --> L_13_15
n111110 -- 1 --> n1111101
n1111101 -- 0 --> L_15_22
n1111101 -- 1 --> L_16_25
%% Самая глубокая ветвь 111111...
n11111 -- 1 --> n111111
n111111 -- 0 --> n1111110
n1111110 -- 0 --> L_189_335
n1111110 -- 1 --> L_28_37
n111111 -- 1 --> n1111111
n1111111 -- 0 --> L_5_7
n1111111 -- 1 --> n11111111
n11111111 -- 0 --> L_7_11
n11111111 -- 1 --> L_CUSTOM
%% Стилизация для удобства чтения
classDef leaf fill:#e1f5fe,stroke:#0288d1,stroke-width:2px;
classDef internal fill:#eceff1,stroke:#607d8b,stroke-width:1px;
class L_2_3,L_1_2,L_3_5,L_5_8,L_10_19,L_3_4,L_4_7,L_1_1,L_7_10,L_8_11,L_11_18,L_11_20,L_11_28,L_18_25,L_1_phi,L_4_5,L_6_7,L_10_17,L_13_15,L_15_22,L_16_25,L_189_335,L_28_37,L_5_7,L_7_11,L_CUSTOM leaf;
class root,n1,n11,n110,n1101,n11011,n111,n1110,n11100,n111001,n11101,n111010,n111011,n1111,n11110,n111100,n111101,n11111,n111110,n1111100,n1111101,n111111,n1111110,n1111111,n11111111 internal;
То есть для 45% флагов с соотношением сторон 2:3 достаточно присвоить первому биту значение 0.
Формат содержит деревья Хаффмана для:
Соотношения сторон (самые распространённые: 2:3, 1:2, 3:5)
Особое соотношение ширина : высота для длинного хвоста
Размер цветовой палитры (самые распространённые: 3, 2, 4, 5)
Особое значение «Count — 7» для длинного хвоста, потому что дерево уходит вверх на 7 уровней
Цвет (самые распространённые: красный, белый, синий)
Особые цвета можно задавать в виде компактной 10-битной RGB‑аппроксимации (RRR GGGG BBB)
Количество слоёв
Тип слоя (полосы, фигура, области, пересечение, интервал, внутренний)
Ещё несколько специализированных поддеревьев
например, количество точек на звезде, расположение фигуры
Практически весь формат представляет собой обход одного дерева Хаффмана за другим, которые определяют, из чего состоит флаг.
Определившись со всем этим, можно попробовать закодировать в формат наш первый флаг. Для этого я выбрал флаг Индонезии, потому что это явный победитель в кодировании, или «самый среднестатистический флаг».
Соотношение сторон 2:3 (1 бит) →
0самое распространённое соотношение сторон
Палитра из двух цветов (2 бита) →
10Это единственный параметр, в котором мы немного теряем, потому что самое распространённое в дереве количество цветов — три
Определяем 2 цвета: красный (2 бита) →
00и белый (2 бита) →01Два самых распространённых цвета в дереве
1 слой (1 бит) →
0вершина дерева
Слой полос (1 бит) →
0, режим «равенство палитры» (то есть каждому цвету в палитре даётся одна одинаковая полоса, 1 бит) →0и горизонтальные полосы (1 бит) →0Всё это находится на вершинах соответствующих деревьев Хаффмана
→ Соединяем всё вместе:
0 10 00 01 0 0 0 0, илиQgA=в кодировке base64
При использовании этого формата усреднённый флаг можно представить в 76 битах, а медиана составляет 55 бит.
Самый длинный — это флаг Катара, 420 бит: #gHR1Y$?-+]m.0xS3F!0{.UH{uDppW5u2^+s|6~(p@GwHH<N:?57K99\(s)~!G4`!. Я бы сказал, что этот флаг едва умещается в нашу кодировку: сбоку у него есть зигзагообразный край, который я закодировал в виде 11 отдельных слоёв прямоугольников.
Флаг Великобритании
Можно сказать, что с ним я сжульничал. «Юнион Джек» сильно распространён, но его так сложно собирать из слоёв, что я просто сделал его встроенной в протокол фигурой. То есть он не собирается из частей, а для флага мы указываем «Слой „Юнион Джек“ в левом верхнем углу».
Кодируем флаги
Поначалу я использовал base64, чтобы просто превращать биты в сохраняемый текст. При 6 битах полезной нагрузки на один байт ASCII на усреднённое определение флага требуется 14 с медианой 12 символов. Самый короткий код флага — это QgA= (Индонезия).
Однако для повышения эффективности кодирования я решил воспользоваться кодировкой Base94, которая задействует все видимые однобайтовые символы ASCII с «!» по «~».
Думал я и о кодировании на основе эмодзи, но поскольку для сохранения каждого символа всё равно понадобится больше 1 байта, уменьшившееся количество символов, вероятно, всё равно потребует суммарно больше бит. (А ещё я не хотел рисковать тем, что флаг страны окажется закодированным в «💩🤮👎» или нечто подобное…)
В результате мы уменьшили усреднённое значение до 12 символов на флаг с медианой 9 символов. Индонезия осталась самым коротким кодом: <F.
Рендеринг
При помощи ChatGPT Codex я превратил этот формат в двухэтапную систему: кодировщик/декодер и SVG‑рендерер.
Декодер сначала превращает двоичный блоб в читаемый формат. Для уже рассмотренного нами флага Индонезии это выглядит так:
{
"aspectRatio": {
"kind": "rational",
"height": "2",
"width": "3"
},
"palette": [
{
"r": 210,
"g": 16,
"b": 52
},
{
"r": 255,
"g": 255,
"b": 255
}
],
"layers": [
{
"kind": "stripes",
"direction": "horizontal",
"stripes": [
{
"color": 0
},
{
"color": 1
}
]
}
]
}Затем рендерер превращает этот декодированный флаг в код SVG:
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1.5 1">
<rect x="0" y="0" width="1.5" height="0.5" fill="#d21034"/>
<rect x="0" y="0.5" width="1.5" height="0.5" fill="#fff"/>
</svg>Код довольно красив, в нём есть отдельный класс и интерфейсы для закодированных двоичных частей и слоёв. Однако даже при tsc‑компиляции кодировщик/декодер занимает 27 КБ, а рендерер — 12,5 КБ; наверно, это перебор, учитывая такую сильную оптимизацию исходного формата…
Поэтому я снова обратился к Codex и создал альтернативный «мини‑декодер»: вместо двух отдельных движков он объединяет декодирование и рендеринг в один проход, избавившись от красивой инфраструктуры из интерфейсов и класса и сведя всё к маленьким примитивным функциям.
Благодаря этому мы получили 470-строчный файл TypeScript, после компиляции превратившийся в 5,29 КБ (2,66 КБ после сжатия gzip).
Флаги, не поместившиеся в формат
С разной степенью успешности мне удалось закодировать в этот довольно примитивный формат 128 флагов.
Но осталось 67 флагов, которые мне закодировать не удалось. Наиболее примечательные из них:
Испании, Экваториальной Гвинеи, Андорры, Белиза, Брунея, Камбоджи, Коста‑Рики, Хорватии, Доминиканской Республики, Эквадора, Сальвадора, Фиджи, Гаити, Мексики, Молодовы, Черногории, Никарагуа, Омана, Парагвая, Португалии, Сан‑Марино, Сербии, Словакии, Словении, Венесуэлы
Содержащие герб, символ или национальную эмблему (25)
Анголы, Барбадоса, Эсватини, Гватемалы, Кении, Лесото, Лихтенштейна, Мальты, Мозамбика, Таджикистана, Ватикана
С глифами‑объектами: оружием, инструментами, коронами, щитами или головным убором (11)
Албании, Бутана, Доминики, Египта, Кирибати, Папуа — Новой Гвинеи, Шри‑Ланки, Уганды, Замбии, Зимбабве
С глифами‑животными, в основном орлами и другими птицами (10)
Канады, Кипра, Эритреи, Гренады, Ливана
С растительными глифами: листьями, ветвями или мускатным орехом (5)
Антигуа и Барбуды, Бразилии, Непала, ЮАР, Вануату
С геометрией, которую не может выразить модель слоёв, например, Y‑образной, V‑образной, завитком или непрямоугольным контуром (5)
Афганистана, Ирана, Ирака, Саудовской Аравии
С текстом или каллиграфией на арабском (4)
Здесь бы могло помочь добавление специального слоя текста
Индии, Кыргызстана, Монголии, Республики Корея
С религиозными или культурными символами: колесом Ашоки, юрты‑тюндюка, соёмбо или тхэгыкки (4)
Беларуси, Казахстана, Туркменистана
С орнаментальными узорами по краю
→ То есть практически все, содержащие особый глиф или текст, которые нелегко представить в виде геометрических слоёв
Случайные флаги!
Теперь, когда у нас есть структурированный язык описания флагов, я решил добавить рандомизатор, заполняющий новый флаг случайными элементами из имеющихся у нас деревьев Хаффмана.
Да, у какой‑нибудь страны вполне мог бы быть подобный флаг!
Подведём итог
Я уверен, что кто‑то ещё сможет найти более экономные или совершенно иные способы сжатия или структурирования данных. Однако мне всё равно было очень интересно взять полный список флагов, искать в них общие элементы и находить способы упаковки в биты максимального объёма данных. Здорово было и наконец‑то воспользоваться своими знаниями кода Хаффмана, полученными в рамках бакалавриата, а также писать код на битовом уровне.
Готовую страницу со всеми флагами можно найти здесь: https://vantezzen.github.io/miniflags/, а исходный код — здесь: https://github.com/vantezzen/miniflags. Не ожидайте увидеть там особо чистый код — в конце концов, по большей мере я его вайбкодил, исходя из своих мыслей о формате.
Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.