W jaki sposób Lucene indeksuje dokumenty?

95

Przeczytałem jakiś dokument o Lucene; również przeczytałem dokument w tym linku ( http://lucene.sourceforge.net/talks/pisa ).

Naprawdę nie rozumiem, jak Lucene indeksuje dokumenty i nie rozumiem, jakich algorytmów używa Lucene do indeksowania?

Na powyższym łączu jest napisane, że Lucene używa tego algorytmu do indeksowania:

  • algorytm przyrostowy:
    • utrzymywać stos indeksów segmentowych
    • utworzyć indeks dla każdego przychodzącego dokumentu
    • umieść nowe indeksy na stosie
    • niech b = 10 będzie współczynnikiem łączenia; M = 8

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

W jaki sposób ten algorytm zapewnia zoptymalizowane indeksowanie?

Czy Lucene używa algorytmu B-drzewa lub innego podobnego algorytmu do indeksowania - czy też ma określony algorytm?

M.Amrollahi
źródło
Większość odpowiedzi jest poprawnych, ponieważ Lucene najpierw tworzy odwrócony indeks, ale to nie wyjaśnia kluczowego punktu, w jaki sposób indeks tego terminu jest następnie przeszukiwany (i uważam, że właśnie o to prosił OP). Dlatego poniżej proszę znaleźć nową odpowiedź na to dość stare pytanie, która, miejmy nadzieję, zapewni lepszy wgląd.
fnl
1
Zaktualizowałem moją odpowiedź jeszcze raz, ponieważ obecne odpowiedzi (w tym moje!) Nie są tak naprawdę satysfakcjonujące, aby odpowiedzieć na dwa główne pytania PO (w jaki sposób Lucene zapewnia zoptymalizowane indeksowanie i według którego konkretnego algorytmu - listy pomijanej, a nie drzewa B, BTW). Mam nadzieję, że moje ostatnie aktualizacje teraz właściwie odpowiadają na rzeczywiste pytanie!
fnl

Odpowiedzi:

54

Jest tutaj dość dobry artykuł: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Edycja 12/2014: Zaktualizowano do wersji zarchiwizowanej z powodu usunięcia oryginału, prawdopodobnie najlepszą nowszą alternatywą jest http://lucene.apache.org/core/3_6_2/fileformats.html

Jeszcze nowsza wersja jest dostępna pod adresem http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , ale wydaje się, że zawiera mniej informacji niż starszy.

Krótko mówiąc, kiedy lucene indeksuje dokument, dzieli go na kilka terminów. Następnie zapisuje terminy w pliku indeksu, w którym każdy termin jest powiązany z dokumentami, które go zawierają. Można o tym pomyśleć trochę jak o tablicy haszującej.

Terminy są generowane przy użyciu analizatora, który wyprowadza każde słowo do jego formy źródłowej. Najpopularniejszym algorytmem rymowania dla języka angielskiego jest algorytm rymowania Portera: http://tartarus.org/~martin/PorterStemmer/

Zapytanie jest przetwarzane przez ten sam analizator, który został użyty do zbudowania indeksu, a następnie użyty do wyszukania pasujących terminów w indeksie. To zawiera listę dokumentów pasujących do zapytania.

Darren
źródło
Dziękuję za odpowiedź i linki. Ale słyszałem, że projekt Lucene ma specjalny stemmer o nazwie „Snowball”? Słyszałeś coś o tym?
M.Amrollahi
To jest inne pytanie: Zobacz lucidimagination.com/search/… Poza tym, widząc wzorzec pytań, sugeruję przeczytanie książki „Lucene in Action”: manning.com/hatcher2 (pierwsze wydanie jest trochę przestarzałe, ale może być znalezione w wersji martwego drzewa. Drugie wydanie można kupić jako e-book).
Yuval F
5
Możesz zmodyfikować odpowiedź, nie znaleziono pierwszego odsyłacza, który jest odsyłaczem do IBM :)
Adelin
W jaki sposób pola wpisują się w cały obraz? Jeśli zapytanie dotyczy określonego pola, w jaki sposób iw którym momencie lucene wie, że termin wskazujący na dokument nie znajduje się w żadnym miejscu w dokumencie, ale w żądanym polu?
Levon Tamrazov
44

