Odwrócony indeks - Inverted index

W informatyce , odwrócony wskaźnik (określane również jako plik Inf lub odwrócony plik ) to indeks w bazie przechowywania mapowanie z zawartością, takich jak słowa lub liczby, do jego lokalizacji w tabeli , lub w dokumencie lub zestaw dokumenty (nazwane w przeciwieństwie do indeksu do przodu , który odwzorowuje dokumenty na zawartość). 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 przy wyszukiwaniu dokumentów systemy, używane 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 odwrócone architektury list, w tym ADABAS , DATACOM / DB i Model 204 .

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

Aplikacje

Odwrócona struktura danych indeksu jest centralnym elementem typowego algorytmu indeksowania wyszukiwarki . Celem implementacji wyszukiwarki jest optymalizacja szybkości zapytania: znalezienie dokumentów, w których występuje słowo X. Po opracowaniu indeksu w przód , który przechowuje listy słów w każdym dokumencie, jest on następnie odwracany, aby opracować indeks odwrócony. Zapytanie o indeks do przodu wymagałoby sekwencyjnej iteracji przez każdy dokument i każde słowo, aby zweryfikować pasujący dokument. Czas, pamięć i zasoby przetwarzania potrzebne do wykonania takiego zapytania nie zawsze są technicznie realistyczne. Zamiast wymieniać słowa na dokument w indeksie w przód, opracowywana jest odwrócona struktura danych indeksu, która wyszczególnia dokumenty według słowa.

Po utworzeniu indeksu odwróconego można teraz rozwiązać zapytanie, przechodząc do słowa ID (przez dostęp losowy ) w indeksie odwróconym.

W czasach przed komputerami konkordancje do ważnych książek były składane ręcznie. Były to skutecznie odwrócone indeksy z niewielką ilością towarzyszącego komentarza, którego wytworzenie 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 na podstawie referencyjnej sekwencji DNA. Niewielką liczbę niedopasowań (z powodu różnic między sekwencjonowanym DNA a referencyjnym DNA lub błędów) można wyjaśnić, dzieląc fragment na mniejsze fragmenty - co najmniej jeden podfragment prawdopodobnie będzie pasował do referencyjnej sekwencji DNA. Dopasowanie wymaga skonstruowania odwróconego indeksu wszystkich podciągów o określonej długości z referencyjnej sekwencji DNA. Ponieważ ludzkie DNA zawiera ponad 3 miliardy par zasad i musimy przechowywać podciąg DNA dla każdego indeksu i 32-bitową liczbę całkowitą dla samego indeksu, zapotrzebowanie na taki odwrócony indeks prawdopodobnie wynosi dziesiątki gigabajtów.

Kompresja

Ze względów historycznych opracowano odwróconą kompresję list i kompresję bitmap jako osobne kierunki badań, a dopiero później uznano, że rozwiązują zasadniczo ten sam problem.

Zobacz też

Bibliografia

  • Knuth, DE (1997) [1973]. „6.5. Pobieranie kluczy drugorzędnych”. The Art of Computer Programming (wydanie trzecie). Reading, Massachusetts : Addison-Wesley . ISBN   0-201-89685-0 .
  • Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (grudzień 1998). „Pliki odwrócone a pliki podpisów do indeksowania tekstu”. Transakcje ACM w systemach baz danych . New York: Association for Computing Machinery . 23 (4): 453–490. doi : 10.1145 / 296854.277632 . S2CID   7293918 .
  • Zobel, Justin; Moffat, Alistair (lipiec 2006). „Odwrócone pliki dla wyszukiwarek tekstowych”. Ankiety ACM Computing . New York: Association for Computing Machinery . 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; Fox, Edward A .; Wu, Harry (1983). „Rozszerzone wyszukiwanie informacji logicznych”. Commun. 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 .

Bibliografia

Linki zewnętrzne