Контрольные числа и идентификационные коды


Одним из самых удивительных применений математики являются контрольные числа по которым можно определить ошибку. Они используются повсеместно, например в номере кредитной карточки последняя цифра контрольная. А ещё в штрих коде, ISBN код книги, IBAN код счёта, номер кошелька в Яндекс.Деньги, ИНН, ОКПО. Жалко что нет в телефонных номерах 😦
Т.е. они используются для цифровых идентификаторов которые могут быть переданы с ошибками.

Технически это такой подвид хешкодов который настроен на то что однозначно можно будет определить ошибку в одной или нескольких цифрах или перестановках. А у обычных хеш функций высоко ценится равномерное распределение. В частности, хеш алгоритм SHA1 вероятность 94.5% для любого вида искажения.
А вот алгоритм контрольного числа Верхуффа сможет однозначно с определить ошибку в одном числе (например 6 вместо 7), но с вероятностью 90% если число продублировалось (66). Т.е. если человек во время ввода номера карточки ошибся и дважды продублировал число, то мы на самом деле не уверены что произошло именно это, и смысл в такой проверке отпадает.

Если вы пишете для Java платформы, то для использование контрольных чисел становится проще некуда: вам поможет библиотека Apacha Commons Validator. Эта библиотека уже сейчас активно используется по многих проектах поскольку есть в транзитивных зависимостях Hibernate. Но только в последней версии 1.4 в ней появился целый пакет с реализацией контрольных сумм.
Сейчас хочу показать вам простой пример генерации и проверки ISIN кода.
Он использует продвинутую вариацию алгоритма Луна и в нём явно прописано как вести себя с латинскими буквами. Контрольное число из одной цифры. Вообщем сойдёт почти для любого кода.

String codePart = "1234"
String checkSum = ISINCheckDigit.ISIN_CHECK_DIGIT.calculate(codePart)
assert checkSum == "4"
String code = codePart + checkSum
assert code == "12344"
assert ISINCheckDigit.ISIN_CHECK_DIGIT.isValid(code)
assert !ISINCheckDigit.ISIN_CHECK_DIGIT.isValid("12349")

Внимательные читатели заметят что здесь идёт обращение к константе ISIN_CHECK_DIGIT. Это просто экземпляр класса для удобства, что-то вроде Singletone. Использовать его таким образом безопасно, потому что сам класс ISINCheckDigit не хранит внутреннего состояния.

Если у вас реально огромный идентификатор, то вы возможно захотите двух цифровое контрольное число. Например размер междунородно банковского кода IBAN может быть до 34х символов, два из которых — контрольное число вычисленное по алгоритму MOD 97-10. Но лучше конечно избегайте таких аномальных кодов.
Если вам нужны алгоритмы похитрее, то поищите в книге The Laws of Cryptography.

От себя бы хотел добавить несколько мыслей по поводу идентификаторов которые у меня возникли при их изучении.

Если возможно не изобретайте свой новый формат.

Присмотритесь к существующим кодам — среди них полно универсальных и интернациональных. И есть куча региональных: ABA, NSIN, SEDOL, ОКПО, ИНН, ОКАТО. Все они на самом деле почти одно и тоже, но блин каждый считал своим долгом их выдумать.

Печатный формат

Формат IBAN хорош тем, что в нём регламентировано что на бумаге его отображать разбитым по четыре числа с пробелами:
UA93 3996 2200 0414 9005 2335 6688 2
Это очень актуально, потому что IBAN может быть реально гигантским. Вообще о форматировании (маске) как-то не задумываются обычно.
А ведь числа лучше смотрятся когда они разбиты апострофом на тысячи, миллионы, миллиарды итд.
Но коды лучше разбивать не по три цифры, а по две или четыре. Так их становится в разы удобнее произносить.
Попробуйте сами произнести число 2012 — «twenty twelve» легче чем «two thousand twelve».
Номера телефонов мы обычно записываем группируя их двойками и разделяя минусом. Кстати минус вполне можно заменить обычным пробелом — визуального шума будет меньше.
IBAN в этом плане крут: решение бить квадрами по четыре цифры через пробел делает реально удобным надиктовку кода и быструю навигацию глазами по нему.

Я думаю, нет особого смысла фиксировать размер

Фиксированный размер имеет одно большое и явное преимущество — если не хватает цифры по размеру то это сразу бросается человеку в глаза. Мы все привыкли что в наших телефонных номерах тринадцать чисел и если одного не хватает то сразу переспрашиваем. Это отличный способ отлавливать один из видов наиболее массовых ошибок ещё до проверки контрольно суммы.
Отдельно можно выделить что проверка на чётность\нечётность количества цифр в коде тоже вполне может сойти. Например я знаю что код может быть длиной в 6, 8, 10, 12 цифр, и если мне надиктовали код нечётной длины, например 7, то я могу переспросить собеседника «ты где то потерял или продублировал цифру».

