wd wp Пошук: ⬜

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

Алгарытм Верхуфа (англ.: 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

Алгарытм валідацыі кантрольнага ліку

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

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

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

Гл. таксама

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

Тэмы гэтай старонкі (1):
Катэгорыя·Алгарытмы