Implementacja szyfru Kamasutra

Question

To jest ćwiczenie 3.1.31. z książki Computer Science An Interdisciplinary Approach autorstwa Sedgewick & Wayne:

Napisz filtr KamasutraCipher, który pobiera dwa ciągi jako argument wiersza poleceń (ciągi kluczy), a następnie odczytuje ciągi (oddzielone spacjami) ze standardowego wejścia, zastępuje każdą literę zgodnie z ciągami kluczy i wypisuje wynik na standardowe wyjście. Ta operacja jest podstawą jednego z najwcześniejszych znanych systemów kryptograficznych. Warunek dotyczący ciągów kluczy jest taki, że muszą one mieć równą długość i każda litera ze standardowego wejścia musi występować dokładnie w jednym z nich. Na przykład, jeśli dwa klawisze to THEQUICKBROWN i FXJMPSVLAZYDG, wtedy tworzymy tabelę

THEQUICKBROWN

FXJMPSVLAZYDG

co mówi nam, że powinniśmy podstawić F za T, T za F, H za X, X za H itd., filtrując standardowe wejście na standardowe wyjście. Wiadomość jest kodowana przez zastąpienie każdej litery jej parą. Na przykład wiadomość MEET AT ELEVEN jest zakodowana jako QJJF BF JKJCJG. Osoba otrzymująca wiadomość może użyć tych samych klawiszy, aby ją odzyskać.

Oto mój program:

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 to proste API napisane przez autorów książki. Sprawdziłem mój program i działa.

Czy jest jakiś sposób na ulepszenie mojego programu?

Dziękuję za uwagę.

Answer 1

Wdrożenie wygląda dobrze, mam tylko kilka sugestii.

Zasada pojedynczej odpowiedzialności

Metoda encryptwydaje się mieć dużą odpowiedzialność:

1. Odczytuje dane wejściowe od użytkownika
2. Szyfruje dane wejściowe
3. Wyprowadza wynik do konsoli

Jedna z definicji SRP brzmi: „Klasa powinna mieć tylko jeden powód do zmiany”. Ale jest wiele powodów KamasutraCipherdo zmiany:

1. Dane wejściowe mogą pochodzić z System.inpliku, bazy danych itp.
2. Biblioteka się StdInzmienia.
3. Dane wyjściowe muszą przejść do pliku itp.
4. Wynik musi być dobrze sformatowany dla użytkownika
5. itp..

Jedynym obowiązkiem KamasutraCipherpowinno być zaszyfrowanie (lub odszyfrowanie) ciągu i zwrócenie wyniku.

Interfejs można zreformować z tego:

public class KamasutraCipher {
    public static void encrypt(String s, String t)
}

Do:

public class KamasutraCipher {
    public KamasutraCipher(String key1, String key2)
    public String encrypt(String s)
}

Jedynym powodem KamasutraCipherdo zmiany są optymalizacje lub zmiana algorytmu Kamasutry, ale to drugie nie nastąpi wkrótce.

Cała logika żądania danych wejściowych i generowania danych wyjściowych jest umieszczana w pliku main.

Ciągi znaków są niezmienne

W Javie ciągi znaków są niezmiennymi obiektami, a każda modyfikacja ciągu tworzy nowy ciąg. Dlatego ta część:

String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);

Można zmienić na:

word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);

Optymalizacja

Złożoność metody encryptpolega na tym, że O(m*n)gdzie mjest długością ciągu wejściowego i njest długością klucza. (ignorując metody Stringpętli i while).

Bardziej wydajnym sposobem byłoby użycie mapy do przechowywania kluczy ciągów. Na przykład, biorąc pod uwagę klawisze ciągów ABC i FGH , mapa zawierałaby:

• A -> F.
• B -> G.
• C -> H.
• F -> A
• G -> B
• H -> C

Metoda encryptstaje się wówczas prostym wyszukiwaniem na mapie, zmniejszając złożoność do 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();
}

SpringBuilderpozwala nam zaoszczędzić trochę pamięci, wydajniej tworząc ciąg wynikowy. keyMapjest tworzony w konstruktorze, ponieważ klucze nie zmieniają się po inicjalizacji.

Walidacja danych wejściowych

każda litera w standardowym wejściu musi pojawić się dokładnie w jednym z nich (klawiszach)

Jak wspominali inni, jest to wymaganie, które należy spełnić, prawdopodobnie w metodzie encrypt.

W przypadku wyjątków możesz użyć IllegalArgumentExceptionzamiast RuntimeException.

Refaktoryzowany kod

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));
        }
    }
}

Answer 2

Marc poruszył wiele kwestii, ale chciałbym zwrócić uwagę na kilka rzeczy, o których nie wspomniał wprost, i dodać kilka dalszych komentarzy.

• „public static void encrypt (String s, String t)”. Zwróć uwagę, jak Marc zastąpił nieprzejrzyste nazwy „s” i „t” bardziej znaczącymi. Ogólnie krótkie imiona nie są naszymi przyjaciółmi. Użycie przez Marca "s" jako nazwy argumentu w jego metodzie encrypt () jest, IMHO, OK w tym kontekście, ponieważ metoda jest tak krótka, ale generalnie preferuje dłuższe, bardziej wyraziste nazwy.
• „String.valueOf (word.charAt (i)). Equals (String.valueOf (s.charAt (j)))” String.charAt (int) zwraca wartość typu char , która w rzeczywistości jest (dość) małą liczbą całkowitą. Nie musisz zawijać dwóch znaków w Strings i używać String.equals (), aby je porównać. Możesz po prostu powiedzieć „word.charAt (i) == s.charAt (j)”.
• Ani twoje rozwiązanie, ani Marc faktycznie nie sprawdzają, czy dwa zestawy kluczy nie mają wspólnych znaków ani nie zawierają duplikatów.
• Ze specyfikacji problemu wynika, że ​​jeśli zaszyfrowane słowo zawiera znak, którego nie ma w pęku kluczy, jest to błąd. Ani twoje rozwiązanie, ani Marc nie traktują tego jako takiego.

Jako alternatywę dla rozwiązania Marca, przedstawię alternatywną strategię wyszukiwania zamiast mapy Marca. (Nie zamierzam tego kodować - byłoby to dla ciebie bardziej przydatne ćwiczenie).

Jeśli utworzysz tablicę znaków o rozmiarze Character.MAX_VALUE, możesz wypełnić ją znakami zastępczymi i po prostu uzyskać do niej dostęp, używając znaków wejściowych jako indeksu. Nieprzypisane wpisy w tablicy (dla znaków niedostarczonych w ciągach kluczy) zostaną zainicjowane znakiem pustym ( zgodnie ze specyfikacją języka ).

[Uwaga: zignorowałem zastępcze jednostki kodu, zakładając, że dane wejściowe PO nie będą ich obejmować ...]