Но если его превысите то заимеете геморрой когда станет не хватать. Например ISBN который несколько раз расширяли.
Ещё один очень яркий пример — IP4 и IPv6: попытка расширить адрес закончилась абсолютно новым, обратно не совместимым протоколом.

Обычно необходимость в фиксированном размере возникает если у вас есть несколько частей (зон, доменов) в коде. Например штрих код EAN-13 можно разделить на 5 зон:

  • Префикс национальной организации GS1 (3 цифры)
  • Регистрационный номер производителя товара (4-6 цифр)
  • Код товара (3-5 цифр)
  • Контрольное число (1 цифра)
  • Дополнительное поле (необязательное штрихкодовое поле, иногда там ставится знак «>», «индикатор свободной зоны»).

Теперь вы обречены страдать если диапазона не хватает. Код товара в в пять цифр — это смешно по современным меркам. В супермаркете артикулов под миллион — каждый брелок разного цвета имеет свой отдельный артикул.

Иногда такая зона становится не нужной и тогда её помечают как неиспользуемая. Или для обратной совместимости она теперь всегда имеет одинаковое значение.
Прекрасный пример номер счёта Яндекс.Деньги: он начинается с номера валюты счёта. Раньше у Яндекса были не только рубли, но и региональные сегменты системы (украинский, армянский, американский и другие), которые обслуживались разными процессинговыми центрами. Но сейчас из-за закона есть только рубли, и у всех кошельков одинаковый префикс.

Ещё больший бред это резервировать зоны «на будущее». Короче, как ни крути, фиксированный формат невозможно предугадать и он вынуждает к нерациональному использованию доступных регистров.

А нужны ли зоны? Может, пускай код будет просто кодом? Всегда есть соблазн напихать кучу информации в код, но зачем? Для шардинга?
Я видел очень много примеров когда код состоял из нескольких зон и это делало его только хуже.

Если у вас есть острая необходимость в зонах то введите просто разделитель для них. Идеальный разделитель это точка ‘.’. Она есть сразу на Num Pade, так что пользователи скажут вам спасибо.
Обратите внимание что так и поступили с адресами интернет доменов. И ещё интернет домены хороши что они теперь иерархичные, поддерживают по сути неограниченный размер и глубину вложенности. Так что очень даже отличный пример.

Контрольное число всё таки лучше ставить в конце кода.

Во первых, это как-то соответствует естественному порядку. Во вторых упростите жизнь разработчикам библиотек. Например в коде IBAN контрольная сумма это третье и четвёртая цифра, и если посмотреть на реализацию IBANCheckDigit то там можно обнаружить костыль когда они вырезаются и вставляются в конец кода.

Нужно сто раз подумать над допустимыми символами в коде: цифры, латинские буквы, национальные буквы, чувствительность регистра.

Только десятичные цифры — идеально для людей. Их относительно легко запомнить, диктовать (без всяких там «эс как эс русская»), трудно ошибиться, легко набирать. Причём последнее свойство актуально и для набора на телефонной клавиатуре, и для набора на Num Pad и для информационный киосков и платёжных терминалов с сенсорным экраном.
Очень многие форматы, такие как уже упомянутые ISIN и IBAN начинаются с двухсимвольного кода страны (UA, GB), т.е. они уже alphanumeric.
И тут начинается жесть — теперь из-за двух букв придётся использовать полную клавиатуру (те кто с телефонов вас проклянут).
Следующая проблема: как преобразовывать буквы в цифры? Брать ASII код? В ISIN и IBAN решили поступить как с шестнадцатиричными числами: т.е. буква A = 10, B = 11 … Z = 35.
Т.е. по сути обратная Base32 кодировка.
А ещё, хоть и нет зависимости от регистра, но иногда при диктовке всё равно будут переспрашивать большая буква или маленькая.

В действительности смысл в алфанумерик есть тогда, когда у вас очень большие числа, например код кошелька BitCoin. Очень большие числа шифруют уже в 64хричной системе через Base64: регистрозависимый алфанумерик. Это сделает код в несколько раз короче, но надиктовывать его будет полный ад. Тут уже на помощь приходят QR коды.

Откуда вы вообще берёте размеры?

Если у вас чисто числовой код, и он не влезает в 64х разрядный long, то уже прийдётся использовать классы обвёртки BigDecimal или BigInteger. А это сразу жёсткий удар по производительности и расходу памяти.
Также во многих БД на строковые поля объявлены как VARCHAR(255) и не дай бог выйти за их предел. Но я не думаю что кто-то, в здравом уме будет делать такие длинные коды 🙂

Оставьте комментарий