W skrócie, Lucene buduje odwrócony indeks przy użyciu Skip-Lists na dysku , a następnie ładuje mapowanie indeksowanych terminów do pamięci przy użyciu przetwornika skończonego stanu (FST). Należy jednak pamiętać, że Lucene nie (koniecznie) ładuje wszystkie indeksowane terminy do pamięci RAM , jak opisał Michael McCandless, sam autor systemu indeksowania Lucene. Zauważ, że używając Skip-Lists, indeks można przechodzić od jednego trafienia do drugiego, dzięki czemu możliwe są takie rzeczy jak set, a zwłaszcza zapytania o zakres (podobnie jak B-drzewa). I wpis Wikipedii na temat indeksowania list pomijanych wyjaśnia również, dlaczego realizacja Skip-List Lucene jest nazywany wielopoziomowe Skip-list - zasadniczo, aby umożliwić O(log n)wyszukiwanie (znowu, podobnie jak B-drzewa).

Kiedy więc odwrócony indeks (termin) - oparty na strukturze danych Skip-List - zostanie utworzony z dokumentów, indeks jest przechowywany na dysku. Lucene następnie ładuje (jak już powiedział: być może, tylko niektóre) te terminy do skończonego przetwornika , w implementacji FST luźno inspirowany przez Morfologick .

Michael McCandless (również) wykonuje całkiem dobrą i zwięzłą robotę, wyjaśniając, jak i dlaczego Lucene używa (minimalnie acyklicznego) FST do indeksowania terminów, które Lucene przechowuje w pamięci, zasadniczo jako a SortedMap<ByteSequence,SomeOutput>, i podaje podstawowe pojęcie o tym, jak działają FST (tj. jak FST kompaktuje sekwencje bajtów [tj. terminy indeksowane], aby wykorzystanie pamięci tego odwzorowania rosło podliniowo). I wskazuje na artykuł, w którym opisano konkretny algorytm FST, którego używa Lucene.

Dla tych, którzy ciekawi dlaczego używa Lucene skip-listy, podczas gdy większość baz używać (B +) - i / lub (b) -Trees, przyjrzeć się z prawej SO odpowiedzi dotyczącej tej kwestii (skip wykazach vs. B-drzewach). Ta odpowiedź daje całkiem dobre, głębokie wyjaśnienie - w zasadzie nie tyle sprawiaj, że równoczesne aktualizacje indeksu będą „bardziej podatne” (ponieważ możesz zdecydować, aby nie ponownie balansować drzewa B natychmiast, uzyskując w ten sposób mniej więcej taką samą wydajność równoczesną jak Skip-List), ale raczej Skip-Lists oszczędzają Ci pracy nad (opóźnioną lub nie) operacją równoważenia (ostatecznie) potrzebne B-drzewom (w rzeczywistości, jak pokazuje odpowiedź / odniesienia, prawdopodobnie jest bardzo mała różnica w wydajności między B-drzewami i [wielopoziomowymi] listami pominiętymi, jeśli którekolwiek z nich są „wykonane prawidłowo”).

fnl
źródło
1
Afaik używają Skip List zamiast B-tree, aby zmniejszyć liczbę wyszukiwań dysku, ponieważ część Skip List znajduje się w pamięci i bardzo niewiele operacji we / wy dysku wymaga podczas przechodzenia przez indeks
Anton
24

Wydaje się, że Twoje pytanie dotyczy bardziej scalania indeksów niż samego indeksowania.

Proces indeksowania jest dość prosty, jeśli zignorujesz szczegóły niskiego poziomu. Lucene tworzy z dokumentów tzw. „Indeks odwrócony”. Więc jeśli pojawi się dokument z tekstem „Być albo nie być” i id = 1, odwrócony indeks będzie wyglądał następująco:

[to] → 1
[be] → 1
[or] → 1
[not] → 1

