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?
Odpowiedzi:
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.
źródło
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”).
źródło
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 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:
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.
źródło
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.
źródło