ED-4.2-m06-1.0-Slajd27

From Studia Informatyczne

Problem (1)

Problem (1)


Zasadniczy problem związany z konstrukcją algorytmów odkrywania wzorców sekwencji w obecności ograniczeń czasowych wiąże się z problemem własności monotoniczności miary wsparca. Własność monotoniczności miary wsparcia, w kontekście definicji zawierania się sekwencji w obecności ograniczeń czasowych, musi być zdefiniowana w nieco inny sposób. Wynika to z następującego spostrzeżenia. W przypadku braku ograniczenia {max-gap}, można łatwo pokazać, że dowolna sekwencja X, zawierająca sekwencję S, zawiera również wszystkie podsekwencje Y sekwencji S; Y całkowicie zawiera się w S. W przypadku obecności ograniczenia czasowego {max-gap}, powyższe stwierdzenie nie jest prawdziwe.

Przykładowo:

Zakładamy, że maksymalna odstęp max-gap będzie równy 3. Dana jest sekwencja X = <(1 2): 1, (3 4): 3, (5 6): 5, (7 8): 7>.

X zawiera sekwencję S = <(1 2): 1, (3 4): 3, (5 6): 5>, ale X nie zawiera sekwencji Y = <(1 2): 1, (5 6): 5>, która jest podsekwencją sekwencji S.

Odległość pomiędzy dwoma wyrazami przekracza maksymalny odstęp.


<< Poprzedni slajd | Spis treści | Następny slajd >>