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

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

Сутнасць

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

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, n_i)), дзе i — парадкавы нумар лічбы, а n_i — значэнне лічбы.
3. Калі c = 0, кантрольны лік правільны.

Алгарытм вылічэння кантрольнага ліку

1. Узяць зыходнае значэнне c = 0.
2. Для кожнай лічбы зыходнага ліку, пачынаючы з найменш значнай (справа), вылічыць c = d(c, p(i + 1,n_i)), дзе i — парадкавы нумар лічбы, а n_i — значэнне лічбы.
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
}

Гл. таксама

• Алгарытм Луна