Иерархические схемы кодировки

В иерархической схеме кодировки набор значений разделяется на несколько категорий, те, в свою очередь, — на несколько подкатегорий, и так далее, пока не будет достигнут некий нижний уровень. Такие схемы называют также вложенными или древовидными. У каждой категории есть определенное значение, а подкатегории его уточняют.
Наиболее очевидный пример — почтовый индекс, разделяющий территорию США на отдельные регионы. При чтении слева направо каждая следующая цифра уточняет расположение адресата: регион, штат, город и, наконец, почтовое отделение. Рассмотрим индекс 30310. Номера с 30000 до 39999 соответствуют юго-востоку США. Номера с 30000 по 30399 распределены по Джорджии, а индексы с 30300 по 30399 указывают на Атланту. Весь индекс, 30310, идентифицирует почтовое отделение на западной окраине города. Для расшифровки индекса его нужно читать по цифрам слева направо — сначала одну цифру, потом две, потом оставшиеся две.
Другой пример — библиотечная классификация DDC (Dewey Decimal Classification), применяемая в американских библиотеках. Номера в шестой сотне (начинающиеся с 5) покрывают “Естественные науки”, номера 510-519 соответствуют математике и, наконец, код 512 обозначает алгебру. Схему можно расширять далее, добавляя позиции после десятичной точки для обозначения подразделов алгебры.
Иерархические схемы кодировки хороши для работы с большими объемами данных, обладающих естественной иерархической структурой. Структурированную информацию легко организовать и представить, но при разработке подобных схем также возникают проблемы.
Во-первых, древовидная структура не обязана быть сбалансированной: для некоторых категорий необходимо больше кодов, чем для других. В системе DDC мало кодов для восточных и древних религий, что отражает предпочтение, отдававшееся христианским и иудаистским текстам. Между тем, в наши дни в Библиотеке Конгресса США явно лидирует буддизм — книг по нему больше, чем по любой другой религии Земли.
Во-вторых, размещение определенных категорий на дереве может со временем оказаться неудачным. Например, в системе DDC книги по логике представлены кодом 164 из раздела “Философия”, тогда как более уместен был бы код из математического раздела. В XIX веке математической логики просто не было, а сегодня мало кому придет в голову искать книги по логике в философском разделе. Создатель системы DDC просто закрепил в ней понятия своего времени — как поступают и многие современные программисты.

Векторные коды

Вектор состоит из фиксированного числа компонентов. Они могут быть упорядоченными и неупорядоченными, обладать постоянной или переменной длиной, быть взаимно зависимыми или независимыми, но они всегда присутствуют в заданном количестве, и код имеет смысл лишь при наличии всех компонентов.
Самый распространенный векторный код — дата, состоящая из числа, месяца и года. Компоненты даты, конечно, имеют некоторый смысл и сами по себе, но во всей полноте суть даты раскрывается лишь при наличии всех трех компонентов. Порядок их расположения особого значения не имеет: в мировой практике вы, вероятно, найдете все возможные сочетания. Допустимые значения для числа зависят от года (високосный или нет) и месяца (который может иметь 28, 29, 30 или 31 день). Компоненты могут разделяться точками (28.09.2005), косыми чертами (28/09/2005), пробелами (28 сентября 2005 г.) или вообще никак не разделяться (28092005).
Другой пример — код ISO размеров автомобильных покрышек, составляемый из диаметра колеса в дюймах, типа покрышки (буквенный код) и ее ширины в миллиметрах. Код 15R155 соответствует 15-дюймовой радиальной покрышке шириной 155 миллиметров, а код 15SR155 — покрышке тех же размеров, но с опоясывающим металлическим кордом. Несмотря на смесь американских и международных единиц это вполне общее физическое описание покрышки.
Векторные схемы информативны, кроме того, они позволяют подобрать для каждого компонента наилучший способ кодирования, но вместе с тем иногда приходится придумывать, как разделить код на составные части (во многих СУБД имеются функции для разделения на компоненты дат, адресов и имен). Сортировка по компонентам практически невозможна, разве что в том порядке, в каком они стоят в коде.
Еще один недостаток заключается в том, что неудачный выбор кода всего для одного компонента делает бесполезной всю схему. Расширение кода тоже проблематично. Что если в код покрышки нужно будет включить еще толщину в миллиметрах? Раз появляется еще одно число, его придется отделять пунктуацией. Вообще, такие переделки обычно чреваты необходимостью вносить правки в очень многие программы.

Составные коды

Составной код представляет собой комбинацию произвольного числа нескольких компонентов. Как и в векторной кодировке, компоненты могут быть упорядоченными и неупорядоченными, зависимыми и независимыми, разделяться пунктуацией, пробелами и пр. Часто в составном коде присутствует иерархическая структура, которая выстраивается с помощью уточняющих компонентов, которые добавляются к коду справа. Иногда в качестве составного кода используется список свойств, каждое из которых может присутствовать или отсутствовать. Порядок компонентов тоже не является обязательным.
Составные коды были популярны в мастерских начала XX в. К изделию прикреплялся бумажный ярлык, на котором каждый рабочий записью подтверждал завершение очередного этапа обработки. Составные коды и по сей день используются в авиационной промышленности: с помощью длинного кода описывается набор деталей, входящих в состав компонента (его называют корневым или родительским), который расположен в начале кода. Еще один вариант составного кода — неупорядоченный кворум-код. Чтобы некое условие считалось выполненным, в таком коде должно присутствовать n компонентов из k. Например, чтобы деталь считалась прошедшей контроль качества, ее должны одобрить любые три инспектора из пяти.
Самый популярный составной код — список ключевых слов, стоящий в начале какого-либо документа и описывающий его содержание. Ключевые слова назначаются документу автором или библиотекарем. Как правило, они выбираются из ограниченного специализированного словаря. В начале компьютерной эры популярность составных кодов снизилась, поскольку из-за переменной длины их трудно было хранить в первых компьютерных системах, в которых записи имели фиксированную длину (помните перфокарты?). Чтобы такие коды можно было корректно сортировать, их приходилось хранить в виде строк, выровненных влево.
Неудачно разработанный составной код может быть неоднозначным. Например, какой код стоит в начале цепочки “1234” — 1 или 12? В базах данных составные коды обычно преобразуются в набор флажков “да/нет”, расположенных в смежных столбцах файла, то есть, фактически из истинных составных кодов превращаются в булевы векторные коды.