Algorytmy na tekstach

Algorytmy na tekstach to zestaw technik i metod przetwarzania danych tekstowych, które mają szerokie zastosowanie w informatyce, lingwistyce komputerowej i kryptografii. Oto kluczowe obszary zastosowania i algorytmów:

1. Wyszukiwanie wzorców w tekście

Polega na znalezieniu wystąpień określonego wzorca w danym tekście. Przykładowe algorytmy:

  • Metoda naiwna: Przesuwa wzorzec wzdłuż tekstu i porównuje go z każdym fragmentem.
  • Algorytm Knutha-Morrisa-Pratta (KMP): Używa prefiksów wzorca do optymalizacji wyszukiwania.
  • Algorytm Boyera-Moore’a: Porównuje wzorzec od końca i efektywnie pomija niepasujące fragmenty.
2. Szyfrowanie tekstów

Stosowane w celu ochrony informacji poprzez przekształcanie tekstu w formę niezrozumiałą dla osób niepowołanych. Rodzaje:

  • Szyfrowanie podstawieniowe: Każda litera jest zamieniana na inną, np. szyfr Cezara.
  • Szyfrowanie przestawieniowe: Zmienia kolejność liter w tekście, tworząc anagramy.
  • Szyfrowanie symetryczne: Jeden klucz służy do szyfrowania i deszyfrowania (np. AES).
  • Szyfrowanie asymetryczne: Używa pary kluczy (publicznego i prywatnego), np. algorytm RSA.
3. Analiza tekstów

Obejmuje algorytmy przetwarzania języka naturalnego, wyszukiwania informacji i kompresji danych tekstowych.

Algorytmy na tekstach mają kluczowe znaczenie w aplikacjach takich jak wyszukiwarki, systemy szyfrowania danych, edytory tekstowe oraz systemy wykrywania plagiatów.

1. Wyszukiwanie wzorca w tekście metodą naiwną

Metoda naiwna jest jednym z najprostszych sposobów wyszukiwania wzorca w tekście. Polega na przesuwaniu wzorca wzdłuż tekstu i porównywaniu go z kolejnymi fragmentami.

Opis algorytmu:

  1. Przesuń wzorzec o jedną pozycję wzdłuż tekstu, zaczynając od początku.
  2. Na każdym etapie porównaj wzorzec z odpowiadającym mu fragmentem tekstu.
  3. Jeśli wzorzec pasuje do fragmentu, zapisz pozycję dopasowania.
  4. Powtarzaj aż do końca tekstu.

Przykład:

  • Tekst: „abcabcabc”
  • Wzorzec: „abc”
  • Wynik: Dopasowania na pozycjach 0, 3, 6.

Zalety i wady:

  • Zalety: Prosty do implementacji.
  • Wady: Wolny przy długich tekstach i wzorcach.

2. Szyfrowanie tekstu metodą podstawieniową

W jakim celu stosujemy szyfry?

Szyfrowanie jest kluczowym elementem ochrony danych w cyfrowym świecie. Jego głównym celem jest zapewnienie:

  • Poufności: Dane są dostępne tylko dla uprawnionych użytkowników.
  • Integralności: Dane nie zostały zmienione w trakcie przesyłania.
  • Autentyczności: Odbiorca może potwierdzić tożsamość nadawcy.

Podstawowe pojęcia dotyczące szyfrowania:

  • Tekst jawny (ang. plaintext): Dane przed szyfrowaniem.
  • Tekst zaszyfrowany (ang. ciphertext): Dane po zaszyfrowaniu.
  • Klucz: Sekretna informacja używana do szyfrowania i deszyfrowania.
  • Algorytm szyfrowania: Zestaw reguł matematycznych używanych do przekształcania danych.

Szyfr Cezara

Jest to jeden z najprostszych szyfrów podstawieniowych. Jego działanie polega na przesunięciu każdej litery w alfabecie o określoną liczbę miejsc.

Schemat działania:

  1. Przypisz każdej literze jej numer w alfabecie (A=0, B=1, …, Z=25).
  2. Zaszyfruj każdą literę, przesuwając ją o określony klucz kkk:
    Zaszyfrowana litera = (Pozycja+k) mod  26 \ text {Zaszyfrowana litera} = (\text{Pozycja} + k) \mod 26 Zaszyfrowana litera = (Pozycja+k) mod26.
  3. Odzyskaj tekst jawny, stosując przesunięcie wstecz.

Przykład:

  • Tekst jawny: HELLO
  • Klucz: 3
  • Tekst zaszyfrowany: KHOOR

Analiza bezpieczeństwa:

  • Łatwo go złamać, stosując brutalną siłę (sprawdzenie 25 przesunięć).
  • Współcześnie używany jedynie w celach dydaktycznych.

3. Szyfrowanie tekstu metodą przestawieniową

W szyfrowaniu przestawieniowym kolejność znaków w tekście jest zmieniana zgodnie z określonym kluczem.

Miniszyfrowanie – tworzenie anagramów

Jednym z przykładów szyfrowania przestawieniowego jest zamiana kolejności liter w słowach w sposób losowy, np. z KOT na TOK. Takie podejście jest stosunkowo łatwe do złamania, ale może być używane w prostych grach i zabawach językowych.

Szyfrowanie symetryczne i asymetryczne

  1. Symetryczne:
    W tym typie szyfrowania ten sam klucz jest używany do szyfrowania i deszyfrowania danych. Przykłady: DES, AES.
    Zalety: Szybkość działania.
    Wady: Problem z bezpiecznym przekazywaniem klucza.
  2. Asymetryczne:
    Opiera się na dwóch kluczach – publicznym i prywatnym. Publiczny służy do szyfrowania, a prywatny do deszyfrowania. Przykłady: RSA, ElGamal.
    Zalety: Brak konieczności wymiany klucza prywatnego.
    Wady: Większe zapotrzebowanie na zasoby obliczeniowe.

Algorytm RSA

RSA to jeden z najbardziej znanych algorytmów szyfrowania asymetrycznego. Jego bezpieczeństwo opiera się na trudności faktoryzacji dużych liczb.

Proces szyfrowania:

  1. Wygeneruj dwie liczby pierwsze ppp i qqq.
  2. Oblicz n=p⋅qn = p \cdot qn=p⋅q oraz ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)ϕ(n)=(p−1)(q−1).
  3. Wybierz liczbę eee, taką że gcd⁡(e,ϕ(n))=1\gcd(e, \phi(n)) = 1gcd(e,ϕ(n))=1.
  4. Oblicz klucz prywatny ddd, taki że e⋅d≡1(modϕ(n))e \cdot d \equiv 1 \pmod{\phi(n)}e⋅d≡1(modϕ(n)).
  5. Szyfruj wiadomość MMM: C=Memod  nC = M^e \mod nC=Memodn.
  6. Deszyfruj wiadomość CCC: M=Cdmod  nM = C^d \mod nM=Cdmodn.

RSA jest szeroko stosowany w protokołach bezpieczeństwa takich jak HTTPS.