Алгарытм Верхуфа

З пляцоўкі Вікіпедыя
Jump to navigation Jump to search

Алгарытм Верхуфа (англ.: Verhoeff algorithm) — алгарытм разліку кантрольнага ліку для выяўлення памылак пры ручным уводзе доўгіх лічбавых паслядоўнасцяў. Упершыню апублікаваны ў 1969 годзе нідэрландскім матэматыкам Якабам Верхуфам. Алгарытм дазваляе выявіць такую ж колькасць памылак, як аналагічны алгарытм Луна, але памылкі, якія выяўляюцца толькі першым, здзяйсняюцца людзьмі звычайна часцей, чым памылкі, якія выяўляюцца толькі другім.

Сутнасць[правіць | правіць зыходнік]

Замест падсумоўвання здабыткаў лічбаў на вагавыя каэфіцыенты Верхуф прапанаваў выкарыстоўваць групавую аперацыю, вядомую як дыэдральная група D5.

d(j, k) k
j 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 0 6 7 8 9 5
2 2 3 4 0 1 7 8 9 5 6
3 3 4 0 1 2 8 9 5 6 7
4 4 0 1 2 3 9 5 6 7 8
5 5 9 8 7 6 0 4 3 2 1
6 6 5 9 8 7 1 0 4 3 2
7 7 6 5 9 8 2 1 0 4 3
8 8 7 6 5 9 3 2 1 0 4
9 9 8 7 6 5 4 3 2 1 0

Вынік аперацыі d(j, k) прасцей за ўсё вызначыць па табліцы, дзе ён размяшчаецца на скрыжаванні j-га радка і k-га слупка табліцы. Абраная Верхуфам аперацыя не з’яўляецца камутатыўнай.

Паслядоўна выконваючы аперацыю d(j, k), дзе j — вынік папярэдняй ітэрацыі (0 для першай ітэрацыі), а k — чарговая лічба ліку, можна атрымаць алгарытм вылічэння кантрольнага ліку, лепшы, чым звычайнае складанне па модулі 10. Сапраўды, нягледзячы на ​​тое, што абодва алгарытмы выяўляюць аднолькавыя памылкі, алгарытм Верхуфа дазваляе вызначыць 60 з 90 магчымых памылак перастаноўкі суседніх лічбаў, у адрозненні ад складання па модулі 10.

Аднак Верхуф пайшоў далей. Ён прапанаваў выкарыстоўваць у якасці другога параметру d(j, k) не самую лічбу, а вынік яшчэ адной аперацыі — p(x, y), дзе y — лічба, x — пазіцыя гэтай лічбы па модулі 8. Вынік гэтай аперацыі таксама зручна вызначаць па табліцы.

p(x, y) y
x 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 5 7 6 2 8 3 0 9 4
2 5 8 0 3 7 9 6 1 4 2
3 8 9 1 6 0 4 3 5 2 7
4 9 4 5 3 1 2 6 8 7 0
5 4 2 8 6 5 7 3 9 0 1
6 2 7 9 3 8 0 6 4 1 5
7 7 0 4 6 9 1 3 2 5 8

Алгарытм валідацыі кантрольнага ліку[правіць | правіць зыходнік]

  1. Узяць зыходнае значэнне c = 0.
  2. Для кожнай лічбы разглядаемага ліку n, пачынаючы з найменш значнай (справа), вылічыць c = d(c, p (i, ni)), дзе i — парадкавы нумар лічбы, а ni — значэнне лічбы.
  3. Калі c = 0, кантрольны лік правільны.

Алгарытм вылічэння кантрольнага ліку[правіць | правіць зыходнік]

  1. Узяць зыходнае значэнне c = 0.
  2. Для кожнай лічбы зыходнага ліку, пачынаючы з найменш значнай (справа), вылічыць c = d(c, p(i + 1,ni</ sub>)), дзе i — парадкавы нумар лічбы, а n< sub>i</ sub> — значэнне лічбы.
  3. Дадаць справа да зыходнага ліку вынік аперацыі inv(c), вызначаны па яшчэ адной табліцы:
