Implementierung der Kamasutra-Chiffre
Dies ist Übung 3.1.31. aus dem Buch Informatik Ein interdisziplinärer Ansatz von Sedgewick & Wayne:
Schreiben Sie einen Filter KamasutraCipher, der zwei Zeichenfolgen als Befehlszeilenargument (die Schlüsselzeichenfolgen) verwendet, dann Zeichenfolgen (durch Leerzeichen getrennt) aus der Standardeingabe liest, jeden Buchstaben gemäß den Schlüsselzeichenfolgen ersetzt und das Ergebnis in die Standardausgabe druckt. Diese Operation ist die Basis für eines der frühesten bekannten kryptografischen Systeme. Die Bedingung für die Schlüsselzeichenfolgen ist, dass sie gleich lang sein müssen und dass jeder Buchstabe in der Standardeingabe in genau einer von ihnen erscheinen muss. Wenn die beiden Schlüssel beispielsweise THEQUICKBROWN und FXJMPSVLAZYDG sind, erstellen wir die Tabelle
THEQUICKBROWN
FXJMPSVLAZYDG
Dies sagt uns, dass wir F für T, T für F, H für X, X für H usw. ersetzen sollten, wenn wir die Standardeingabe in die Standardausgabe filtern. Die Nachricht wird codiert, indem jeder Buchstabe durch sein Paar ersetzt wird. Beispielsweise wird die Nachricht MEET AT ELEVEN als QJJF BF JKJCJG codiert. Die Person, die die Nachricht empfängt, kann dieselben Schlüssel verwenden, um die Nachricht zurückzubekommen.
Hier ist mein Programm:
public class KamasutraCipher
{
public static void encrypt(String s, String t)
{
int m = s.length();
int n = t.length();
if (m != n)
{
throw new RuntimeException("The key lengths must be equal");
}
while (!StdIn.isEmpty())
{
String word = StdIn.readString();
int wordLength = word.length();
for (int i = 0; i < wordLength; i++)
{
for (int j = 0; j < m; j++)
{
if (String.valueOf(word.charAt(i)).equals(String.valueOf(s.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
}
else if (String.valueOf(word.charAt(i)).equals(String.valueOf(t.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(s.charAt(j)) + temp.substring(i+1);
}
}
}
System.out.print(word + " ");
}
}
public static void main(String[] args)
{
encrypt(args[0], args[1]);
}
}
StdIn ist eine einfache API, die von den Autoren des Buches geschrieben wurde. Ich habe mein Programm überprüft und es funktioniert.
Gibt es eine Möglichkeit, mein Programm zu verbessern?
Danke für Ihre Aufmerksamkeit.
Antworten
Die Implementierung sieht gut aus, ich habe nur ein paar Vorschläge.
Prinzip der Einzelverantwortung
Die Methode encryptscheint viel Verantwortung zu haben:
- Liest die Eingabe vom Benutzer
- Verschlüsselt die Eingabe
- Gibt das Ergebnis an die Konsole aus
Eine Definition von SRP lautet "Eine Klasse sollte nur einen Grund zur Änderung haben". Es gibt jedoch viele Gründe, sich KamasutraCipherzu ändern:
- Die Eingabe kann von
System.in, Datei, Datenbank usw. stammen. - Die Bibliothek
StdInändert sich. - Die Ausgabe muss in eine Datei usw. gehen.
- Die Ausgabe muss für den Benutzer gut formatiert sein
- usw..
Die einzige Verantwortung von KamasutraCiphersollte darin bestehen, eine Zeichenfolge zu verschlüsseln (oder zu entschlüsseln) und das Ergebnis zurückzugeben.
Die Schnittstelle kann folgendermaßen überarbeitet werden:
public class KamasutraCipher {
public static void encrypt(String s, String t)
}
Zu:
public class KamasutraCipher {
public KamasutraCipher(String key1, String key2)
public String encrypt(String s)
}
Der einzige Grund für KamasutraCiphereine Änderung sind Optimierungen oder Änderungen des Kamasutra-Algorithmus. Letzteres wird jedoch nicht in Kürze geschehen.
Die gesamte Logik zum Anfordern des Eingangs und zum Erzeugen des Ausgangs wird an die main.
Saiten sind unveränderlich
In Java sind Zeichenfolgen unveränderliche Objekte, und jede Änderung an einer Zeichenfolge erstellt eine neue Zeichenfolge. Deshalb dieser Teil:
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
Kann geändert werden zu:
word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);
Optimierung
Die Komplexität der Methode encryptist, O(m*n)wo mdie Länge der Eingabezeichenfolge und ndie Länge des Schlüssels ist. (Ignorieren der Methoden Stringund der while-Schleife).
Ein effizienterer Weg wäre die Verwendung einer Karte zum Speichern der Zeichenfolgenschlüssel. Bei den Zeichenfolgenschlüsseln ABC und FGH würde die Karte beispielsweise Folgendes enthalten:
- A -> F.
- B -> G.
- C -> H.
- F -> A.
- G -> B.
- H -> C.
Die Methode wird encryptdann zu einer einfachen Suche auf der Karte, wodurch die Komplexität auf Folgendes reduziert wird O(m):
public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
sb.append(keyMap.get(c));
}
return sb.toString();
}
SpringBuilderLassen Sie uns Speicherplatz sparen, indem Sie die Ergebniszeichenfolge effizienter erstellen. keyMapwird im Konstruktor erstellt, da sich die Schlüssel nach der Initialisierung nicht ändern.
Eingabevalidierung
Jeder Buchstabe in der Standardeingabe muss in genau einem von ihnen erscheinen (Tasten).
Wie von anderen erwähnt, ist dies eine Anforderung, die möglicherweise in der Methode behandelt werden muss encrypt.
Für die Ausnahmen können Sie IllegalArgumentExceptionanstelle von verwenden RuntimeException.
Überarbeiteter Code
public class KamasutraCipher {
private final Map<Character,Character> keyMap;
public KamasutraCipher(String key1, String key2) {
if (key1.length() != key2.length()) {
throw new IllegalArgumentException("The key lengths must be equal");
}
keyMap = new HashMap<>();
for (int i = 0; i < key1.length(); i++) {
keyMap.put(key1.charAt(i), key2.charAt(i));
keyMap.put(key2.charAt(i), key1.charAt(i));
}
}
public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if(!keyMap.containsKey(c)) {
throw new IllegalArgumentException(String.format("'%c' is not in the keys", c));
}
sb.append(keyMap.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
KamasutraCipher cipher = new KamasutraCipher(args[0], args[1]);
while (!StdIn.isEmpty()) {
String input = StdIn.readString();
System.out.println(cipher.encrypt(input));
}
}
}
Marc hat einen Großteil des Bodens abgedeckt, aber ich möchte auf einige Dinge hinweisen, die er nicht ausdrücklich erwähnt hat, und einige weitere Kommentare hinzufügen.
- "öffentliche statische Leerenverschlüsselung (String s, String t)". Beachten Sie, wie Marc die undurchsichtigen Namen "s" und "t" durch aussagekräftigere ersetzt hat. Im Allgemeinen sind Kurznamen nicht unsere Freunde. Marc's Verwendung von "s" als Argumentname in seiner encrypt () -Methode ist meiner Meinung nach in diesem Zusammenhang OK, da die Methode so kurz ist, aber im Allgemeinen längere, ausdrucksstärkere Namen bevorzugt.
- "String.valueOf (word.charAt (i)). Gleich (String.valueOf (s.charAt (j)))" String.charAt (int) liefert einen char - Wert, der tatsächlich eine (relativ) kleine Ganzzahl. Sie müssen nicht zwei Zeichen in Strings einschließen und String.equals () verwenden, um sie zu vergleichen. Sie können einfach "word.charAt (i) == s.charAt (j)" sagen.
- Weder Ihre Lösung noch Marc's überprüfen tatsächlich, ob die beiden Schlüsselringe keine Zeichen gemeinsam haben oder Duplikate enthalten.
- Die Problemspezifikation legt nahe, dass es sich um einen Fehler handelt, wenn das zu verschlüsselnde Wort ein Zeichen enthält, das nicht in den Schlüsselringen enthalten ist. Weder Ihre Lösung noch Marc's behandeln sie als solche.
Als Alternative zu Marc's Lösung werde ich anstelle von Marc's Map eine alternative Suchstrategie skizzieren. (Ich werde es nicht codieren - es wäre eine nützlichere Übung für Sie, dies zu tun.)
Wenn Sie ein Array von Zeichen der Größe Character.MAX_VALUE erstellen, können Sie es mit Ersatzzeichen füllen und einfach mit Eingabezeichen als Index darauf zugreifen. Nicht zugewiesene Einträge im Array (für Zeichen, die nicht in den Schlüsselzeichenfolgen enthalten sind) werden mit dem Nullzeichen ( gemäß der Sprachspezifikation ) initialisiert .
[Hinweis: Ich habe Ersatzcodeeinheiten unter der Annahme ignoriert, dass die OP-Eingabe sie nicht einbezieht ...]