Jaka jest różnica między odwróconym indeksem a zwykłym starym indeksem?


99

W inżynierii oprogramowania indeksy tworzymy cały czas (np. W bazach danych), ale słyszę też, że wiele osób mówi o indeksach odwróconych. Czy jest między nimi coś zasadniczo innego? Brzmią jak to samo.



Aby wyjaśnić, pytasz: co różni się od normalnego indeksu ( en.wikipedia.org/wiki/Index_%28database%29 ), który dzieli tabelę na podstawie danych, które już istnieją w tej tabeli? Czy to jest poprawne?
jwheron

3
@ guidoism To, o czym nikt nie wspomniał (chociaż normalność częściowo opisuje to za pomocą przykładów, a miłość jest prawie na przycisku) to fakt, że odwrócone indeksy „odwracają” podstawowe dane, aby były bardziej wydajne (np. zamień klucze / dane w celu wyszukiwania z innej perspektywy lub porządkowanie alfabetyczne / numeryczne, aby umożliwić algorytmy szybkiego wyszukiwania), podczas gdy standardowy indeks przechowuje dane w takiej postaci, w jakiej je znajdzie. Odniesienia „wstecz / dalej” i dosłowne znaczenie słowa „odwróć” nie mają tutaj zastosowania, zamiast tego odnosi się do inwersji danych w celu uzyskania wydajnego formatu właściwego dla wykonywanego zadania.
TheManWithNoName

Odpowiedzi:


216

Jednym z typowych zastosowań jest „… aby umożliwić szybkie wyszukiwanie pełnotekstowe”.

Te dwa typy oznaczają kierunkowość . Jeden prowadzi cię do przodu przez indeks, a drugi do tyłu (odwrotnie) przez indeks. Otóż ​​to. Nie ma tu żadnej tajemnicy do odkrycia. W przeciwnym razie te dwa typy są identyczne, to tylko kwestia tego, jakie masz informacje , a co za tym idzie, jakie informacje próbujesz znaleźć.

Aby odpowiedzieć na twoje zapytanie, nie sądzę, aby rzeczywiście można było dowiedzieć się, dlaczego zastosowanie jest takie, jakie jest dzisiaj. Jedynym powodem, dla którego ważne jest zdefiniowanie, który jest, forwarda który jest, invertedjest to, że wszyscy możemy o nich porozmawiać i wszyscy wiedzą, o którym kierunku mówimy. Pomyśl o terminach „lewy” i „prawy”: są one względne. Co nie ma znaczenia, poza tym, że każdy musi się zgodzić, który z nich jest „lewy”, a który „właściwy”, aby słowa miały znaczenie. Gdybyśmy jako kultura zdecydowali się odwrócić w lewo i w prawo, mielibyście ten sam problem, zastanawiając się, czym jest „skręt w prawo”, a co „skręt w lewo”, odkąd zmieniło się uzgodnione znaczenie. Jednak nazewnictwo jest arbitralne, na znaczeniu.

W swoim komentarzu, w którym pytasz „proszę, nie definiuj tylko terminów”, nie rozumiesz sedna sprawy i myślę, że po prostu rozłączasz się ze sformułowaniami, podczas gdy nie ma między nimi absolutnie żadnej różnicy.


Z korzyścią dla przyszłych czytelników przedstawię teraz kilka przykładów indeksów „do przodu” i „odwróconych”:

Przykład 1: wyszukiwanie w sieci

Jeśli myślisz, że odwrotność indeksu jest czymś w rodzaju odwrotności funkcji w matematyce , gdzie odwrotność jest specjalną rzeczą, która ma inną postać, to się mylisz: tak nie jest w tym przypadku.

W wyszukiwarce masz listę dokumentów (stron w witrynach internetowych), w których wpisujesz słowa kluczowe i otrzymujesz wyniki.

Wskaźnik do przodu (lub po prostu index) jest wykaz dokumentów , a które słowa pojawiają się w nich. W przykładzie wyszukiwania w sieci Google przeszukuje sieć, budując listę dokumentów i ustalając, które słowa pojawiają się na każdej stronie.

Odwrócony wskaźnik jest lista słów , oraz dokumenty, w których się pojawiają. W przykładzie wyszukiwania w Internecie podajesz listę słów (zapytanie wyszukiwania), a Google tworzy dokumenty (linki wyników wyszukiwania).

Oba są indeksami - to tylko kwestia, w którym kierunku zmierzasz. Przekaż dalej pochodzi z dokumentów-> do-> słów, odwrócony jest od słów-> do-> dokumentów.

Przykład 2: DNS

