Hammingdistanz a la EPROG

Choose

Hammingdistanz a la EPROG

updated by rck, 2004-11-06

Ich habe mal spaßhalber ein Programm aus der EPROG-Beispielsammlung umgesetzt. Es hat die Nummer 1074 und ermittelt die Hammingdistanz von ein paar übergebenen Codewörtern.

1 | 2 | 3 | 4 | 5 | 6

Die Hammingdistanz
Hier wird's interessant. Der Kern unseres Programms ist genauso kurz und kompakt, wie der Rest. Mit effektiv 3 Programmzeilen ermitteln wir die Hammingdistanz zweier Codewörter. Die Länge sollte bereits überprüft worden sein.

distance(String, String, int)
`110 public static int distance(String a, String b,` `111 int len) throws Exception {` `112` `113 int d=0;` `114` `115 for(int i=0; i<len; i++)` `116 if(a.charAt(i) != b.charAt(i))` `117 d++;` `118` `119 return(d);` `120 }`

Beschreibung distance(String, String, int)
113 gehen wir mal davon aus, dass die beiden Wörter gleich sind. 115 Wir schauen dann bei jedem Zeichen... 116 ob das auch stimmt und... 117 erhöhen, falls dem nicht so ist die Anzahl der gefundenen Unterschiede... 119 ...die wir dann zurückliefern. Fertig.

distance(String)
Damit das ganze Hand und Fuß bekommt, verknüpfen wir jetzt unsere Hammingdistanzberechnung mit der Fehlerbehandlung. Wichtig dabei ist, sämtliche Wünsche der Aufgabenbeschreibung abzudecken. Ich habe die Methode wieder distance genannt, immerhin tut sich de facto das gleiche wie die andere distance-Funktion. Der Compiler kann sie dennoch anhand der Typen und Parameteranzahl unterscheiden. `177 public static String distance(String a) throws Exception {` `178` `179 // Was ist ein StringTokenizer ?` `180 // steht auf http://www.kiesler.at/article60.html` `181 StringTokenizer st=new StringTokenizer(a);` `182` `183 int len=get_wordlen(st.nextToken()), dist=len,` `184 words=2;` `185` `186 String prev=st.nextToken(), s=st.nextToken();` `187 check_length(prev, len);` `188` `189 while(is_binary(s)) {` `190 check_length(s, len);` `191` `192 dist=min(dist, distance(s, prev, len));` `193` `194 prev=s;` `195 s=st.nextToken(); words++;` `196 }` `197` `198 words--; // der Terminator gilt nicht!` `199` `200 check_termlength(s);` `201 check_wordcount(words);` `202` `203 return(new Integer(dist).toString());` `204 }`

distance(String)

Damit das ganze Hand und Fuß bekommt, verknüpfen wir jetzt unsere Hammingdistanzberechnung mit der Fehlerbehandlung. Wichtig dabei ist, sämtliche Wünsche der Aufgabenbeschreibung abzudecken.

Ich habe die Methode wieder distance genannt, immerhin tut sich de facto das gleiche wie die andere distance-Funktion. Der Compiler kann sie dennoch anhand der Typen und Parameteranzahl unterscheiden.

177         public static String distance(String a) throws Exception {
178
179                 // Was ist ein StringTokenizer ?
180                 // steht auf http://www.kiesler.at/article60.html
181                 StringTokenizer st=new StringTokenizer(a);
182
183                 int len=get_wordlen(st.nextToken()), dist=len,
184                         words=2;
185
186                 String prev=st.nextToken(), s=st.nextToken();
187                 check_length(prev, len);
188
189                 while(is_binary(s)) {
190                         check_length(s, len);
191
192                         dist=min(dist, distance(s, prev, len));
193
194                         prev=s;
195                         s=st.nextToken(); words++;
196                 }
197
198                 words--;        // der Terminator gilt nicht!
199
200                 check_termlength(s);
201                 check_wordcount(words);
202
203                 return(new Integer(dist).toString());
204         }

