Pojęcia podstawowe przy przetwarzaniu tekstów


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie

 

W algorytmach tekstowych będziemy stosowali następujące ustalenia i oznaczenia:

 

Alfabetem (ang. alphabet) będziemy nazywali skończony zbiór symboli (ang. the set of symbols) – zwykle alfabet jest zbiorem liter, znaków, cyfr, jednakże w przypadku uogólnionym może to być dowolny zbiór obiektów, które można w jakiś sposób sklasyfikować.

 

Skończone ciągi symboli alfabetu nazwiemy łańcuchami (ang. strings). Czasami w tym znaczeniu używa się terminów słowa (ang. words) lub teksty (ang. texts).

 

Przez pusty łańcuch (ang. empty string) rozumiemy łańcuch nie zawierający ani jednego znaku.

 

s[i] – oznacza i-ty znak łańcucha s. Umówmy się, iż indeksy w łańcuchach rozpoczynają się od 0. W języku Pascal oraz Basic indeksy startują od wartości 1. Należy to uwzględniać w programach. My wybieramy wartość 0, robiąc ukłon w stronę języka C++, który jest o wiele bardziej popularny niż Pascal i Basic.

 

|s| – oznacza długość łańcucha (ang. string length), czyli liczbę przechowywanych w nim aktualnie znaków. Łańcuch pusty ma długość 0.

 

s[i : j] – oznacza fragment łańcucha (ang substring) zawierający kolejne znaki s[i] s[i + 1] s[i + 2] ... s[j - 1]. Znak s[j] nie należy do tej sekwencji. Na przykład, jeśli s = "ALA MA BOCIANA", to s[4 : 9] = "MA BO". Taki fragment łańcucha s będziemy nazywali oknem (ang. string window).

 

Długość podłańcucha wyliczamy ze wzoru:

 

s[i : j] | = j - i

 

Podłańcuch s[i : i] jest łańcuchem pustym – posiada długość 0, co wynika bezpośrednio z podanego powyżej wzoru.

 

s = t – równość dwóch łańcuchów oznacza, iż są one tej samej długości oraz posiadają identyczne znaki na tych samych pozycjach.

 

s[i : i + | t | ] = t – oznacza to, iż fragment łańcucha s od pozycji i-tej do i + |t| - 1 zawiera dokładnie te same znaki, co łańcuch t. Na przykład, jeśli s = "ALA MA BOCIANA" i t = "MA", to zachodzi s[4 : 6] = t (zwróć uwagę, iż znak s[6] nie jest częścią podłańcucha s[4...6]).

 

Prefiks (ang. prefix) łańcucha s jest łańcuchem zbudowanym z k początkowych znaków:

 

Pref(s) = s[0 : k]

 

Sufiks (ang. suffix) łańcucha s jest łańcuchem zbudowanym z k końcowych znaków:

 

Suff(s) = s[n - k : n]

 

s[0 : n]
Pref(s)  
s[0 : k]
s[0 : n]
  Suff(s)
  s[n-k : n]

 

Prefiks i sufiks mogą być puste, tzn. mogą nie zawierać żadnego znaku.

 

Mówimy, że prefiks lub sufiks jest właściwy (ang. proper), jeśli nie obejmuje całego łańcucha s.

 

Maksymalny prefiks właściwy (ang. maximal proper prefix) obejmuje wszystkie znaki łańcucha s za wyjątkiem ostatniego. Podobnie maksymalny sufiks właściwy (ang. maximal proper sufix) obejmuje wszystkie znaki łańcucha za wyjątkiem pierwszego:

 

max Pref(s) = s[0 : |s| - 1]

max Suff(s) = s[1 : |s| ]

 

Jeśli istnieje prefiks s, który jest równy sufiksowi s, to mówimy, iż tworzą one tzw. prefikso-sufiks (ang. border):

 

s
Pref(s)   Suff(s)
Pref(s) = Suff(s) = Border(s)

 

Uwaga: prefiks i sufiks w powyższym układzie mogą się wzajemnie częściowo pokrywać (a nie sugeruje tego rysunek). Na przykład maksymalny prefikso-sufiks dla tekstu:

 

ababab

 

to

 

ababab

ababab

 

Dwie środkowe litery ab pokrywają się w prefiksie i sufiksie. Przez maksymalny prefikso-sufiks łańcucha s rozumiemy najdłuższy, właściwy prefiks i sufiks s, które są sobie równe.

 

Jeśli dany łańcuch s posiada prefikso-sufiks o długości k, to okresem (ang. period) nazywamy taką liczbę całkowitą d, że zachodzi warunek:

 

s[0 : k] = s[d : n]

 

Graficznie wygląda to tak:

 

   
Border(s)           s           Border(s)
d
Border(s)           s           Border(s)
 

 

Okres można bardzo prosto obliczyć wg wzoru:

 

 d = |s| - | Border(s) |  

 

Maksymalny prefikso-sufiks łańcucha s oznacza najdłuższy prefiks i sufiks tego łańcucha, które są sobie równe.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.