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

©2021 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++, 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 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 ł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 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.

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
©2021 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.