Implémentation du chiffrement Kamasutra
C'est l'exercice 3.1.31. extrait du livre Computer Science An Interdisciplinary Approach de Sedgewick & Wayne:
Ecrivez un filtre KamasutraCipher qui prend deux chaînes comme argument de ligne de commande (les chaînes de clé), puis lit les chaînes (séparées par des espaces) à partir de l'entrée standard, remplace chaque lettre comme spécifié par les chaînes de clé et imprime le résultat sur la sortie standard. Cette opération est à la base de l'un des premiers systèmes cryptographiques connus. La condition sur les chaînes de clé est qu'elles doivent être de longueur égale et que toute lettre en entrée standard doit apparaître dans exactement l'une d'entre elles. Par exemple, si les deux clés sont THEQUICKBROWN et FXJMPSVLAZYDG, alors nous faisons la table
THEQUICKBROWN
FXJMPSVLAZYDG
ce qui nous dit que nous devrions remplacer F pour T, T pour F, H pour X, X pour H, etc. lors du filtrage de l'entrée standard vers la sortie standard. Le message est encodé en remplaçant chaque lettre par sa paire. Par exemple, le message MEET AT ELEVEN est codé comme QJJF BF JKJCJG. La personne qui reçoit le message peut utiliser les mêmes touches pour récupérer le message.
Voici mon programme:
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 est une API simple écrite par les auteurs du livre. J'ai vérifié mon programme et cela fonctionne.
Est-il possible d'améliorer mon programme?
Merci de votre attention.
Réponses
La mise en œuvre semble bonne, j'ai juste quelques suggestions.
Principe de responsabilité unique
La méthode encryptsemble avoir beaucoup de responsabilités:
- Lit l'entrée de l'utilisateur
- Crypte l'entrée
- Envoie le résultat sur la console
Une définition de SRP est "Une classe ne devrait avoir qu'une seule raison de changer". Mais il y a de nombreuses raisons KamasutraCipherde changer:
- L'entrée peut provenir d'un
System.infichier, d'une base de données, etc. - La bibliothèque
StdInchange. - La sortie doit aller dans un fichier, etc.
- La sortie doit être bien formatée pour l'utilisateur
- etc..
La seule responsabilité de KamasutraCipherdevrait être de crypter (ou décrypter) une chaîne et de renvoyer le résultat.
L'interface peut être refactorisée à partir de ceci:
public class KamasutraCipher {
public static void encrypt(String s, String t)
}
À:
public class KamasutraCipher {
public KamasutraCipher(String key1, String key2)
public String encrypt(String s)
}
Maintenant, la seule raison KamasutraCipherde changer est pour les optimisations ou si l'algorithme Kamasutra change, mais ce dernier ne se produira pas de sitôt.
Toute la logique pour demander l'entrée et produire la sortie est poussée vers le main.
Les cordes sont immuables
En Java, les chaînes sont des objets immuables et toute modification apportée à une chaîne crée une nouvelle chaîne. Par conséquent cette partie:
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
Peut être changé en:
word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);
Optimisation
La complexité de la méthode encryptest O(m*n)où mest la longueur de la chaîne d'entrée et nla longueur de la clé. (en ignorant les méthodes de Stringet la boucle while).
Un moyen plus efficace serait d'utiliser une carte pour stocker les clés de chaîne. Par exemple, étant donné les clés de chaîne ABC et FGH , la carte contiendrait:
- A -> F
- B -> G
- C -> H
- F -> A
- G -> B
- H -> C
La méthode encryptdevient alors une simple recherche sur la carte, réduisant la complexité à 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();
}
SpringBuildernous permet d'économiser de la mémoire en créant la chaîne de résultat plus efficacement. keyMapest créé dans le constructeur car les clés ne changent pas après l'initialisation.
Validation d'entrée
toute lettre en entrée standard doit apparaître dans exactement l'une d'elles (touches)
Comme mentionné par d'autres, c'est une exigence qui doit être gérée, éventuellement dans la méthode encrypt.
Pour les exceptions, vous pouvez utiliser à la IllegalArgumentExceptionplace de RuntimeException.
Code refactorisé
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 a couvert une grande partie du terrain, mais j'aimerais souligner quelques points qu'il n'a pas explicitement mentionnés et ajouter quelques commentaires supplémentaires.
- "public static void encrypt (String s, String t)". Remarquez comment Marc a remplacé les noms opaques «s» et «t» par des noms plus significatifs. En général, les noms courts ne sont pas nos amis. L'utilisation par Marc de "s" comme nom d'argument dans sa méthode encrypt () est, à mon humble avis, OK dans ce contexte car la méthode est si courte, mais en général préfère des noms plus longs et plus expressifs.
- "String.valueOf (word.charAt (i)). Equals (String.valueOf (s.charAt (j)))" String.charAt (int) renvoie une valeur char , qui est en fait un entier (assez) petit. Vous n'avez pas besoin d'encapsuler deux caractères dans Strings et d'utiliser String.equals () pour les comparer. Vous pouvez simplement dire "word.charAt (i) == s.charAt (j)".
- Ni votre solution ni celle de Marc ne vérifient réellement que les deux chaînes de clés ne partagent aucun caractère, ni ne contiennent des doublons.
- La spécification du problème suggère que si le mot à chiffrer contient un caractère qui ne figure pas dans les chaînes de clés, c'est une erreur. Ni votre solution ni celle de Marc ne la traite comme telle.
Au lieu de la solution de Marc, je décrirai une stratégie de recherche alternative à la place de Marc's Map. (Je ne vais pas le coder - ce serait un exercice plus utile pour vous de le faire.)
Si vous créez un tableau de caractères de taille Character.MAX_VALUE, vous pouvez le remplir avec des caractères de substitution et y accéder simplement en utilisant des caractères d'entrée comme index. Les entrées non attribuées dans le tableau (pour les caractères non fournis dans les chaînes de clé) seront initialisées au caractère nul ( conformément à la spécification de la langue ).
[Remarque: j'ai ignoré les unités de code de substitution en supposant que l'entrée des OP ne les impliquera pas ...]