Verhoeff algoritması - Verhoeff algorithm

Verhoeff algoritması a, sağlama için, formül hata algılama Hollanda mathematician tarafından geliştirilen Jacobus Verhoeff ve birinci ilk ondalık 1969 yılında yayınlandı kontrol basamağı tüm tek basamaklı hataları tespit algoritması, ve iki komşu basamak, ilgili tüm transpozisyon hataları olan o zamanlar böyle bir kodla imkansız görülüyordu.

Hedefler

Verhoeff, tüm tek basamaklı hataları ve bitişik basamakların tüm aktarımlarını algılayan, kontrol basamağının tek bir ondalık basamak olduğu bir ondalık kod bulma hedefine sahipti. O zamanlar, bu kodların var olmadığına dair varsayılan kanıtlar, örneğin ISBN kontrol basamağı gibi 11 tabanlı kodları popüler hale getirdi .

Hedefleri de pratikti ve farklı kodların değerlendirmesini, farklı hata türleri için ağırlıklı puan sistemi kullanarak Hollanda posta sisteminden alınan canlı verilere dayandırdı. Analiz, hataları birkaç kategoriye ayırdı: birincisi, kaç rakamın hatalı olduğuna göre; iki basamak hatalı olanlar için, transpozisyonlar ( ab → ba ), ikizler ( aa → 'bb'), atlama transpozisyonları ( abc → cba ), fonetik ( 1a → a0 ) ve atlama ikizleri ( aba → cbc ) vardır. Ek olarak atlanmış ve eklenen rakamlar vardır. Bu tür hataların bazılarının sıklıkları küçük olsa da, tüm tekilleri ve aktarımları tespit etmenin birincil amaçlarına ek olarak bazı kodlar bunlara karşı bağışık olabilir.

Özellikle fonetik hatalar dilbilimsel etkiler gösterdi, çünkü Hollandaca'da sayılar tipik olarak çiftler halinde okunur; ve 50 Hollandaca'da 15'e benzerken, 80 kulağa 18 gibi gelmiyor.

Verhoeff, altı basamaklı sayıları örnek alarak, hataların aşağıdaki sınıflandırmasını bildirdi:

Hatalı rakamlar	Sınıflandırma	Miktar	Sıklık
1	Transkripsiyon	9.574	% 79.05
2	Transpozisyonlar	1.237	% 10.21
	İkizler	67	% 0,55
	Fonetik	59	% 0.49
	Diğer bitişik	232	% 1.92
	Yer değiştirmeleri atlama	99	% 0.82
	Jump Twins	35	% 0.29
	Diğer atlama hataları	43	% 0,36
	Diğer	98	% 0.81
3		169	% 1.40
4		118	% 0.97
5		219	% 1,81
6		162	% 1,34
Toplam		12.112

Açıklama

Verhoeff, algoritmasını , bir permütasyonla birlikte, 10. dereceden dihedral grubun özelliklerini ( on eleman üzerinde değişmeyen, düzenli bir beşgenin dönüşüne ve yansımasına karşılık gelen, değişmeyen bir işlem sistemi) kullanarak tasarladı . Bunun, dihedral grubun ilk pratik kullanımı olduğunu iddia etti ve sonunda, tüm güzel matematiğin bir kullanım bulacağı ilkesini doğruladı, pratikte algoritma, nasıl yapılacağını anlamaya gerek kalmadan basit arama tabloları kullanılarak uygulanacaktır . bu tabloları temeldeki grup ve permütasyon teorisinden oluşturur.

Mümkün olan başka permütasyonlar olduğundan ve Verhoeff'in tedavisinde tartışıldığından, bu daha doğru bir algoritma ailesi olarak kabul edilir. Bu özel permütasyonun,

{\ displaystyle {\ begin {pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 5 & 7 & 6 & 2 & 8 & 3 & 0 & 9 & 4 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 5 & 8 & 9 & 4 & 2 & 7 & 0 \ end {pmatrix}} {\ başla \ {pmatrix}} {\ 6 {pmatrix}}

fonetik hataların% 95,3'ünü algılama özelliğine sahip olduğu için özeldir.

Algoritmanın güçlü yönleri, tüm transliterasyon ve transpozisyon hatalarını ve ayrıca en çok ikiz, ikiz atlama, atlama transpozisyonu ve fonetik hataları tespit etmesidir.

Verhoeff algoritmasının temel zayıflığı karmaşıklığıdır. Gerekli hesaplamalar bir formül olarak kolayca ifade edilemez. Kolay hesaplama için arama tabloları gereklidir. Benzer bir kod, benzer niteliklere sahip Damm algoritmasıdır .

Tablo tabanlı algoritma

Verhoeff algoritması üç tablo kullanılarak uygulanabilir: çarpım tablosu d , ters tablo inv ve permütasyon tablosu p .

${\ displaystyle d (j, k)}$		k
${\ displaystyle d (j, k)}$		0	1	2	3	4	5	6	7	8	9
j	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

${\ displaystyle inv (j)}$

j	0	0
	1	4
	2	3
	3	2
	4	1
	5	5
	6	6
	7	7
	8	8
	9	9

${\ displaystyle p (konum, sayı)}$		num
${\ displaystyle p (konum, sayı)}$		0	1	2	3	4	5	6	7	8	9
$konum (mod 8)$	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

Birinci tablo, d , dihedral D grubunun çarpım dayanır ₅ . ve basitçe grubun Cayley tablosu . Bu grubun, bazı j ve k , d ( j , k ) ≠ d ( k , j ) değerleri için değişmeli olmadığını unutmayın .

Ters tablo inv , bir basamağın çarpımsal tersini, yani d ( j , inv ( j )) = 0'ı karşılayan değeri temsil eder .

Permütasyon tablosu p , sayıdaki konumuna bağlı olarak her basamağa bir permütasyon uygular . Bu aslında yinelemeli olarak uygulanan tek bir permütasyondur (1 5 8 9 4 2 7 0) (3 6); yani p ( i + j , n ) = p ( i , p ( j , n )).

Verhoeff sağlama toplamı hesaplaması şu şekilde gerçekleştirilir:

Bir dizi oluşturma n sağdan sola doğru alınan sayıda bireysel basamağı üzerinden (en sağdaki rakam olduğu , n ₀ , vb.)
Sağlama toplamını c'yi sıfıra ayarlayın.
Sıfırdan başlayarak, n dizisinin her bir i indeksi için c'yi d ile değiştirin (c, p (i mod 8, n _i )).

Orijinal numara ancak ve ancak c = 0 ise geçerlidir .

Bir kontrol basamağı oluşturmak için, bir 0 ekleyin , hesaplamayı gerçekleştirin: doğru kontrol basamağı inv (c) 'dir .

Örnekler

236 için bir kontrol basamağı oluşturun :

ben	n _ben	p ( ben, n _ben )	c
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

c 2'dir, bu nedenle kontrol basamağı inv (2) 3'tür.

2363 numaralı kontrol basamağını doğrulayın :

ben	n _ben	p ( ben, n _ben )	c
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c sıfırdır, dolayısıyla kontrol doğrudur.

Referanslar

Dış bağlantılar

Verhoeff algoritmasının ayrıntılı açıklaması

Languages

In other projects