algorytm.org

Algorytm Verhoeff'a

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Verhoeff'a
Ocena użytkowników:***** / 3
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 11 kwietnia 2007 19:42

Algorytm Verhoeff'a, który służy do obliczania sumy kontrolnej został po raz pierwszy opublikowany w 1969. Jego nazwa pochodzi od twórcy - holenderskiego matematyka Jacobus'a Verhoeff'a. Opracowana przez niego metoda jest doskonalsza od przedstawionego algorytmu Luhn'a i pozwala na wykrycie:
  • wszystkich błędów na jednym znaku,
  • wszystkich błędów zamiany kolejności dwóch znaków, np: 09 -> 90 i na odwrót,
  • większość podwójnych błędów, np: 22 -> 33,
  • większość podwójnych błędów oddzielonych znakiem, np: 494 -> 191,
  • większość zmian kolejności trzech znaków , np: 123 -> 321,
  • większość tzw. błędów fonetycznych dla języka angielskiego, np: "sixty" -> "sixteen" 60 -> 16.

Algorytm pozwala zabezpieczyć ciąg cyfr dowolnej długości. Numery używające tej metody mają następującą strukturę XXXXXXXC, gdzie XXXXXXX to numer identyfikacyjny (o dowolnej liczbie cyfr), a C to cyfra kontrolna. Algorytm bazuje na właśnościach grupy dihedralnej D5. W praktyce wykorzystuje się 3 tablice z gotowymi wartościami:

Pierwsza tablica d zawiera wartości mnożenia w grupie dihedrealnej D5.

d0123456789
00123456789
11234067895
22340178956
33401289567
44012395678
55987604321
66598710432
77659821043
88765932104
99876543210

Kolejna tablica p zawiera permutację dla każdej cyfry, bazujące na jej pozycji w sprawdzanym identyfikatorze. Pozycje w numerze zabezpieczonym tą metodą liczone są od prawej do lewej począwszy od zera. Permutacje powtarzają się po ósmym wierszu, czyli permutacja dla pozycji 8 jest taka sama jak dla pozycji 0, dla 9 taka jak dla 1, itd...

p0123456789
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258

Trzecia tablica inv przedstawia element odwrotny mnożenia w grupie D5 przedstawionego w pierwszej tabeli, czyli taki że: d(i, inv(i)) = 0. Tablica ta nie jest używana do sprawdzania czy dany identyfikator jest prawidłowy a jedynie do wyznaczenia cyfry kontrolnej dla zadanego numeru.

0123456789
0432156789

Sprawdzanie poprawności numeru jest bardzo proste - kolejne cyfry numeru identyfikacyjnego oznaczymy przez ni, gdzie i jest pozycją cyfry w identyfikatorze licząc od 0 od prawej strony. Zatem n0 to cyfra kontrolna.
  • inicjujemy zmienną pomocniczą c = 0
  • dla kolejnych cyfr od prawej do lewej strony obliczamy korzystając z podanych wcześniej tablic:
    c = d(c, p(i mod 8, ni))
  • jeżeli po wykonaniu obliczeń dla wszystkich cyfr c = 0, to podany identyfikator jest prawidłowy

Przykład:

Sprawdzimy czy identyfikator 8107 jest prawidłowy.
Inicjujemy c = 0 i przystępujemy do obliczeń.
c = d(c, p(i mod 8, ni))
c = d(0, p(0 mod 8, 7)) = d(0, 7) = 7
c = d(7, p(1 mod 8, 0)) = d(7, 1) = 6
c = d(6, p(2 mod 8, 1)) = d(6, 8) = 3
c = d(3, p(3 mod 8, 8)) = d(3, 2) = 0
c = 0. Zatem identyfikator 8107 jest prawidłowy.

A co w sytuacji, gdy mamy identyfikator i chcemy obliczyć cyfrę kontrolną? Tutaj schemat postępowania jest również dosyć prosty - tak jak poprzednio kolejne cyfry numeru identyfikacyjnego oznaczymy przez ni, gdzie i jest pozycją cyfry w identyfikatorze licząc od 0 od prawej strony. Zatem n0 to cyfra kontrolna.:
  • inicjujemy cyfrę kontrolną, n0 = 0
  • inicjujemy zmienną pomocniczą c = 0
  • dla kolejnych cyfr od prawej do lewej strony obliczamy korzystając z podanych wcześniej tablic:
    c = d(c, p(i mod 8, ni))
  • po wykonaniu obliczeń dla wszystkich wstawiamy wartość cyfry kontrolnej n0 = inv(c)

Przykład:

Obliczymy cyfrę kontrolną dla identyfikatora 123c.
Na początku inicjujemy cyfrę kontrolną zerem, zatem otrzymujemy 1230.
Inicjujemy c = 0 i przystępujemy do obliczeń.
c = d(c, p(i mod 8, ni))
c = d(0, p(0 mod 8, 0)) = d(0, 0) = 0
c = d(0, p(1 mod 8, 3)) = d(0, 6) = 6
c = d(6, p(2 mod 8, 2)) = d(6, 0) = 6
c = d(6, p(3 mod 8, 1)) = d(6, 9) = 2
wartość cyfry kontrolnej n0 = inv(c) = inv(2) = 3.
Zatem poprawny identyfikator z cyfrą kontrolną to 1233.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 sierpnia 2012 07:13
Komentarze
photo
-1 # i 2012-05-28 08:15
thank you very much.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz