Odwrócony indeks

W informatyce odwrócony indeks (nazywany również listą wpisów , plikiem wpisów lub odwróconym plikiem ) to indeks bazy danych przechowujący mapowanie z treści, takiej jak słowa lub liczby, do ich lokalizacji w tabeli lub w dokumencie lub zestaw dokumentów (nazwany w przeciwieństwie do indeksu do przodu , który odwzorowuje dokumenty na treść). Celem odwróconego indeksu jest umożliwienie szybkiego wyszukiwania pełnotekstowego , kosztem zwiększonego przetwarzania po dodaniu dokumentu do bazy danych. Odwrócony plik może być samym plikiem bazy danych, a nie jego indeksem. Jest to najpopularniejsza struktura danych wykorzystywana w wyszukiwania dokumentów , wykorzystywana na dużą skalę np. w wyszukiwarkach . Ponadto kilka znaczących systemów zarządzania bazami danych opartych na komputerach mainframe ogólnego przeznaczenia wykorzystywało architektury odwróconej listy, w tym ADABAS , DATACOM/DB i Model 204 .

Istnieją dwa główne warianty odwróconych indeksów: Odwrócony indeks na poziomie rekordu (lub odwrócony indeks plików lub po prostu odwrócony plik ) zawiera listę odniesień do dokumentów dla każdego słowa. Odwrócony indeks na poziomie słów (lub pełny odwrócony indeks lub odwrócona lista ) dodatkowo zawiera pozycje każdego słowa w dokumencie. Ta druga forma oferuje większą funkcjonalność (np. wyszukiwanie fraz ), ale wymaga większej mocy obliczeniowej i przestrzeni do stworzenia.

Aplikacje

Odwrócona struktura danych indeksu jest centralnym elementem typowego algorytmu indeksowania wyszukiwarek . Celem wdrożenia wyszukiwarki jest optymalizacja szybkości zapytania: znalezienie dokumentów, w których występuje słowo X. Po opracowaniu indeksu do przodu , który przechowuje listy słów na dokument, jest on następnie odwracany w celu opracowania indeksu odwróconego. Zapytanie o indeks do przodu wymagałoby sekwencyjnej iteracji przez każdy dokument i każde słowo w celu zweryfikowania pasującego dokumentu. Czas, pamięć i zasoby przetwarzania potrzebne do wykonania takiego zapytania nie zawsze są technicznie realistyczne. Zamiast wymieniać słowa według dokumentu w indeksie do przodu, opracowywana jest odwrócona struktura danych indeksu, która wymienia dokumenty według słowa.

Po utworzeniu odwróconego indeksu zapytanie można teraz rozwiązać, przeskakując do identyfikatora słowa (poprzez dostęp swobodny ) w odwróconym indeksie.

W czasach przedkomputerowych konkordancje do ważnych ksiąg były składane ręcznie. Były to skutecznie odwrócone indeksy z niewielką ilością towarzyszących komentarzy, których stworzenie wymagało ogromnego wysiłku.

W bioinformatyce odwrócone indeksy są bardzo ważne w składaniu sekwencji krótkich fragmentów sekwencjonowanego DNA. Jednym ze sposobów znalezienia źródła fragmentu jest wyszukanie go w odniesieniu do referencyjnej sekwencji DNA. Niewielką liczbę niedopasowań (spowodowanych różnicami między zsekwencjonowanym DNA a referencyjnym DNA lub błędami) można wyjaśnić, dzieląc fragment na mniejsze fragmenty - co najmniej jeden podfragment prawdopodobnie pasuje do referencyjnej sekwencji DNA. Dopasowanie wymaga skonstruowania odwróconego indeksu wszystkich podłańcuchów o określonej długości z referencyjnej sekwencji DNA. Ponieważ ludzkie DNA zawiera ponad 3 miliardy par zasad i musimy przechowywać podłańcuch DNA dla każdego indeksu i 32-bitową liczbę całkowitą dla samego indeksu, zapotrzebowanie na przechowywanie takiego odwróconego indeksu wynosiłoby prawdopodobnie dziesiątki gigabajtów.

Kompresja

Ze względów historycznych kompresja odwróconej listy i kompresja mapy bitowej zostały opracowane jako odrębne kierunki badań i dopiero później uznano, że rozwiązują zasadniczo ten sam problem.

Zobacz też

Bibliografia

  •   Knutha, DE (1997) [1973]. „6.5. Odzyskiwanie kluczy pomocniczych” . Sztuka programowania komputerowego (wyd. Trzecie). Reading, Massachusetts : Addison-Wesley . ISBN 0-201-89685-0 .
  •   Zobel, Justyn; Moffat, Alistair; Ramamohanarao, Kotagiri (grudzień 1998). „Odwrócone pliki a pliki sygnatur do indeksowania tekstu” . Transakcje ACM w systemach baz danych . Nowy Jork: Stowarzyszenie Maszyn Komputerowych . 23 (4): 453–490. doi : 10.1145/296854.277632 . S2CID 7293918 .
  •   Zobel, Justyn; Moffat, Alistair (lipiec 2006). „Odwrócone pliki dla wyszukiwarek tekstowych” . Ankiety komputerowe ACM . Nowy Jork: Stowarzyszenie Maszyn Komputerowych . 38 (2): 6. doi : 10.1145/1132956.1132959 . S2CID 207158957 .
  •   Baeza-Yates, Ricardo ; Ribeiro-Neto, Berthier (1999). Nowoczesne wyszukiwanie informacji . Reading, Massachusetts : Addison-Wesley Longman. P. 192. ISBN 0-201-39829-X .
  •   Salton, Gerard; Lis, Edward A.; Wu, Harry (1983). „Rozszerzone wyszukiwanie informacji logicznych”. Komuna. ACM . ACM. 26 (11): 1022. doi : 10.1145/182.358466 . hdl : 1813/6351 . S2CID 207180535 .
  •   Wyszukiwanie informacji: wdrażanie i ocena wyszukiwarek . Cambridge, Massachusetts: MIT Press. 2010. ISBN 978-0-262-02651-2 . Zarchiwizowane od oryginału w dniu 2020-10-05 . Źródło 2010-08-08 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Inverted_index&oldid=1137401637 ”