Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
А в реализации намеренно пропущены символы "0IOl" (ноль, ай, оу, эль) в массиве alphabet, или это алгоритм такой? Из статьи не удалось понять.
По сравнению с Base64 в Base58 в том числе отсутствуют символы, которые могут быть неоднозначно восприняты человеком
Как раз это я и пропустил. Благодарю за подсказку.
А для чего такие алфавиты нужны? Архивы передавать голосом по телефону?
Алфавит используется для биткоин-адресов, чтобы можно было без ошибок перепечатать с картинки
Помимо bitcoin-адресов это может быть произвольная строка-идентификатор, будь то аккаунт в соц-сети, ИНН, номер паспорта, идентификатор брони в отеле, авиабилета и т.п. Иногда передаются и голосом по телефону, да. Как base58 он получается короче, а потому удобнее, чем набор десятичных цифр.
Кроме того, такие идентификаторы удобно передавать баркодом (например, печатать на посадочном талоне).
Кроме того, такие идентификаторы удобно передавать баркодом (например, печатать на посадочном талоне).
Буквально только что на Computerfile был рассказ про isbn и контрольную сумму в нём. Там используется модульная арифметрика по основанию 11. Они обещают способность обнаружить любые перестановки и искажение любой одной цифры.
www.youtube.com/watch?v=bqtE6Q79PPs
www.youtube.com/watch?v=bqtE6Q79PPs
Почти все алгоритмы для forward error correction работают над конечными числовыми полями, и очень большой класс из них решают 2 задачи: обнаружение ошибки, исправление ошибки. Скорее всего схема, используемая в isbn — частный случай уже существующего кодирования.
ISBN он же EAN-13 он же GS1-13 использует алгоритм модуло10, он же алгоритм Луна, только умножение происходит не на два, а на три. Хотя ранее (года примерно до 2007) был иной алгоритм, с модулем 11 и возможным контрольным символом X. Собственно, переход к EAN-13 и состоял в добавлении префикса 978 и перерасчете контрольной цифры.
При использовании арифметики по модулю 11 нужно как-то записывать остаток 10. Обычно его записывают как 0, и в результате получается защита от большинства (больше 90%) ошибок, но не от всех.
В Википедии тоже обещают, что код ОКПО, основанный на том же принципе (умножение цифр на их номер в строке, и как контрольную цифру берём остаток от деления на 11 суммы), даёт 100% защиту и от искажения одиночной цифры, и от любой перестановки соседних цифр, но на самом деле это не так, там возможны коллизии, и даже одиночная ошибка может быть пропущена.
В ОКПО сделан такой финт:
Если получается остаток, равный 10, то для обеспечения одноразрядного контрольного числа необходимо провести повторный расчет, применяя вторую последовательность весов, сдвинутую на два разряда влево (3, 4, 5,…). Если в случае повторного расчета остаток от деления вновь сохраняется равным 10, то значение контрольного числа проставляется равным «0».
Но он не уменьшает количество определяемых ошибок. Например, для числа 2256261 получается контрольная цифра 2 — такая же, как и для чисел 5256261, 2956261, 2266261, 2254261, 2256761, 2256211 и 2256263, которые отличаются от него всего одной цифрой.
В Википедии тоже обещают, что код ОКПО, основанный на том же принципе (умножение цифр на их номер в строке, и как контрольную цифру берём остаток от деления на 11 суммы), даёт 100% защиту и от искажения одиночной цифры, и от любой перестановки соседних цифр, но на самом деле это не так, там возможны коллизии, и даже одиночная ошибка может быть пропущена.
В ОКПО сделан такой финт:
Если получается остаток, равный 10, то для обеспечения одноразрядного контрольного числа необходимо провести повторный расчет, применяя вторую последовательность весов, сдвинутую на два разряда влево (3, 4, 5,…). Если в случае повторного расчета остаток от деления вновь сохраняется равным 10, то значение контрольного числа проставляется равным «0».
Но он не уменьшает количество определяемых ошибок. Например, для числа 2256261 получается контрольная цифра 2 — такая же, как и для чисел 5256261, 2956261, 2266261, 2254261, 2256761, 2256211 и 2256263, которые отличаются от него всего одной цифрой.
А где же тесты?
Такая группа не является коммутативной: если правильный многоугольник с перенумерованными вершинами сначала симметрично отобразить, а потом повернуть, то в большинстве случаев получится не то же самое, что если сначала повернуть, а потом отобразить.
А нарисовать 4 картинки — не, зато КДПВ — нате!
Я не ставил целью объяснять, что такое диэдральные группы и вообще группы. Цель поста — показать полученное мной решение для задачи, которая, похоже, до сих пор была нерешённой. Остальное — лишь необходимое введение в контекст. О том, что такое системы счисления и какие они бывают, где применяется base58, что такое группа и т.д. я не писал, иначе это было бы слишком долго, да и незачем — об этом есть другие статьи.
Про диэдральные группы можно подробнее почитать хоть в Википедии, там с картинками.
Лично мне нравится, когда помимо сухого материала что-то говорится об авторе, когда он «оживляется», и из названия теоремы превращается в живого человека, поэтому и показал работу Верхуффа как скульптора. Если вам это не по душе — извините.
Про диэдральные группы можно подробнее почитать хоть в Википедии, там с картинками.
Лично мне нравится, когда помимо сухого материала что-то говорится об авторе, когда он «оживляется», и из названия теоремы превращается в живого человека, поэтому и показал работу Верхуффа как скульптора. Если вам это не по душе — извините.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Верхуффа для произвольной чётной системы счисления