Innym przykładem jest wyszukiwanie DNS (które pobiera nazwę hosta i zwraca adres IP) i wyszukiwanie wsteczne (które pobiera adres IP i podaje nazwę hosta).

Przykład 3: książka

Indeks z tyłu książki jest w rzeczywistości indeksem odwróconym , zgodnie z powyższymi przykładami - listą słów i miejscem ich znalezienia w książce. W książce spis treści jest jak indeks do przodu : jest to lista dokumentów (rozdziałów), które zawiera książka, z wyjątkiem tego, że zamiast wymieniać słowa w tych sekcjach, spis treści podaje tylko nazwę / ogólny opis tego, co jest zawarte w tych dokumentach (rozdziałach).

Przykład 4: Twój telefon komórkowy

Indeks naprzód w telefonie komórkowym jest twoja lista kontaktów, a których numery telefonów (komórka, dom, praca) są związane z tymi kontaktami. Odwrócony wskaźnik jest to, co pozwala na ręczne wprowadzenie numeru telefonu, a po trafieniu „dial” zobaczysz nazwisko osoby, zamiast liczby, ponieważ telefon został wzięty pod numer telefonu i znaleźć Ci kontakt z nim związane.


11
Dziękuję za Twój czas. ale twoja odpowiedź jest wciąż niekompletna. Jak wspomniałem w mojej prośbie o nagrodę, ROZUMIEM, co oznaczają te terminy i dlaczego się pojawiają. Moje pytanie brzmiało: „dlaczego ludzie, którzy nazywali odwrócone indeksy, nazywali je odwróconymi, skoro mamy długą tradycję, która nazywa je zwykłymi indeksami? Na przykład indeksy na końcu książek, jak wskazałeś, są w rzeczywistości odwrócone. z perspektywy historycznej indeksy na końcu książek były przed indeksami internetowymi. Po co więc odwracać tradycję? ”. Domyślam się, że to tylko jedna z tych rzeczy, które właśnie się wydarzyły ...
Manav,

1
„Nie sądzę, że to możliwe, aby wiedzieć dlaczego bez przeprowadzania historyczną analizę stosowania terminów” - mam nadzieję, że ktoś będzie przeprowadzenie takiego badania historycznego i dać odpowiedź. :-) Ponieważ jest to przeciwieństwo potocznego znaczenia słowa „indeks”. (Jedną z możliwych odpowiedzi jest to, że kiedy po raz pierwszy pomyślano o frazie „indeks odwrócony”, fraza „indeks” była już używana dla jakiegoś „indeksu” odwróconego względem „indeksu odwróconego”, tj. Odwróconego względem rzeczywistego znaczenia „indeksu” „. W takim przypadku dobrze byłoby wiedzieć, dlaczego„ indeks ”do przodu ma dziwną nazwę.)
ShreevatsaR

2
@jefflunt zastanawiał się tylko, dlaczego powinno być używane indeksowanie w przód. Szczególnie mówię tutaj o przykładzie wyszukiwania w sieci. Więc jeśli google, w ramach indeksowania w przód robi listę dokumentów <-> słów w nich , a ostatecznie używa listy słów <-> lista dokumentów w swoich wyszukiwaniach, to dlaczego lista dokumentów <-> wyrazy w je ? Innymi słowy, moje pytanie brzmi: nie można zapytać google, jakie słowa znajdują się na określonej stronie (dokumencie), albo przede wszystkim zapytać, gdzie występują słowa kluczowe, których szuka, na stronach. Dlaczego więc indeksowanie w przód?
quickbrownfox

1
Czyli w kontekście relacyjnej bazy danych nie ma odwróconego indeksu? lub te indeksy są w rzeczywistości „indeksami odwróconymi”. Problem z „zgodnymi” terminami w literaturze to ignorancja / błąd / rozważanie kilku pionierów lub korpusów, którzy zaczynają różne umowy, a część społeczności stosuje tę nomenklaturę. Po jakimś czasie wszyscy są zdezorientowani. Jestem pewien, że w oprogramowaniu jest wiele terminów, które pierwotnie miały być, powiedzmy, A, ale różne społeczności celowo lub omyłkowo przyjmują je jako A 'lub B, składniowo zbaczając z kursu. Wciąż dezorientuje to nowych uczniów.
nir

1
@Roylee - nie czytałem tej białej księgi. Myślę, że pytasz: „Czy aktualizujesz odwrócony indeks podczas aktualizacji indeksu do przodu?” Jeśli to jest twoje pytanie, odpowiedź brzmi: tak.
jefflunt

26

