Metoda List Prostych – modyfikacje

Wprowadzając modyfikacje do Metody List Prostych możemy przyczynić się do zwiększenia szybkości przetwarzania informacji w niektórych przypadkach. Modyfikacje jednak mogą także przyczynić się do spowolnienia tegoż przetwarzania w konkretnych sytuacjach, gdzie organizacja danych i ich forma okażą się wyjątkowo niekorzystne dla zastosowanych optymalizacji. W krańcowych przypadkach przetwarzanie informacji będzie wolniejsze od standardowej Metody List Prostych – wynika to z faktu nieco dłuższego przetwarzania bardziej złożonego mechanizmu informatycznego dla technik z modyfikacjami, niż w przypadku klasycznej MLP. Modyfikacje opierają się przede wszystkim na organizacji Bazy Danych przechowującej opisy obiektów.

Uporządkowanie opisów obiektów

Najprostszym z metod modyfikacji MLP jest uporządkowanie opisów obiektów i wprowadzenie ustalonej kolejności w ramach atrybutów obiektów i ich wartości (deskryptorów), a także takiej samej kolejności w termach zadawanych do systemu. Wtedy to wystarczy porównać odpowiednie termy składowe z odpowiednią pozycją przypisaną dla danego atrybutu, aby uzyskać szybsze przeszukanie zbioru.

Przykładem jest system informacyjny S zawierający obiekty x_1, x_2, x_3 z atrybutami a_1, a_2, a_3, a_4 o opisach:

      Wiek  Wzrost   Waga   Płeć
x_1 = (a_1,33), (a_2,190), (a_3,95), (a_4,M)
 
x_2 = (a_1,45), (a_2,173), (a_3,88), (a_4,M)
x_3 = (a_1,27), (a_2,158), (a_3,62), (a_4,K)

gdzie:

 a_1 =\{ dziecko < 15 < niepełnoletni < 18 < pełnoletni < 65 < emeryt \}
 a_2 =\{ niski < 160 <  średni < 175 < wysoki \}

Do systemu zadajemy kwerendę (term) postaci:

t^` = (a_2, średni) \cdot (a_1,pełnoletni) \cdot (a_4,M)

taki term należy przekształcić do uszeregowanego wg kolejności zastosowanej w bazie informacyjnej tj.

t^` = (a_1,pełnoletni) \cdot (a_2, średni) \cdot (a_3,*) \cdot (a_4,M)

a następnie dokonać przecięcia po termach składowych odpowiadających poszczególnym atrybutom.

\sigma(t_{d_1}) = \{ x_1, x_2, x_3 \}
\sigma(t_{d_2}) = \{ x_2 \}
\sigma(t_{d_3}) = X 
\sigma(t_{d_4}) = \{ x_1, x_2 \}

\sigma(t) = \{ x_1, x_2, x_3 \} \cap \{ x_2 \} \cap \{ X \} \cap \{ x_1, x_2 \} = \{ x_2 \}

Odpowiedzią na nasze zapytanie jest obiekt x_2

Grupowanie obiektów wg wybranego atrybutu

System informacyjny może zawierać atrybut, który często występuje w zapytaniach do niego. Uporządkowanie zbioru z jego wykorzystaniem może doprowadzić do zmniejszenia ilości koniecznych porównań. Cała baza opisów może zostać podzielona przez ilość wartości tego atrybutu. W sytuacji, gdy term składowy zawiera deskryptor z tym atrybutem znacząco ogranicza nam to ilość obiektów do przejrzenia. W przypadku najmniej korzystnym, gdy term składowy nie zawiera takiego deskryptora, skutkuje to przeglądem zupełnym całej bazy. Grupowanie obiektów względem takiego atrybutu daje nam zbiory rozłączne bazy danych, a ich suma to cała nasza baza.

X_{\nu_j} = \{ x \in X, \rho_x(a_i) = \nu_j, \nu_j \in V_{a_i} \}

Reasumując, w sytuacjach, gdy term składowy zawiera kluczowy deskryptor (a_j,\nu_j) przegląd dotyczy tylko wybranej grupy X_{\nu_j}.

Przykład możemy rozważyć korzystając z systemu informacyjnego z metody klasycznej. Dokonując grupowania obiektów wg a_5 otrzymamy zbiory obiektów:

