Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące przetwarzania tekstów

SPIS TREŚCI

Definicje

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

Alfabetem (ang. alphabet) będziemy nazywali skończony zbiór symboli (ang. 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++ (oraz Python), który jest obecnie 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 tego ciągu. Na przykład, jeśli s = "ALA MA KOTA", to s[4:9] = "MA KO". Taki fragment łańcucha s będziemy nazywali oknem łańcucha (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 KOTA" 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.


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.