Короткая предыстория
Беседовал я некоторое время назад со знакомым роботом. Устроился он временно на Почту России сортировщиком писем. Работёнка не пыльная, смотрит индекс на письме и помещает их в нужное отверстие. Но есть проблема с письмами, у которых в индексе сделана опечатка. На выяснение правильного индекса уходит много времени и пиво успевает выдыхаться.
Заноза в голове
После того разговора прошло уже достаточно времени, но дилемма почтовых индексов не выходила у меня из головы.
Казалось бы — что еще тут можно улучшить? Попробуем преобразить вид цифр индекса таким образом, чтобы даже если одна ошибка попадётся, ее можно было автоматически выявить и исправить.
Оказывается улучшить можно.
Попробуем нарисовать новый вид цифры 0.
Если интересно, зачем и почему — прошу под кат.
Еще в университете, на лекции по дискретной математике, я обратил внимание, что расстояние Хемминга между некоторыми написанными цифрами слишком мало, то есть они отличаются всего «одной палочкой». Далеко за примером ходить не будем, это 0 и 8. Достаточно «переставить» одну палочку, и одна цифра превращается в другую.
Дальнейшее исследование
А есть ли еще проблемы с похожими цифрами? Ведь именно для данного случая, чем больше расстояние между цифрами — тем проще роботу исправить ошибку. Ограничимся одной ошибкой в цифре. К примеру:
Видно, что не хватает одной палочки, однако, алгоритмически можно определить, что это была за ошибка и исправить ее.
Обозначим каждую палку скелета цифры — цифрой (да, такой вот каламбур):
Назначим каждой цифре свой вектор:
postindex[0]=[1,1,1,1,1,1,0,0,0];
postindex[1]=[0,0,0,0,1,1,1,0,0];
postindex[2]=[1,0,0,1,0,1,0,0,1];
postindex[3]=[1,0,0,0,0,0,1,1,1];
postindex[4]=[0,1,0,0,1,1,0,1,0];
postindex[5]=[1,1,0,1,1,0,0,1,0];
postindex[6]=[0,0,1,1,1,0,1,1,0];
postindex[7]=[1,0,1,0,0,0,1,0,0];
postindex[8]=[1,1,1,1,1,1,0,1,0];
postindex[9]=[1,1,0,0,0,1,0,1,1];
Теперь рассчитаем расстояние Хемминга между цифрами:
0 1 2 3 4 5 6 7 8 9
'0': [ 0, 5, 4, 8, 4, 3, 5, 5, 1, 5 ]
'1': [ 5, 0, 5, 5, 3, 6, 4, 4, 6, 6 ]
'2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ]
'3': [ 8, 5, 4, 0, 6, 5, 5, 3, 7, 3 ]
'4': [ 4, 3, 6, 6, 0, 3, 5, 7, 3, 3 ]
'5': [ 3, 6, 5, 5, 3, 0, 4, 6, 2, 4 ]
'6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ]
'7': [ 5, 4, 5, 3, 7, 6, 4, 0, 6, 6 ]
'8': [ 1, 6, 5, 7, 3, 2, 4, 6, 0, 4 ]
'9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ]var postindex = {};
postindex[0]=[1,1,1,1,1,1,0,0,0];
postindex[1]=[0,0,0,0,1,1,1,0,0];
postindex[2]=[1,0,0,1,0,1,0,0,1];
postindex[3]=[1,0,0,0,0,0,1,1,1];
postindex[4]=[0,1,0,0,1,1,0,1,0];
postindex[5]=[1,1,0,1,1,0,0,1,0];
postindex[6]=[0,0,1,1,1,0,1,1,0];
postindex[7]=[1,0,1,0,0,0,1,0,0];
postindex[8]=[1,1,1,1,1,1,0,1,0];
postindex[9]=[1,1,0,0,0,1,0,1,1];
function Hamming_distance(a, b) {
var sum = 0;
for (var i = 0; i < a.length; i++) {
sum += Math.abs(a[i]-b[i]);
}
return sum;
}
console.log(postindex);
var hd = {};
for (var i = 0; i < 10; i++) {
var arr = [];
for (var j = 0; j < 10; j++) {
arr[j] = Hamming_distance(postindex[i],postindex[j]);
hd[i] = arr;
}
}
console.log('');
console.log(hd);
Видно что проблема между 0 и 8 самая большая (расстояние всего 1 единица), еще есть проблема между 5 и 8, там расстояние 2, что тоже не очень хорошо, особенно для вот такой опечатки:
Эта неправильной формы девятка, изменением всего одной палочки, может превратиться и в 8 и в 5. (То, что цифра похожа еще на 9 — не рассматриваем, потому что там 2 ошибки нужны)
Что можно сделать?
Попробуем для начала изменить цифру 0.
Слишком похоже на 9. Будет такая же проблема как у 5 и 8.
Еще вариант:
Аналогично с 6.
Наклоняем ноль:
Вроде бы то, что нужно. Проверяем:
0 1 2 3 4 5 6 7 8 9
'0': [ 0, 3, 4, 4, 6, 9, 5, 3, 7, 5 ]
'1': [ 3, 0, 5, 5, 3, 6, 4, 4, 6, 6 ]
'2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ]
'3': [ 4, 5, 4, 0, 6, 5, 5, 3, 7, 3 ]
'4': [ 6, 3, 6, 6, 0, 3, 5, 7, 3, 3 ]
'5': [ 9, 6, 5, 5, 3, 0, 4, 6, 2, 4 ]
'6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ]
'7': [ 3, 4, 5, 3, 7, 6, 4, 0, 6, 6 ]
'8': [ 7, 6, 5, 7, 3, 2, 4, 6, 0, 4 ]
'9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ]
Всё очень даже неплохо! С одной из цифр разобрались.
Боремся до конца
Теперь нужно что-нибудь придумать для 5 и 8. Скажем НЕТ расстоянию Хэмминга меньше трёх. Рисуем пятёрки разной степени уродства.
Для второго варианта минимальное расстояние Хемминга для всех цифр больше двух, но это уродство сложно назвать пятеркой. Думаем над другими вариантами.
Может, стоит в качестве восьмёрки использовать полностью закрашенный вариант?
Тестируем:
0 1 2 3 4 5 6 7 8 9
'0': [ 0, 3, 4, 4, 6, 9, 5, 3, 5, 5 ]
'1': [ 3, 0, 5, 5, 3, 6, 4, 4, 6, 6 ]
'2': [ 4, 5, 0, 4, 6, 5, 7, 5, 5, 3 ]
'3': [ 4, 5, 4, 0, 6, 5, 5, 3, 5, 3 ]
'4': [ 6, 3, 6, 6, 0, 3, 5, 7, 5, 3 ]
'5': [ 9, 6, 5, 5, 3, 0, 4, 6, 4, 4 ]
'6': [ 5, 4, 7, 5, 5, 4, 0, 4, 4, 8 ]
'7': [ 3, 4, 5, 3, 7, 6, 4, 0, 6, 6 ]
'8': [ 5, 6, 5, 5, 5, 4, 4, 6, 0, 4 ]
'9': [ 5, 6, 3, 3, 3, 4, 8, 6, 4, 0 ]
Ура! Нет ни одной двойки в матрице, Нео!
Итоговый вариант
В данной схеме цифр, одну любую допущенную ошибку можно будет автоматически исправить.
Эпилог
Результат моих измышлений знакомого робота удовлетворил, но он высказал опасения, что все прям сразу привыкнуть к такому варианту не смогут. Но я уверил его, что это изменение нужно для пользы россиян. Письма станут доходить быстрее и ошибок станет меньше. А если всё же не придётся по душе людям данный вариант написания цифр индекса, то вернем старую схему. В общем, выигрываем в любом случае.
Автор: lucius
