img136

136

10. Metody ciągowe

W kolejnych podrozdziałach przedstawimy te metody, prezentując: mechanizm generujący - gramatykę 0, za pomocą której możemy zapamiętać w dynamiczny sposób wzorce x^k ciągu uczącego U, oraz procedurę analizującą i rozpoznającą - automat 21 odpowiedniej klasy. Prezentację zilustrujemy przykładami rozpoznawania kilku zaledwie wzorców x^k klas D\ gdyż wprowadzenie kilkudziesięciu (kilkuset, kilku tysięcy) wzorców (z takimi licznościami mamy do czynienia w praktyce) tylko dla ilustracji nie byłoby sensowne. Z drugiej jednak strony użycie kilku zaledwie wzorców nie pozwoli Czytelnikowi naocznie przekonać się, że użycie dynamicznej formuły generacji ciągu uczącego U - gramatyki 0 jest znacznie mniej pa-mięciochłonne niż pamiętanie ciągu uczącego explicite, w przypadku gdy jest on bardzo liczny^).

10.2. Kody łańcuchowe Freemana

Metodę opartą na kodach łańcuchowych Freemana przedstawimy na przykładzie wzorców czterech drukowanych liter: I, P, R, D. Składowe pierwotne kodu Freemana przedstawiono na rysunku 10.la, a reprezentacje rozważanych liter zbudowane na bazie kodu - na rysunku 10.Ib. Jak zatem widać, kolejne litery możemy zapisać za pomocą następujących ciągów (startując z punktu zaznaczonego kropką i zaznaczając przez $ - koniec ciągu).

I - 0000$,

P - 000023456$,

R - 00002345633$,

D - 00002344456$.

Prawostronnie regularną gramatykę 0_r generującą te ciągi-reprezentacje, zdefiniujemy w następujący sposób: gdzie zbiór omówimy z podziałem na grupy:

(^!) Pojęcia z teorii języków formalnych i automatów używane w niniejszym rozdziale zostały formalnie zdefiniowane w Dodatku 3.