ED-4.2-m03-1.0-Slajd34
Przykład 3 (3)
Kolejnym krokiem algorytmu jest transformacja bazy danych D do FP- drzewa. Konstrukcja FP- drzewa rozpoczyna się od utworzenia korzenia drzewa i przypisania mu etykiety null. Odczyt pierwszej transakcji {T_1} z bazy danych D prowadzi do utworzenia ścieżki drzewa: (orzeszki:1) (coca_cola:1) Liczba całkowita występująca po znaku : określa aktualną wartość licznika, związanego z każdym wierzchołkiem, reprezentującego liczbę transakcji wspierających dany element (zbiór częsty 1-elementowy). Transformacja transakcji T2 jest realizowana następująco. Transakcja {T_2} posiada wspólny prefiks (orzeszki) z transakcją T1, stąd, zwiększamy wartość licznika transakcji pierwszego wierzchołka o 1, i tworzymy nową ścieżkę od wierzchołka (orzeszki) zawierającą dwa nowe wierzchołki: (piwo:1) (pieluszki:1). Dla transakcji T3 tworzymy nowy wierzchołek (coca_cola:1), który łączymy z korzeniem drzewa - transakcja T3 nie posiada wspólnego prefiksu z przetransformowanymi transakcjami T1 i T2. Kolejna transakcja T4 posiada wspólny prefiks (orzeszki, piwo) z transakcją T2. Stąd, zwiększamy wartość licznika transakcji każdego z wierzchołków należących do ścieżki reprezentującej wspólny prefiks o 1, (orzeszki:3) (piwo:2), i tworzymy nowy wierzchołek (coca_cola:1), który łączymy łukiem z wierzchołkiem (piwo:2). Ostatnia transakcja {T_5} jest transformowana do istniejącej już ścieżki (orzeszki:3) (piwo:2) (pieluszki:1), stąd, zwiększamy wartość licznika transakcji każdego z wierzchołków należących do tej ścieżki o 1. Ostatecznie, w wyniku transformacji bazy danych D, otrzymujemy FP- drzewo przedstawione na powyższym slajdzie.