• X_{BT} = \{ x_2, x_3, x_4, x_{12}, x_{13} \},
• X_{MR} = \{ x_5, x_{10}, x_{19} \},
• X_{DR} = \{ x_6, x_7, x_9, x_{11}, x_{14}, x_{18}, x_{20} \},
• X_{DC} = \{ x_8, x_{15}, x_{16} \},
• X_{PR} = \{ x_1, x_{17} \}.

Zadając do takiego systemu zapytanie w postaci termu:

t_i = (a_5,DR) \cdot (a_3,W) \cdot (a_2,b)

będzie skutkować przeglądem zupełnym zbioru odpowiadającego grupie DR, a więc 7-elementowego, zamiast 20-elementowego. Otrzymamy zatem:

\sigma(t_i) = \{ x_9, x_{11}, x_{14}, x_{18}, x_{20} \}

Istotnym jest takie rozważenie wg którego atrybutu dokonać dekompozycji zbiorów na ich rozłączne podzbiory aby uzyskać sytuację pozwalającą na skrócenie wyszukiwania. Bezsensem jest dekompozycja wg atrybutu rzadko używanego, bądź z bardzo nielicznym zbiorem wartości jeśli nie jest on nad wyraz często wybierany w zapytaniach składowych.

Dobrze jest zatem dekomponować bazę informacyjną wg atrybutu, który:

• występuje często w zapytaniach zadawanych do systemu,
• jest atrybutem posiadającym jak najliczniejszy zbiór wartości.

Zakładając równomierne rozłożenie obiektów w zbiorach po dekompozycji względem atrybutu a_i, można pokusić się o określenie średniego czasu wyszukiwania, który wyniesie:

\LARGE \tau = \frac{n \cdot \tau_0}{k}, gdzie:

• n – liczba obiektów,
• \tau_0 – czas przetwarzania jednego obiektu,
• k – ilość zbiorów zdekomponowanych (liczebność zbioru wartości a_i),

i który jest k-razy mniejszy niż czas przeglądu zupełnego całej bazy informacyjnej.

Metoda podziału połówkowego

Metoda ta dedykowana jest atrybutom, które są, lub mogą być interpretowane jako numeryczne. Metoda ta znana jest jako usprawniająca przeszukiwanie bazy informacyjnej, która dzielona jest na kolejne połówki, aż do znalezienia odpowiedzi na zadany term składowy. Wymaga tego, aby baza była uporządkowana w kolejności wartości rosnących (lub malejących) tego atrybutu.

Algorytmicznie metoda wygląda następująco:

1. Określamy ilość obiektów w zbiorze roboczym od jego inicjatora (pierwszego elementu zbioru) do terminatora (ostatniego elementu zbioru),
2. Szukając odpowiedzi przyrównujemy wartość atrybutu w termie składowym do wartości tego atrybutu w połowie zbioru obiektów,
3. Jeśli wartość szukana jest mniejsza, to ustawiamy terminator zbioru na obecną pozycję i przechodzimy do kroku 1,
4. Jeśli wartość szukana jest większa, to ustawiamy inicjator zbioru na obecną pozycję i przechodzimy do kroku pierwszego,
5. Jeśli wartość szukana jest równa to wykonujemy przegląd zupełny zbioru ograniczonego wyznaczonymi inicjatorem i terminatorem.

Ta metoda pozwala skrócić czas wyszukiwania do:

\LARGE \tau = \frac{n \cdot \tau_0}{2^k}, gdzie:

• n – liczba obiektów w zbiorze,
• \tau_0 – czas przetwarzania jednego obiektu w zbiorze
• k – krotność wykonania podziału połówkowego zbioru.

Indeksowanie

Indeksowanie wykorzystuje możliwość nadania zbiorowi obiektów dodatkowych wartości numerycznych powstałych w wyniku przekształcenia opisów wg założonego algorytmu, czy też nadania indeksów lub kodów. W rezultacie otrzymujemy bazę informatyczną w postaci numerycznej do której możemy zadawać pytania w tej samej postaci, a do wyszukania obiektów relewantnych do zadanego pytania możemy wykorzystać np. metodę podziałów połówkowych.