Nazwali to odwróceniem tylko dlatego, że istnieje już indeks do przodu. Weźmy na przykład wyszukiwarkę, która składa się z dwóch części: pierwsza część to „robot sieciowy i parser”, które budują indeks z dokumentu do słowa, druga część to baza danych wyszukiwania, która buduje indeks ze słowa do dokumentu. Ponieważ istnieje pierwszy indeks, naturalnie nazywamy drugi indeks indeksem odwróconym.

Jeśli nazwiesz spis treści (spis treści) książki jako indeks, powinieneś nazwać indeks na końcu książki jako „indeks odwrócony”. Lub z drugiej strony możesz nazwać spis treści jako indeks odwrócony.


6
Powinna to być akceptowana odpowiedź, ponieważ odpowiada na pytanie, dlaczego nazywamy indeks „odwróconymi”, nawet jeśli jest to właśnie to, co wszyscy myślą o „normalnym indeksie”. Indeks b-drzewa SQL przechowuje dla każdego słowa wskaźnik do wszystkich wierszy („dokumentów”) zawierających je. Tam nazywamy to „indeksem”. Ale w wyszukiwarkach nagle nazywamy tę samą procedurę „odwróconym indeksem”. Nie dlatego, że jest zasadniczo inny, ale dlatego, że najpierw utworzyliśmy „indeks do przodu” (podzielony tekst), a następnie go „odwróciliśmy”. Zatem w sumie nazwa „odwrotna” pochodzi z procesu jej tworzenia, a nie z ostatecznej struktury indeksu.
Foo Bar

@xeranic dzięki za wgląd. Szybkie pytanie: Czy praktyczne jest usuwanie wpisów z pliku indeksu do przodu po zbudowaniu z niego indeksu odwróconego?
Roy Lee

3
Zgadzam się z @FooBar. Tę odpowiedź należy wybrać jako właściwą. Odpowiedziała, dlaczego wymyślamy nowy termin, inverted index mimo że wszystkie normalne wskaźniki w naszym życiu są już używane jako inverted.
Ryan Lyu

7

zazwyczaj mówiąc o indeksie, masz na myśli jakieś dodatkowe obliczenia lub zapisane wyniki procedur, które zostały wykonane w celu przyspieszenia aplikacji (np. MySQL lub inny RDBMS Skonsultuj się z MySQL w dokumentacji ). Indeksowanie może być również związane z buforowaniem itp.

Odwrócony indeks tworzy plik o strukturze przeznaczonej głównie do wyszukiwania (pełnotekstowego).

Indeks odwrócony składa się z dwóch głównych plików:

  • Słownictwo
  • Zdarzenia

W słowniku są popularne słowa wyodrębnione z tekstu (oczywiście po przefiltrowaniu słów z czarnej listy, takich jak zaimki). Plik wystąpień zawiera powiązania między słowami i dokumentami (słowo 1 pojawia się w doc1 i doc2, a nie w doc3). Jest reprezentowany w postaci macierzy.

Proces indeksowania - indeks odwrócony

Na powyższym obrazku pokazano proces tworzenia dwóch wspomnianych plików.

Jeśli jesteś dalej zainteresowany tą problematyką, mogę polecić Ci świetną książkę napisaną przez Ricardo Yated - Modern Information Retrieval ( zobacz na Amazon ) - chyba około strony 200.

Mam nadzieję, że to pomoże :-)


To bardzo dobra odpowiedź, ponieważ wyjaśnia, czym naprawdę jest odwrócony indeks. Pomija ideę indeksowania w przód i indeksowania odwrotnego, który różni się od algorytmu używanego do wyszukiwania, które jest włączane przez tworzenie i odwracanie indeksu.
AN6U5

6

Normalność już cudownie rozróżniła między indeksem forward i indeksem odwróconym, ale jeśli chodzi o pytanie, dlaczego jeden jest nazywany indeksem terminowym, a drugi indeksem odwróconym, może dlatego są tak nazywane ---

Biorąc przykład z przeszukiwania i indeksowania w wyszukiwarkach (lub tworzenia indeksu książki), indeks do przodu może być tworzony jednocześnie podczas przeszukiwania stron internetowych (lub czytania książki) lub przechodzenia do przodu . Więc jeśli masz 10 stron internetowych do przeszukania (lub 10 rozdziałów w książce), możesz zaindeksować pierwszą stronę internetową (przeczytaj pierwszy rozdział), a następnie utworzyć listę słów, które pojawiają się na stronie (słowa, które pojawiają się w rozdziale) i kontynuować ten proces dla innych stron internetowych (innych rozdziałów), więc do czasu przeszukania wszystkich 10 stron internetowych (przeczytania wszystkich 10 rozdziałów), Twój indeks w przód jest kompletny i każda strona internetowa (rozdział) wskazuje listę zawartych w niej słów .