Beschreibung distance(String)
181 der StringTokenizer ist eine überaus praktische Klasse, die uns den übergebenen String in einzelne Strings anhand eines Trennzeichens aufteilt. Details finden sich im Artikel zum StringTokenizer. 183 get_wordlen() wandelt hier das erste Token in eine Zahl um und prüft auch gleich, ob die Länge im Rahmen liegt. 183 Wir nehmen den schlimmsten Fall an. Die Distanz zwischen zwei Codewörtern kann, wie wir schon festgestellt haben, höchstens die Codewortlänge sein. 184 Gehen wir mal von zwei Wörtern aus. 186 Nachdem die Angabe mindestens zwei Codewörter vorschreibt, können wir hier einfach mit nextToken() zwei Wörter holen. Klappt das nicht, gibt's eine Exception. Die wird dann im Hauptprogramm in "FALSCHE EINGABE" umgewandelt. Praktisch! 189 Wir wissen, dass das Terminatorsymbol nicht binär sein darf. Entsprechend eignet sich das gut als Schleifenkriterium, weil es ja die anderen sehr wohl sind. Und selbst wenn nicht, ist in beiden Fällen "FALSCHE EINGABE" als Ausgabe erwünscht. 190 Wenn die Länge nicht passt, verlassen wir die Methode mit einer Exception... 192 ...anderenfalls holen wir uns (der Code kann fast schon als Dokumentation durchgehen) das Minimum von der aktuellen kleinsten Hammingdistanz und der neu ermittelten. 194 alles neue wird mal alt, so auch das vorige Token. 195 also holen wir uns gleich ein neues und aktualisieren die Anzahl der eingelesenen Codewörter. 198 wenn wir bis hier her kommen, haben wir ein Codewort zuviel ermittelt, entsprechend ziehen wir von der Wortanzahl eins ab. Der Terminator gilt ja schließlich nicht! 200 wenn dann auch noch die Länge des Terminatorsymbols passt... 201 ...und die Anzahl der Wörter auch im Rahmen liegt... 203 liefern wir aufrufenden Methode die ermittelte minimale Hammingdistanz aller Codewörter fix fertig zurück.

Beschreibung distance(String)

181 der StringTokenizer ist eine überaus praktische Klasse, die uns den übergebenen String in einzelne Strings anhand eines Trennzeichens aufteilt. Details finden sich im Artikel zum StringTokenizer.

183 get_wordlen() wandelt hier das erste Token in eine Zahl um und prüft auch gleich, ob die Länge im Rahmen liegt.

183 Wir nehmen den schlimmsten Fall an. Die Distanz zwischen zwei Codewörtern kann, wie wir schon festgestellt haben, höchstens die Codewortlänge sein.

184 Gehen wir mal von zwei Wörtern aus.

186 Nachdem die Angabe mindestens zwei Codewörter vorschreibt, können wir hier einfach mit nextToken() zwei Wörter holen. Klappt das nicht, gibt's eine Exception. Die wird dann im Hauptprogramm in "FALSCHE EINGABE" umgewandelt. Praktisch!

189 Wir wissen, dass das Terminatorsymbol nicht binär sein darf. Entsprechend eignet sich das gut als Schleifenkriterium, weil es ja die anderen sehr wohl sind. Und selbst wenn nicht, ist in beiden Fällen "FALSCHE EINGABE" als Ausgabe erwünscht.

190 Wenn die Länge nicht passt, verlassen wir die Methode mit einer Exception...

192 ...anderenfalls holen wir uns (der Code kann fast schon als Dokumentation durchgehen) das Minimum von der aktuellen kleinsten Hammingdistanz und der neu ermittelten.

194 alles neue wird mal alt, so auch das vorige Token.

195 also holen wir uns gleich ein neues und aktualisieren die Anzahl der eingelesenen Codewörter.

198 wenn wir bis hier her kommen, haben wir ein Codewort zuviel ermittelt, entsprechend ziehen wir von der Wortanzahl eins ab. Der Terminator gilt ja schließlich nicht!

200 wenn dann auch noch die Länge des Terminatorsymbols passt...
201 ...und die Anzahl der Wörter auch im Rahmen liegt...

203 liefern wir aufrufenden Methode die ermittelte minimale Hammingdistanz aller Codewörter fix fertig zurück.

1 | 2 | 3 | 4 | 5 | 6

Die Problemstellung
Fehlerüberprüfungen
Die Hammingdistanz
Das Hauptprogramm
hammin.java
Fazit