W jaki sposób Lucene indeksuje dokumenty?

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?

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.

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”).

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.

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.