Aby jednak utworzyć odwrócony indeks, musisz przeszukać wszystkie 10 stron internetowych (przeczytaj 10 rozdziałów), a następnie pobrać każde słowo z listy dokumentów i dowiedzieć się, które dokumenty zawierają to słowo. Jest to więc jak cofanie się po przeszukaniu stron internetowych (przeczytaj rozdziały książki) . Więc nazywa się to odwróconym indeksem.

To tylko moje spekulacje.


5

Istnieje wiele typów indeksów. Na przykład B-tree, R-tree, hash ... Do różnych celów musimy wybrać właściwy indeks.

Indeks odwrócony jest wyjątkowy. Indeks odwrócony zwykle używany w wyszukiwarce pełnotekstowej. Korzystając z odwróconego indeksu, możemy jak najszybciej zlokalizować słowo w dokumencie (lub zestawie dokumentów). Pomyśl o limicie pamięci i procesora, inny indeks nie może zakończyć tego zadania.

Możesz przeczytać dokument Lucene, aby uzyskać więcej informacji. To wyszukiwarka open source. http://lucene.apache.org/java/docs/index.html


3

Termin „Indeks odwróconych słów” odnosi się do zmiany relacji pojedynczego dokumentu zawierającego wiele słów do każdego unikalnego słowa zawierającego (lub identyfikującego) listę wielu dokumentów. Jest to efektywne przyjęcie relacji jeden do wielu (dokumenty na słowa) i odwrócenie (lub odwrócenie) go w taki sposób, że istnieje teraz nowy „odwrócony” związek jeden do wielu, który jest unikalnym słowem odnoszącym się do wielu Dokumenty (czyli wszystko, co zawiera to słowo). Jego pochodzenie jest naprawdę proste, a termin „odwrócony indeks” był używany do opisania ręcznych indeksów tego samego typu na długo przed istnieniem komputerów i elektronicznego szybkiego indeksowania (tak, przyznaję, jestem starym, prymitywnym programistą, prawie wystarczająco stara, by uważać Grace Hopper za „słodką młodą damę” wiek odpowiedni do zalotów, kiedy COBOL był nowym, błyszczącym językiem). Proszę, nie odrzucajcie nas jeszcze, staruszków, ponieważ czasami możemy zapewnić przydatne, a być może nawet cenne, historyczne ciekawostki - to znaczy, gdy nasza osobista pamięć RAM nadal działa. [szeroki uśmiech]


2

w indeksach odwróconych mamy następującą postać:

word1-> lista dokumentów, w których występuje (kolejność posortowana)

word2-> lista dokumentów, w których występuje (kolejność posortowana)

Jest to bardzo przydatne do przetwarzania zapytań w wyszukiwarkach, ponieważ pozwala nam znaleźć dokumenty, w których występuje słowo.

Możesz użyć nadzorowanego uczenia maszynowego do zbudowania tego odwróconego indeksu.


6
To brzmi dla mnie jak indeks, co w tym jest odwrócone?
guidoizm

2
@ guidoism Odwrócony indeks jest odwróceniem indeksu forward. indeks do przodu przechowuje listę słów dla każdego dokumentu. Np. Doc-> w1, w2
Programmer

Nadal nie znajduję żadnej różnicy między indeksem Forward i Inverted (jeśli chodzi o to, jak to działa, zostaw bit nazewnictwa). Obydwa dla mnie wyglądają jak indeks, który odwzorowuje pole na zbiór identyfikatorów dokumentów. W ten sposób zrozumiałem, w jaki sposób Oracle btree (inaczej określany jako forward index) organizuje dane. Nie widzę żadnej różnicy w zasadach indeksu odwróconego. Mapowanie Doc -> w1, w2, w3 wygląda na nieefektywną propozycję pod względem wyszukiwania. Zastanawiam się, dlaczego tak jest w pierwszej kolejności? To sprawia, że ​​wracam do punktu wyjścia. :-).
user1189332

@Programmer Szybkie pytanie: Czy jest praktyczne usuwanie wpisów z pliku indeksu do przodu po zbudowaniu z niego indeksu odwróconego?
Roy Lee

0

Jeszcze jedna różnica:

Obsługa aktualizacji z indeksem odwróconym jest kosztowna w porównaniu z indeksem forward.

Indeks do przodu obsługuje aktualizacje z łatwością, odzwierciedlając zmiany tylko w odpowiednim indeksie dokumentu, podczas gdy w indeksie odwróconym ta sama zmiana musi odzwierciedlać się w wielu pozycjach w indeksie odwróconym.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.