Недавно я посмотрел интересное видео 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. Не ожидайте увидеть там особо чистый код — в конце концов, по большей мере я его вайбкодил, исходя из своих мыслей о формате.
