Алгоритмы контрольной цифры устроены так похоже, что их удобно рассматривать как одно семейство с настраиваемыми параметрами. Ниже разберём, из чего состоит общий каркас, чем на самом деле отличаются три основные ветви, почему одна и та же идея по-разному реагирует на перестановку соседних знаков и какие четыре вопроса стоит задать себе до того, как выбирать правило.
Из чего состоит любой алгоритм этого семейства?
Скелет у всех один, и он укладывается в три шага: пронумеровать позиции номера, умножить каждый знак на вес, зависящий от позиции, сложить произведения и взять остаток от деления суммы на выбранный модуль. Из остатка тем или иным способом получают один знак — либо берут его как есть, либо вычитают из модуля, получая дополнение.
Различия между конкретными алгоритмами живут ровно в трёх местах. Первое — таблица весов: она может повторяться через одну позицию, расти слева направо, убывать или быть периодической с более длинным периодом. Второе — модуль: десять, одиннадцать, девяносто семь и другие значения. Третье — отображение остатка в знак: что делать, если остаток больше девяти и одной цифрой его не записать.
Именно третий пункт чаще всего и создаёт различия, заметные пользователю. Пока модуль равен десяти, остаток всегда укладывается в одну цифру и вопросов не возникает. Как только модуль растёт, однозначных остатков на всех не хватает, и системе приходится или расширять алфавит, допуская букву, или сдвигать диапазон, или вовсе отказываться от части значений.
Три основные ветви: mod-10, mod-11 и mod-97
Три ветви различаются не сложностью, а применимостью, и это удобнее всего показать таблицей.
| Ветвь | Типичная область применения | Что даёт рост модуля | Главная сложность |
|---|---|---|---|
| mod-10 | короткие и средние номера, много открытых систем | остаток всегда одна цифра | веса задают, какие ошибки ловятся |
| mod-11 | системы, где нужна повышенная чувствительность | появляется проблема многозначного остатка | нужен способ записать остаток, равный десяти |
| mod-97 | длинные строки из цифр и букв | очень низкая вероятность случайного совпадения | требует перестановки и замены букв на числа |
Ветвь mod-10 самая распространённая, и причина проста: она работает с чистыми цифрами и никогда не требует букв. Вариант с удвоением и последующим вычитанием девяти из получившихся двузначных чисел — один из представителей этой ветви, и он же чаще всего встречается в платёжной отрасли и за её пределами.
Ветвь mod-11 поднимает чувствительность: одиннадцать возможных остатков различают больше ситуаций, чем десять. Платой становится необходимость договориться, что делать с остатком, который в одну цифру не помещается. Одни системы просто отказываются от таких номеров при выпуске, другие допускают в последней позиции букву, обычно икс, означающую конкретное числовое значение.
Ветвь mod-97 применяют там, где номер длинный, а иногда ещё и содержит буквы. Перед вычислением строку переставляют по определённому правилу и заменяют буквы числами по фиксированной схеме, после чего вся длинная последовательность цифр сворачивается в остаток. Именно так устроена проверка международного номера счёта, о которой подробнее сказано в статье про структуру IBAN.
Веса и модуль: что именно крутим внутри семейства
Когда каркас общий, настройка сводится к двум ручкам, и у каждой есть цена.
Первая ручка — периодичность весов. Простейший вариант чередует два значения: одно на чётных позициях, другое на нечётных. Более сложные берут период из трёх, четырёх или большего числа элементов. Чем длиннее период, тем труднее подобрать вручную два разных набора знаков, дающих одинаковую сумму, но тем сложнее и проверка — её уже неудобно выполнять в уме.
Вторая ручка — модуль. Рост модуля уменьшает вероятность того, что случайная опечатка случайно же сохранит остаток. Но за рост приходится платить: множество допустимых остатков перестаёт совпадать с алфавитом, которым записывается номер, и появляются либо запрещённые значения, либо расширение алфавита буквой.
Есть и третья, менее очевидная настройка: направление обхода. Часть систем считает веса от начала строки, часть — от конца. Это важно не само по себе, а потому, что от направления зависит, какая именно позиция получит удвоение, а значит, и то, как правило отреагирует на конкретную ошибку. Сдвиг направления — самая частая ошибка при самостоятельной реализации.
Почему одни правила ловят перестановку, а другие нет?
Возьмём строку, в которой две соседние цифры поменялись местами. Сумма произведений на веса изменится только в том случае, если веса этих двух позиций различаются. Если веса одинаковы, обмен знаков ничего не меняет: каждое произведение просто переезжает на место другого, а сумма остаётся прежней.
Отсюда прямое следствие. Правило с симметричными весами, например чередующее одно и то же значение, перестановку соседних знаков внутри пары одинаковых позиций не заметит вообще. Правило с несимметричными весами, где соседние позиции имеют разные множители, такую перестановку ловит. Именно поэтому в схемах, рассчитанных на ручной ввод, веса почти всегда делают несимметричными.
Второе следствие тоньше. Даже несимметричное правило не является абсолютной защитой: при некоторых модулях и некоторых парах знаков перестановка может дать тот же остаток, потому что разность вкладов окажется кратной модулю. Утверждение «перестановки ловятся всегда» неверно ни для одного известного правила, и полагаться на него в проектировании не стоит. Полезно сравнить это с поведением конкретной распространённой схемы, разобранной в материале про проверку Луна — правила там другие, но природа ограничений та же.
Четыре вопроса, которые нужно задать до выбора правила
Выбор алгоритма — это не вопрос вкуса, а ответ на четыре вопроса о вашей задаче. Задайте их по порядку.
- Какой длины номера и насколько они предсказуемы? Если длина переменная и заранее неизвестна, правило должно работать без опоры на фиксированные позиции.
- Из чего состоит алфавит? Только цифры или ещё буквы? Появление букв сразу исключает часть правил, работающих исключительно с числами.
- Откуда берутся ошибки? Человек за клавиатурой чаще путает соседние знаки и переставляет их, машина при генерации — ошибается иначе. От этого зависит, какие веса предпочтительны.
- Что делать, если результат не помещается в одну цифру? Ответ на этот вопрос определяет, нужен ли вам расширенный алфавит и как вы будете объяснять его пользователю.
Если номера к вам приходят из внешней системы, пятый вопрос звучит иначе: не «какое правило выбрать», а «какое правило опубликовала эта система». Изобретать своё правило для чужих номеров бессмысленно — совпадения не будет ни у кого. Правило берут из документации системы, а свою реализацию проверяют на опубликованных ею примерах.
Как разработчику держать семейство в одной реализации
Когда алгоритмов несколько, соблазн велик — написать для каждого отдельную функцию. Через полгода таких функций окажется десяток, и половина будет отличаться одной строкой. Гораздо практичнее описать семейство как данные: таблица весов, модуль, направление обхода и правило отображения остатка. Тогда реализация одна, а конкретных алгоритмов — сколько угодно.
Второе — проверяйте реализацию на границах. Пустая строка, строка из одного знака, строка из одних нулей и строка с ведущими нулями ломают наивные решения чаще, чем любые экзотические данные. Ведущие нули особенно коварны: любое преобразование строки в число их уничтожает, а вместе с ними меняется и результат.
Третье — держите рядом с алгоритмом контрольный пример, взятый из публичного описания системы. Не для того, чтобы доказать правильность на одном случае, а чтобы заметить сдвиг, если кто-то однажды поменяет направление обхода. Числа в примере придуманы и служат только иллюстрацией: параметры семейства — это открытое знание, но ни один приведённый здесь набор значений не описывает реально выданный номер и не принадлежит никакой системе нумерации.
Что делать дальше
Определите, какое правило действует для номеров, с которыми работает ваша система, и выпишите его параметры в одном месте: веса, модуль, направление обхода, отображение остатка. Если правило неизвестно, честно зафиксируйте это в документации, а не подставляйте похожее: неверное правило хуже отсутствующего, потому что отвергает корректные данные.
Затем проверьте свою реализацию на инструменте проверки: он показывает, каким системам подошла строка и какой вывод дала каждая из них. А чтобы увидеть, как эти решения складываются в общий конвейер обработки, посмотрите материал про устройство проверки номера.