ED-4.2-M13-1.0-Slajd20

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Struktury danych: pliki odwrócone (1)

Struktury danych: pliki odwrócone (1)


Przejdziemy obecnie do przedstawienia wybranych struktur danych wspierających przechowywanie i wyszukiwanie dokumentów. W literaturze zaproponowano szereg struktur danych wspierających przechowywanie i wyszukiwanie dokumentów tekstowych. Najbardziej popularne, w chwili obecnej, są dwie struktury danych: pliki odwrócone i pliki sygnaturowe. Idea pliku odwróconego jest przedstawiona na następnym slajdzie. Najczęściej, dokumenty tekstowe przechowujemy z wykorzystaniem dwóch poindeksowanych tablic: TermTable i DocTable. Podstawową tablicą przechowująca dokumenty jest tablica TermTable, której rekordy składają się z par <słowo-wskaźnik> lub <słowo-lista_wskaźników>. Słowa są kluczami wyszukiwania, natomiast wskaźnik wskazuje na blok zawierający wskaźniki do dokumentów zawierających dane słowo (rozwiązanie przedstawione na slajdzie). W przypadku pary słowo-lista_wskaźników, lista wskaźników wskazuje bezpośrednio na dokumenty zawierające dane słowo. Tablica DicTable jest uzupełnieniem tablicy TermTable. Rekordy tablicy DocTable składają się z par <doc_id, lista słów kluczowych> lub lista wskaźników do słów kluczowych występujących w dokumencie doc_id, uporządkowana zgodnie z ich ważnością. W bloku zawierającym, dla danego słowa, wskaźniki do dokumentów zawierających dane słowo, umieszcza się również pewne dodatkowe dane o samym wystąpieniu słowa (np. częstość występowania słowa danym dokumencie, waga TF-IDF slowa). Wyszukiwanie jest realizowane w oparciu o słowa.


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