ED-4.2-m06-1.0-Slajd15
Kompletność algorytmu PrefixSpan
Zauważmy, że podstawowa idea algorytmu o której już wspominaliśmy polega na zastąpieniu etapu sekwencjonowania, który występuje w algorytmie GSP i który polega na generowaniu sekwencji kandydujących. Następnie sprawdzaniu czy dana sekwencja kandydująca spełnia warunki minimalnego wsparcia. Etapem czy sekwencją etapów polegających na budowie i analizie prefiksów sekwencji należących do bazy danych sekwencji. To znaczy w kolejnych krokach generujemy czy konstruujemy wzorce sekwencji. W pierwszym kroku algorytmu generujemy wzorce sekwencji o długości 1 i rozmiarze 1. W kolejnych krokach generujemy wzorce sekwencji o rozmiarze 2 i długości 1 lub wzorce sekwencji o długości 2. W kolejnych krokach konstruujemy wzorce sekwencji. W konsekwencji algorytm PrefixSpan generuje wszystkie możliwe wzorce sekwencji, które zawierają się w bazie danych sekwencji, a zatem algorytm PrefixSpan jest kompletny.
