skip to main content

kiesler.at

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         }

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



RSSComments - Make a comment
The comments are owned by the poster. We are not responsible for its content.
RSSAll Articles
2008, 2007, 2006, 2005, 2004