To jest w zasadzie to - indeks od słowa do listy dokumentów zawierających dane słowo. Każdy wiersz tego indeksu (słowa) nazywany jest listą ogłoszeń. Indeks ten jest wówczas przechowywany długoterminowo.

W rzeczywistości sprawy są oczywiście bardziej skomplikowane:

  • Lucene może pominąć niektóre słowa w oparciu o podany analizator;
  • słowa mogą być wstępnie przetwarzane przy użyciu algorytmu ryzacji w celu zmniejszenia fleksji języka;
  • lista wysyłkowa może zawierać nie tylko identyfikatory dokumentów, ale także offset danego słowa w dokumencie (potencjalnie w kilku przypadkach) oraz inne dodatkowe informacje.

Istnieje wiele innych komplikacji, które nie są tak ważne dla podstawowego zrozumienia.

Ważne jest jednak, aby zrozumieć, że indeks Lucene jest tylko dodawany . W pewnym momencie aplikacja zdecyduje się zatwierdzić (opublikować) wszystkie zmiany w indeksie. Lucene kończy wszystkie operacje serwisowe indeksem i zamyka go, aby był dostępny do wyszukiwania. Po zatwierdzeniu indeks w zasadzie niezmienny. Ten indeks (lub część indeksu) nazywany jest segmentem . Kiedy Lucene wyszukuje zapytanie, przeszukuje wszystkie dostępne segmenty.

Powstaje więc pytanie - jak zmienić już zindeksowany dokument ?

Nowe dokumenty lub nowe wersje już zindeksowanych dokumentów są indeksowane w nowych segmentach, a stare wersje unieważniane w poprzednich segmentach za pomocą tzw. Listy zniszczeń . Lista zabójstw jest jedyną częścią zatwierdzonego indeksu, która może ulec zmianie. Jak można się domyślić, wydajność indeksowania spada z czasem, ponieważ stare indeksy mogą zawierać głównie usunięte dokumenty.

Tutaj pojawia się łączenie. Merging - to proces łączenia kilku indeksów w celu ogólnego zwiększenia wydajności. Zasadniczo podczas scalania dokumenty na żywo są kopiowane do nowego segmentu, a stare segmenty są całkowicie usuwane.

Korzystając z tego prostego procesu, Lucene jest w stanie utrzymać indeks w dobrym stanie pod względem wydajności wyszukiwania.

Mam nadzieję, że to pomoże.

Denis Bazhenov
źródło
1
Czy w celu znalezienia najpierw najbardziej aktualnych wyników wyszukiwanie powinno rozpocząć się od spojrzenia na najnowsze segmenty? Więc tylko dla wyjaśnienia - załóżmy, że dokument jest aktualizowany. Starsza wersja dokumentu jest dodawana do listy zabitych, a następnie wszelkie dopasowania znalezione w starszych segmentach są usuwane z wyników wyszukiwania, jeśli ich identyfikator dokumentu pasuje do identyfikatora na liście zabitych?
Joel B
2
Tak, masz rację. Jedyną rzeczą, o której należy wspomnieć, jest ostateczna kolejność określana za pomocą reguł sortowania (indeks trafności w trywialnym przypadku), dlatego kolejność wyszukiwania segmentów nie ma znaczenia.
Denis Bazhenov
12

Jest to indeks odwrócony , ale nie określa, jakiej struktury używa. Format indeksu w Lucene zawiera pełne informacje.
Rozpocznij od „Podsumowania rozszerzeń plików”.

Najpierw zauważysz, że mówi o różnych różnych indeksach. O ile mogłem zauważyć, żadne z nich nie używa ściśle mówiąc B-drzewa , ale są podobieństwa - powyższe konstrukcje przypominają drzewa.

Bez powodu
źródło
1
Odwrócony indeks Lucene jest oparty na liście pominiętych, a nie na B-drzewie. Wciąż struktura podobna do drzewa w bardzo szerokim sensie, ale tylko po to, by być kompletnym - np. Zobacz to pytanie SO dot. Lucene używa listy pominiętych i to SO pytanie, dlaczego listy pomijane mogą być lepsze od B-drzew .
fnl