METODA LIST ŁAŃCUCHOWYCH
W metodzie list łańcuchowych oprócz gromadzenia właściwych danych w bazie konieczne jest gromadzenie dodatkowych danych wspomagających proces wyszukiwania.
Po pierwsze, do każdej cechy w rekordzie dodawana jest informacja o miejscu wystąpienia tej cechy w bazie. Po drugie, dla wszystkich niepowtarzalnych cech zostaje zapamiętana informacja o miejscu pierwszego wystąpienia tej cechy oraz informacja o ilości wystąpień tej cechy. Prześledźmy proces tworzenia się bazy i dodatkowych informacji.
Wprowadzamy do bazy pierwszy wyraz z zadanego tekstu. W tabeli danych pojawia się pierwszy rekord. W tabeli łańcuchów pojawiają się dane, ale są puste, gdyż do tej pory ani razu w bazie nie pojawiły się cechy „Ala”, „L1” i „Z1”. W tabeli początków pojawiają się trzy nowe wpisy wskazujące gdzie się znajdują i ile jest cech „Ala”, „L1” oraz „Z1”.
Wprowadzamy do bazy drugi wyraz zadanego tekstu. Cechy „ma” i „Z5” są nowe, więc ich wprowadzanie wygląda tak jak wprowadzanie poprzednich cech. Natomiast cecha „L1” już występuje, więc nie dopisujemy jej do tabeli początków, a jedynie zmieniamy adres startowy oraz wagę dla tej cechy. W tabeli łańcuchów wprowadzamy pierwszy łańcuch – ponieważ cecha „L1” już istnieje, więc przy jej drugim wystąpieniu dodajemy informację, gdzie jest pierwsza taka cecha.
Poniżej przedstawiono poszczególne (nie wszystkie) kroki wprowadzania do bazy reszty tekstu.
Ostateczny wygląd bazy jest następujący:
Po zapoznaniu się z przedstawionym powyżej przykładem możemy się pokusić o stworzenie algorytmu dodawania nowych rekordów do bazy danych i struktur pomocniczych.
METODA LIST INWERSYJNYCH
W metodzie list inwersyjnych przyspieszenie procesu wyszukiwania danych w bazie uzyskano kosztem gromadzenia dodatkowych danych o położeniu poszczególnych cech.
Tworzona jest dodatkowa struktura danych (tabela cech) przechowująca informacje o wszystkich niepowtarzalnych cechach występujących w bazie. Dla każdej z cech występującej w tej strukturze zapamiętywane są informacje o lokalizacjach danej cechy w bazie. Prześledźmy proces tworzenia się bazy i dodatkowych informacji.
Wprowadzamy do bazy pierwszy wyraz z zadanego tekstu. W tabeli danych pojawia się pierwszy rekord. W tabeli cech pojawiają się trzy nowe cechy – „Ala”, „L1” i „Z1”. Do każdej z nowych cech podpinamy listę inwersyjną, w której zapisujemy numer rekordu zawierającego daną cechę – w tym wypadku 1.
Wprowadzamy do bazy drugi wyraz zadanego tekstu. Cechy „ma” i „Z5” są nowe, więc ich wprowadzanie wygląda tak jak wprowadzanie poprzednich cech. Natomiast cecha „L1” już występuje, więc nie dopisujemy jej do tabeli cech, a jedynie dokładamy do listy inwersyjnej tej cechy nowe pole. W polu tym zapisujemy informację o występowaniu cechy „L1” w rekordzie numer 2.
Poniżej przedstawiono poszczególne (nie wszystkie) kroki wprowadzania do bazy reszty tekstu.
Ostateczny wygląd bazy jest następujący:
Po zapoznaniu się z przedstawionym powyżej przykładem możemy się pokusić o stworzenie algorytmu dodawania nowych rekordów do bazy danych i struktur pomocniczych (jeśli chcesz zrób to sam).
informatyka wydrukuj do góry
