Podstawy algorytmów tekstowych

25.11.2009 - Damian Rusak
Trudność

Aby przyswoić zasady działania algorytmów tekstowych trzeba znać podstawowe zagadnienia i definicje z tej dziedziny. Może się wydawać, że nie ma nic bardziej intuicyjnego od posługiwania się tekstem i językiem, jednak to co te pojęcia oznaczają z informatycznego punktu widzenia może być początkowo zaskakujące. Poniższy artykuł ma na celu prezentację (mam nadzieję, w miarę ciekawy sposób) terminologii, której znajomość pozwala nauczyć się wielu fascynujących algorytmów tekstowych.

Zacznijmy może od strony "technicznej" - jak matematycznie i dokładnie sformułować to, czym chcemy się zajmować? Każdy tekst składa się z pewnych symboli - nasz korzysta z liter, cyfr, znaków przestankowych i wielu innych. Nie ma większego sensu ograniczać się w tej kwestii - przyjmijmy, że symbole mogą być dowolne.

Zbiór symboli, z którego będziemy korzystać nazwiemy alfabetem - oznacza się go zwyczajowo jako $ \Sigma $. Możemy na przykład korzystać z alfabetu:

$ \Sigma = \left\{a,b,c,\dots, z\right\} $

ale równie dobrze alfabetem może być zbiór $ \Sigma = \left\{1,e,\alpha,\dots \right\} $. Pełna dowolność. Albo taki alfabet jak poniżej:

Każdy symbol jest jednakowo dobry - to tylko pewien obiekt, któremu można nadać matematyczne znaczenie. Oczywiście, skoro mamy dowolność, najwygodniej będzie korzystać z liter alfabetu angielskiego - i z taką konwencją będziemy się najczęściej spotykać w zadaniach informatycznych.

Teraz jak alfabet wykorzystać? Otóż z symboli będziemy tworzyć słowa. Słowo to po prostu skończony ciąg symboli z alfabetu. Z alfabetu $ \Sigma = \left\{1,e,\alpha,\dots \right\} $ możemy utworzyć słowa $ 1111 $, $ e\alpha $, $ e1e1\alpha $ i nieskończenie wiele innych - chociażby każde słowo składające się tylko z symbolu $ 1 $.

Czy słowo może nie składać się z żadnego symbolu? Owszem, z wielu powodów przyjmujemy, że zawsze mamy słowo puste - odpowiednik zera w liczbach naturalnych czy zbioru pustego. Słowo puste zwyczajowo oznaczamy grecką literą epsilon - $ \epsilon $. Do czego nam to przydatne? Przekonamy się wkrótce, że dobrze mieć takie "nic" pod ręką.

Widzimy, że słów można stworzyć bardzo wiele - jest też matematyczne pojęcie na zbiór słów - to język. Oczywiście musimy porzucić intuicje z "rzeczywistego" świata - słowa nie muszą mieć żadnego sensu w języku polskim, ani w żadnym innym "ludzkim" języku. Język zatem to pewien zbiór słów, spośród wszystkich, jakie tylko możemy stworzyć. Rysunek poniżej pokazuje nam przykład alfabetu i nieskończonego języka nad nim, który zawiera wszystkie słowa możliwe do utworzenia - taki język oznaczamy jako $ \Sigma^{*} $.

 

Właśnie - napisałem, że język jest nad alfabetem, a na rysunku znajduje się poniżej... To po prostu konwencja matematyczna - mówimy, że język jest nad alfabetem, gdy wszystkie słowa z tego języka są stworzone za pomocą symboli alfabetu. Wiemy już, jak oznaczyć język zawierający wszystkie możliwe słowa, możemy więc wprowadzić formalną definicję języka:

$ L $ jest językiem nad alfabetem $ \Sigma $ wtedy i tylko wtedy, gdy $ L \subseteq \Sigma^{*} $.

Innymi słowy, jeśli $ L $ jest podzbiorem zbioru wszystkich możliwych słów nad pewnym alfabetem, to jest też zbiorem słów nad tym alfabetem - a to nasza definicja języka. Dla alfabetu $ \Sigma = \left\{a,b,c\right\} $ językami są na przykład $ \left\{\epsilon, a, ab, aabb, cba\right\} $, $ \left\{\epsilon, a, b, c\right\} $, $ \left\{c, ccc, ccccc, \dots \right\} $.

Możemy mówić też o języku pustym - $ L = \emptyset $. Zauważ, że język $ L_{1} = \left\{\epsilon\right\} $ to nie to samo. $ L_{1} $ to język zawierający słowo puste, a $ L $ nie zawiera żadnego słowa.

Najwyższy czas by formalizm zaatakował też pojęcie słowa. Na oznaczenie słów najczęściej będziemy używać liter $ v,w,u,x,y,z $. Wiemy teraz, że:

$ v $ jest słowem nad alfabetem $ \Sigma $ jeśli $ v \in \Sigma^{*} $.

 

Dla wygody i szybkiego dostępu do symboli składających się na słowo wprowadźmy sobie indeksy kolejnych "liter" słowa:

jeśli $ v=a_{0}a_{1}a_{2}\dots a_{n} $  to $ v_{0} = a_{0}, v_{1} = a_{1} , \dots v_{n} = a_{n} $.

Np. jeśli $ v = abbcabcba $ to $ v_{0} = a , v_{1} = b, v_{2} = b, v_{3} = c , \dots , v_{8} = a $.

Zauważ, że numerujemy symbole słowa począwszy od zera - to przyjęta w informatyce konwencja indeksowania. Może się to kojarzyć np. z indeksowaniem tablic w wielu językach programowania - istotnie, często napisy są reprezentowane przez tablice znaków.

Nietrudno będzie zdefiniować długość słowa - to po prostu ilość symboli, z których się składa. Oznacza się to tak, jak wartość bezwględną liczby albo długość odcinka. Będziemy pisali:

Długość słowa $ v $ - $ \left|v\right| = n \leftrightarrow v = a_{0}a_{1}\dots a_{n-1} $

4.2
Twoja ocena: Brak Ocena: 4.2 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com