短い背景
少し前に、おなじみのロボットと話しました。 彼は手紙の選別機によってロシアの郵便局に一時的に定住した。 仕事はほこりっぽくなく、手紙のインデックスを見て、希望の穴に入れます。 ただし、索引にタイプミスのある文字には問題があります。 正しいインデックスを見つけるのに多くの時間がかかり、ビールは蒸気を使い果たします。
頭の破片
その会話から十分な時間が経ちましたが、郵便番号のジレンマは私の心を離れませんでした。
どうやら-ここで他に改善できることは何ですか？ インデックスの数字の見た目を変換して、1つのミスが見つかっても自動的に検出して修正できるようにしましょう。
改善できることがわかりました。
新しい種類の数字0を描画してみましょう。
興味があれば、理由と理由-猫をお願いします。
大学に戻って、離散数学に関する講義で、筆記された数字のいくつかの間のハミング距離が小さすぎることに気付きました。 例ではこれまでに行きません;これらは0と8です。 ワンドを「再配置」すれば十分であり、1つの数字が別の数字に変わります。
さらなる研究
同様の数字でまだ問題がありますか？ 実際、この特定のケースでは、数値間の距離が大きいほど、ロボットがエラーを修正しやすくなります。 私たちは、図の1つの間違いに限定しています。 例：
1つのスティックが欠落していることがわかりますが、それがどのようなエラーであったかをアルゴリズム的に判断して修正することができます。
数字のスケルトンの各スティックを指定します（はい、そのようなしゃれ）：
各桁に独自のベクトルを割り当てます。
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の距離があるため、特にこのようなタイプミスではあまり良くありません。
この不規則な形の9本は、1本のスティックを交換するだけで、 8と5に変わります。 （2つのエラーが必要なので、図が別の9と類似しているという事実は考慮しません）
何ができますか？
番号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 ]
すべてがとても良いです！ 数字の1つを見つけました。
最後まで戦う
今、あなたは5と8のために何かを考え出す必要があります。 ハミング距離が3未満の場合は、NOと言います。 さまざまな程度のさを5つ描画します。
2番目のオプションの場合、すべての数値の最小ハミング距離は2を超えますが、このlinesさを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 ]
やった！ マトリックスにはデュースはありません
最終オプション
この数字の体系では、ミスを1つでも自動的に修正できます。
エピローグ
おなじみのロボットの私の考えの結果は満足したが、彼は誰もがすぐにこのオプションに慣れることができないだろうという恐れを表明した。 しかし、私は彼に、この変更はロシア人の利益のために必要であることを保証した。 手紙はより早く届き始め、エラーが少なくなります。 インデックス番号を書き込むためのこのオプションがまだ好まれない場合は、古いスキームを返します。 一般的に、私たちはとにかく勝ちます。
UPD：
Habrauser jaguardは、 この問題に対するよりエレガントなソリューションを提案しました。