j 0 1 2 3 4 5 6 7 8 9
inv(j) 0 4 3 2 1 5 6 7 8 9

Рэалізацыя валідацыі[правіць | правіць зыходнік]

JS[правіць | правіць зыходнік]

const assert = require("assert")

const D_OP_TABLE = [
    [0,1,2,3,4,5,6,7,8,9],
    [1,2,3,4,0,6,7,8,9,5],
    [2,3,4,0,1,7,8,9,5,6],
    [3,4,0,1,2,8,9,5,6,7],
    [4,0,1,2,3,9,5,6,7,8],
    [5,9,8,7,6,0,4,3,2,1],
    [6,5,9,8,7,1,0,4,3,2],
    [7,6,5,9,8,2,1,0,4,3],
    [8,7,6,5,9,3,2,1,0,4],
    [9,8,7,6,5,4,3,2,1,0]
]

const P_OP_TABLE = [
    [0,1,2,3,4,5,6,7,8,9],
	[1,5,7,6,2,8,3,0,9,4],
	[5,8,0,3,7,9,6,1,4,2],
	[8,9,1,6,0,4,3,5,2,7],
	[9,4,5,3,1,2,6,8,7,0],
	[4,2,8,6,5,7,3,9,0,1],
	[2,7,9,3,8,0,6,4,1,5],
	[7,0,4,6,9,1,3,2,5,8]
]

const d_op = (digit1, digit2) => D_OP_TABLE[digit1][digit2]
const p_op = (digit1, digit2) => P_OP_TABLE[digit1][digit2]

module.exports = (num) => {
    assert(num)
    assert(num.length)

    let digits = [...Array(9).keys()]

    for(i = num.length - 1; i > 0; i--)
        assert(num[i] in digits)
    
    let i
    let checksum = 0

    for(i = num.length; i > 0; i--) {
        checksum = d_op(checksum, p_op(i, num[i]))
    }

    return checksum == 0
}

Рэалізацыя вылічэння[правіць | правіць зыходнік]

JS[правіць | правіць зыходнік]

const assert = require("assert")

const D_OP_TABLE = [
    [0,1,2,3,4,5,6,7,8,9],
    [1,2,3,4,0,6,7,8,9,5],
    [2,3,4,0,1,7,8,9,5,6],
    [3,4,0,1,2,8,9,5,6,7],
    [4,0,1,2,3,9,5,6,7,8],
    [5,9,8,7,6,0,4,3,2,1],
    [6,5,9,8,7,1,0,4,3,2],
    [7,6,5,9,8,2,1,0,4,3],
    [8,7,6,5,9,3,2,1,0,4],
    [9,8,7,6,5,4,3,2,1,0]
]

const P_OP_TABLE = [
    [0,1,2,3,4,5,6,7,8,9],
	[1,5,7,6,2,8,3,0,9,4],
	[5,8,0,3,7,9,6,1,4,2],
	[8,9,1,6,0,4,3,5,2,7],
	[9,4,5,3,1,2,6,8,7,0],
	[4,2,8,6,5,7,3,9,0,1],
	[2,7,9,3,8,0,6,4,1,5],
	[7,0,4,6,9,1,3,2,5,8]
]

const d_op = (digit1, digit2) => D_OP_TABLE[digit1][digit2]
const p_op = (digit1, digit2) => P_OP_TABLE[digit1][digit2]

const INV_OP_ARRAY = [0,4,3,2,1,5,6,7,8,9]

const inv_op = (digit) => INV_OP_ARRAY[digit]

module.exports = (num) => {
    assert(num)
    assert(num.length)

    let digits = [...Array(9).keys()]

    for(i = num.length; i > 0; i--)
        assert(num[i] in digits)
    
    let i
    let checksum = 0

    let crc_num = []
    for(i = num.length - 1; i > 0; i--) {
        checksum = d_op(checksum, p_op(i + 1, num[i]))
        crc_num.unshift(num[i])
    }

    crc_num.unshift(inv_op(checksum))

    return crc_num
}

Гл. таксама[правіць | правіць зыходнік]