Weźmy przykład atrybutu a_5 z naszego już eksploatowanego przykładu, gdzie posiada on wartości V_{a_5} = \{ BT, MR, DR, DC, PR \}. Możemy je zakodować np. przydzielając im odpowiednio kody: 1, 2, 3, 4, 5 ¹Patrząc na ten aspekt informatycznie nie sposób zauważyć, że te wartości atrybutów niejako “z automatu” mają już nadane wartości!!! Są nimi odpowiednio: 16980, 19794, 17490, 17475, 20562 – wystarczy potraktować te dwuliterowce jako zapis ASCII i wyliczyć ze wzoru np. dla BT, gdzie kod ASCII litery B to 66, a T to 84, co można wyliczyć jako: 66*256+84 = 16980. Mając już wartości numeryczne bez przeszkód można zastosować poprzednio poznaną metodę do przeszukania obiektów. Takie podejście pozwala nam na łatwe przekształcanie w zasadzie dowolnych wartości atrybutów na ich postać numeryczną, a następnie stosowanie już numerycznych modyfikacji metod wyszukiwania informacji.

Parametry Metody List Prostych

Parametry te to przede wszystkim struktura bazy danych, występująca redundancja i zajętość pamięci, czasy wyszukiwania, a także możliwość stosowania aktualizacji bazy danych.

Struktura bazy danych

Metoda List Prostych korzysta z niewyszukanej bazy danych będącą po prostu listą opisów obiektów, co najwyżej uporządkowaną względem wybranej metody wyszukiwania informacji.

Redundancja i zajętość pamięci

Redundancja (czyli nadmiarowość) w tej metodzie nie występuje. Każdy obiekt posiada jeden opis. Zajętość pamięci jest zajętością jedynie powstałą jako skutek konieczności pamiętania opisów obiektów.

\Large R = \frac{ \sum\limits_{i=1}^r \overline{\overline{X}} - N }{N}

• r – liczba deskryptorów w systemie,
• N  – liczba obiektów (tożsame z: liczność zbioru X).

Czasy wyszukiwania

Czasy wyszukiwania w tej metodzie są bezpośrednio powiązane z ilością przetwarzanych obiektów. Zakładając średni czas przetwarzania \tau_0 jednego opisu obiektu, możemy obliczyć czas wyszukiwania jako k \cdot \tau_0, gdzie k to liczba przetworzonych obiektów. Określenie wartości k wymaga już sięgnięcia do informacji czy korzystaliśmy (i z jakiej) z modyfikacji metody.

Tak też w wersji klasycznej, przy pełnym przeglądzie mamy:

\large \tau_{klas} = n \cdot \tau_0, gdzie n – to ilość obiektów w systemie.

Przy skorzystaniu z grupowania:

\large \tau_{grup} = \frac{n \cdot \tau_0}{k}, gdzie k to liczba grup.

Przy podziale połówkowym:

\large \tau_{pp} = \frac{n \cdot \tau_0}{2^k}, gdzie k to ilość podziałów połówkowych.

Aktualizacje bazy danych

Aktualizacja bazy danych, czyli dodawanie i usuwanie obiektów z bazy informacyjnej w Metodzie List Prostych jest nieskomplikowana. Obiekty są dopisywane do listy obiektów. Ich usuwanie może wskazywać na konieczność reorganizacji bazy danych w celu fizycznego wyeliminowania z niej usuniętego obiektu. Także funkcjonalność edytowania opisu obiektu może wymuszać reorganizację bazy danych. Wynika to z przyjętego modelu informatycznego bazy i zastosowanej w nim metody wyszukiwania informacji np. konieczność uszeregowania opisów obiektów w założonym i wymaganym porządku, bądź utworzenie nowych podzbiorów obiektów. Łatwiej jest ograniczyć się do edycji opisu obiektu jako aktywności w postaci usunięcia jednego obiektu i wprowadzenia nowego (ze zmodyfikowanym opisem).

Podsumowanie metody

Metoda List Prostych jak sama nazwa wskazuje jest prosta. Owa prostota skutkuje znaczącą wadą tej metody, czyli czasem wyszukiwania informacji. Próby zniwelowania tej wady poprzez wprowadzenie modyfikacji nie do końca kończą temat, dlatego też należy zauważyć, iż powstały inne metody wyszukiwania informacji, a ta metoda może być z powodzeniem wykorzystywana w prostych systemach informacyjnych o niewielkiej liczbie obiektów.