Regelmäßig stehen Entwickler vor der Aufgabe, Nutzereingaben auf Korrektheit zu prüfen. Mittlerweile existiert eine erhebliche Anzahl an standardisierten Datenformaten, mit denen solche Validierungsaufgaben leicht zu meistern sind. Die International Standard Book Number oder kurz ISBN ist ein solches Datenformat. ISBN gibt es in zwei Ausführungen: in einer zehnstelligen und in einer 13-stelligen Variante. Von 1970 bis 2006 wurde die zehnstellige Version der ISBN verwendet (ISBN-10), die im Januar 2007 von der 13-stelligen Fassung abgelöst wurde (ISBN-13). Heutzutage ist es in vielen Verlagen verbreitete Praxis, für Titel beide Versionen der ISBN bereitzustellen. Dass sich anhand dieser Nummer Bücher eindeutig identifizieren lassen, ist allgemein bekannt. Das bedeutet natürlich auch, dass diese Nummern eindeutig sind. Es gibt also keine zwei unterschiedlichen Bücher mit gleicher ISBN (Bild 1).
Der theoretische Hintergrund, um festzustellen, ob eine Zahlenfolge korrekt ist stammt aus der Codierungstheorie. Wer sich also etwas ausführlicher mit dem mathematischen Hintergrund Fehler-erkennender und Fehler-korrigierender Codes beschäftigen möchte, dem Sei das Buch „Codierungstheorie“ von Ralph Hardo Schulz empfohlen [1]. Darin lernt man beispielsweise, wie die Fehlerkorrektur bei Comact Disks (CD) funktioniert. Aber keine Sorge, wir reduzieren in diesem kleinen Workshop die notwendige Mathematik auf ein Minimum.
Bei der ISBN handelt es sich um einen Fehler erkennenden Code. Wir können also den erkannten Fehler nicht automatisch wieder beheben. Wir wissen nur, dass etwas falsch ist, kennen aber nicht den konkreten Fehler. Gehen wir der Sache daher ein wenig auf den Grund.
Warum man sich bei ISBN-13 genau auf 13 Stellen geeinigt hat, bleibt Spekulation. Zumindest haben sich die Entwickler nicht von irgendwelchem Aberglauben beeindrucken lassen. Das große Geheimnis hinter der Validierung ist die Bestimmung der Restklassen [2]. Die Algorithmen für ISBN-10 und ISBN-13 sind recht ähnlich. Beginnen wir also mit dem älteren Standard, ISBN-10, der sich wie folgt errechnet:
1x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + 7x7 + 8x8 + 9x9 + 10x10 = k modulo 11
Keine Sorge, um die oben stehende Formel zu verstehen, müssen Sie kein Raketeningenieur bei SpaceX sein. Wir heben den Schleier der Verwirrung anschaulich mit einem kleinen Beispiel für die ISBN 3836278340. Daraus ergibt sich folgende Rechnung:
(1*3) + (2*8) + (3*3) + (4*6) + (5*2) + (6*7) + (7*8) + (8*3) + (9*4) + (10*0) = 220 220 modulo 11 = 0
Die letzte Ziffer der ISBN ist die sogenannte Prüfziffer. In dem aufgeführten Beispiel lautet diese 0. Um diese Prüfziffer zu erhalten, multiplizieren wir jede Stelle mit ihrem Wert. Das heißt, an vierter Position steht eine 6, also rechnen wir 4 * 6. Das wiederholen wir mit allen Positionen und die einzelnen Ergebnisse addieren wir zusammen. So erhalten wir den Betrag 220. Die 220 wird mit der sogenannten Restwertoperation Modulo durch 11 geteilt. Da die 11 genau 20 mal in die 220 hineinpasst, bleibt ein Rest null. Das Ergebnis von 220 modulo 11 ist 0 und stimmt mit der Prüfziffer überein, was uns sagt das eine gültige ISBN-10 vorliegt.
Eine Besonderheit gibt es aber noch zu beachten. Bisweilen kommt es vor, dass die letzte Ziffer der ISBN mit X endet. In diesem Fall ist das X gegen 10 auszutauschen.
Wir sehen, der Algorithmus ist sehr einfach gehalten und kann leicht über eine einfache for-Schleife umgesetzt werden.
boolean success = false;
int[] isbn;
int sum = 0;
for(i=0; i<10; i++) {
sum += i*isbn[i];
}
if(sum%11 == 0) {
success = true;
}
Um den Algorithmus so einfach wie möglich zu halten, wird jede Stelle der ISBN-10-Nummer in einem Integer-Array gespeichert. Ausgehend von dieser Vorbereitung ist es nur noch nötig, das Array zu durchlaufen. Wenn dann die Überprüfung der Summe durch das Modulo 11 das Ergebnis 0 liefert, ist alles bestens.
Um die Funktion richtig zu testen, werden zwei Testfälle benötigt. Einerseits gilt es zu überprüfen ob eine ISBN korrekt erkannt wird. Der zweite Test überprüft die sogenannten false positives. Es wird also ein erwarteter Fehler mit einer falschen ISBN provoziert. Das lässt sich zügig bewerkstelligen, indem man von einer gültigen ISBN eine beliebige Stelle ändert.
Unser ISBN-10 Validator hat noch einen kleinen Schönheitsfehler. Ziffernfolgen, die kürzer oder länger als 10 sind, also dem erwarteten Format nicht entsprechen, könnten bereits vorher abgewiesen werden. Der Grund hierfür lässt sich in dem Beispiel erkennen: Die letzte Stelle der ISBN-10 ist eine 0 – somit ist das Zeichenergebnis auch 0. Wird die letzte Stelle also vergessen und eine Prüfung auf das korrekte Format fehlt, wird der Fehler nicht erkannt. Etwas das keine Auswirkung auf den Algorithmus hat, aber sehr hilfreich als Feedback bei Nutzereingaben ist, ist das Eingabefeld so lange auszugrauen und den Absenden-Button zu deaktivieren, bis das korrekte Format der ISBN eingegeben wurde.
Der Algorithmus für ISBN-13 ist ähnlich einfach aufgebaut.
x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 + 3x12 + x13 = k modulo 10
Analog wie bei ISBN-10 steht xn für den Zahlenwert an der entsprechenden Position in er ISBN-13. Auch hier werden die Teilergebnisse aufsummiert und durch ein Modulo geteilt. Der große Unterschied ist, dass hier nur die geraden Positionen, also die Stellen 2, 4, 6, 8, 10 und 12, mit 3 multipliziert werden und das Ergebnis dann mit Modulo 10 dividiert wird. Als Beispiel berechnen wir die ISBN-13: 9783836278348.
9 + (3*7) + 8 + (3*3) + 8 + (3*3) + 6 + (3*2) + 7 + (3*8) + 3 + (3*4) + 8 = 130 130 modulo 10 = 0
Auch für die ISBN-13 lässt sich der Algorithmus in einer einfachen for-Schleife umsetzen.
boolean success = false;
int[] isbn;
int sum = 0;
for(i=0; i<13; i++) {
if(i%2 == 0) {
sum += 3*isbn[i];
} else {
sum += isbn[i];
}
}
if(sum%10 == 0) {
success = true;
}
Die beiden Codebeispiele zu ISBN-10 und ISBN-13 unterscheiden sich vor allem in der if-Bedingung. Der Ausdruck i % 2 berechnet den Modulo-Wert 2 zur jeweiligen Iteration. Wenn an dieser Stelle der Wert 0 herauskommt, bedeutet das, dass es sich um eine gerade Zahl handelt. Der dazugehörige Wert muss dann mit 3 multipliziert werden.
Hier zeigt sich wie praktisch die Modulo-Operation % für das Programmieren sein kann. Um die Implementierung möglichst kompakt zu halten, kann anstatt der if-else-Bedingung auch der sogenannte Dreifach-Operator verwendet werden. Der Ausdruck sum += (i%2) ? isbn[i] : 3 * isbn[3] ist wesentlich kompakter, dafür aber auch schwerer zu verstehen.
Nachfolgend finden Sie eine vollständig implementierte Klasse zur Prüfung der ISBN in den Programmiersprachen: Java, PHP und C#.
Abonnement / Subscription
[English] This content is only available to subscribers.
[Deutsch] Diese Inhalte sind nur für Abonnenten verfügbar.
Die in den Beispielen vorgestellten Lösungen haben zwar alle denselben Kernansatz, unterscheiden sich aber nicht nur in syntaktischen Details. So bietet die Java-Version eine allumfassende Variante, die etwas generischer zwischen ISBN-10 und ISBN-13 unterscheidet. Das demonstriert zum einen, dass viele Wege nach Rom führen. Soll aber auch gerade weniger erfahrenen Entwicklern verschiedene Lösungsansätze zeigen und sie motivieren, eigene Anpassungen vorzunehmen. Um das Verständnis zu vereinfachen, wurde der Quelltext mit Kommentaren angereichert. Bei PHP, als untypisierte Sprache, entfällt insbesondere das Konvertieren des Strings in Nummern. Dafür wird eine RegEx genutzt, um sicherzustellen, dass die eingegebenen Zeichen typsicher sind.
Lessons Learned
Wie Sie sehen, handelt es sich bei der Überprüfung, ob eine ISBN korrekt ist, um keine Hexerei. Das Thema der Validierung von Benutzereingaben ist natürlich viel umfangreicher. Andere Beispiele sind Kreditkartennummern. Aber auch reguläre Ausdrücke leisten in diesem Zusammenhang wertvolle Dienste.
Ressourcen
- [1] Ralph-Hardo Schulz, Codierungstheorie: Eine Einführung, 2003, ISBN 978-3-528-16419-5
- [2] Begriff der Restklasse bei Wikipedia, https://de.wikipedia.org/wiki/Restklasse
