W jaki sposób dokumenty indeksu lucenu?

Question

Przeczytałem dokument o Lucene; także czytałem dokument pod tym linkiem (http://lucene.sourceforge.net/talks/pisa).

Nie bardzo rozumiem, jak Lucene indeksuje dokumenty i nie rozumie, jakie algorytmy używa Lucene do indeksowania?

na powyższy link, to mówi Lucene używa tego algorytmu do indeksowania:

• przyrostowe algorytm:
  • utrzymać stos indeksów segmentu
  • utworzyć indeks dla każdego dokumentu przychodzącego
  • popchnij nowe indeksy na stosie
  • niech b = 10 będzie czynnikiem scalającym ; 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; 
    } 
} 

Jak to algorytm zapewniają optymalną indeksowanie?

Czy Lucene używa algorytmu B-tree lub jakiegokolwiek innego algorytmu do indeksowania - czy ma konkretny algorytm?

Answer 1

To jest inverted index, ale to nie określa, której struktury używa. Index format in lucene ma pełne informacje.
Rozpocznij od "Podsumowanie rozszerzeń plików".

Po pierwsze zauważysz, że mówi o różnych indeksach. O ile mi wiadomo, żadne z nich nie używają ściśle mówiąc: B-tree, ale są podobieństwa - powyższe struktury przypominają drzewa.

Answer 2

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

Edycja 12/2014: Aktualizacja do zarchiwizowanej wersji ze względu na oryginalną zostać usunięty, prawdopodobnie najbardziej nowszych alternatywą jest http://lucene.apache.org/core/3_6_2/fileformats.html

Jest jeszcze nowsza wersja na 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ż starsza.

W skrócie, kiedy lucen indeksuje dokument, dzieli go na kilka terminów. Następnie przechowuje warunki w pliku indeksu, gdzie każdy termin jest powiązany z dokumentami, które go zawierają. Można by pomyśleć, że to trochę jak hashtable.

Warunki są generowane za pomocą analizatora, który wyłapuje każde słowo do jego formy głównej. Najbardziej popularnym algorytmem dla języka angielskiego jest algorytm Portera: http://tartarus.org/~martin/PorterStemmer/

Po wygenerowaniu zapytania jest przetwarzany za pomocą tego samego analizatora, który został użyty do zbudowania indeksu, a następnie użyty do wyszukania pasującego hasła (s) w indeksie. Zapewnia to listę dokumentów pasujących do zapytania.

Answer 3

Wydaje się, że twoje pytanie bardziej dotyczy scalania indeksu niż samego indeksowania.

Proces indeksowania jest dość prosty, jeśli ignorujesz szczegóły niskiego poziomu. Lucene tworzy z dokumentów tzw. "Indeks odwrócony". Więc jeśli dokument z tekstem „Być albo nie być”, a id = 1 przychodzi, wskaźnik odwrócony wyglądałby 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ące dane słowo. Każda linia tego indeksu (słowo) jest nazywana listą księgową. Ten indeks jest następnie przechowywany w magazynie długoterminowym.

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

• Lucene może pominąć kilka słów na podstawie konkretnego analizatora danej;
• słowa mogą być wstępnie przetworzone za pomocą algorytmu rozstrzygania w celu zmniejszenia flexii języka;
• lista księgowań może zawierać nie tylko identyfikatory dokumentów, ale także przesunięcie danego słowa wewnątrz dokumentu (potencjalnie kilka wystąpień) i kilka innych dodatkowych informacji.

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

Ważne jest, aby zrozumieć, że indeks Lucene to dołącz tylko. W pewnym momencie aplikacja decyduje się zatwierdzić (opublikować) wszystkie zmiany w indeksie. Lucene zakończy wszystkie operacje serwisowe indeksem i zamknie je, aby można było je przeszukiwać. Po indeksie commit w zasadzie niezmiennym. Ten indeks (lub część indeksu) nazywa się segment. Kiedy Lucene wykona wyszukiwanie zapytania, wyszukuje we wszystkich dostępnych segmentach.

Pojawia się zatem pytanie - jak możemy zmienić już zindeksowany dokument?

Nowe dokumenty lub nowe wersje już zaindeksowanych dokumentów są indeksowane w nowych segmentach i starych wersjach unieważnionych w poprzednich segmentach przy użyciu tak zwanej listy zabitych. Lista zabić jest jedyną częścią zatwierdzonego indeksu, która może ulec zmianie. Jak można się domyślić, wydajność indeksów spada z czasem, ponieważ stare indeksy mogą zawierać głównie usunięte dokumenty.

W tym miejscu pojawia się łączenie. Łączenie - to proces łączenia kilku indeksów w celu uzyskania bardziej wydajnego wskaźnika ogólnego. Zasadniczo dzieje się podczas scalania dokumentów na żywo skopiowanych do nowego segmentu i starych segmentów całkowicie usuniętych.

Korzystanie z tego prostego procesu Lucene jest w stanie utrzymać indeks w dobrej formie pod względem wydajności wyszukiwania.

Mam nadzieję, że pomoże.

Answer 4

W skrócie, Lucene tworzy odwrócone indeks pomocą Skip-Lists na dysku, a następnie ładuje się mapowanie indeksowanych względem do pamięci stosując Finite State Transducer (FST). Należy jednak zauważyć, że Lucene does not (necessarily) load all indexed terms to RAM, jak opisał Michael McCandless, autor systemu indeksowania Lucene sam.Zauważ, że korzystając z Skip-Lists, indeks może być przesuwany z jednego uderzenia do drugiego, dzięki czemu możliwe są takie opcje, jak zestaw, aw szczególności zakres zapytań (podobnie jak B-drzewa). Ponadto, Wikipedia entry on indexing Skip-Lists wyjaśnia również, dlaczego implementacja Skip-List Lucene jest nazywana wielopoziomową maską - w zasadzie, aby umożliwić O(log n) ponowne wyszukiwanie (ponownie, podobnie jak B-drzewa).

Kiedy indeks odwrócony (termin) oparty na numerze Skip-List data structure jest zbudowany z dokumentów, indeks jest przechowywany na dysku. Lucene następnie ładuje (jak już powiedziano: możliwe, tylko niektóre) te warunki do Finite State Transducer, w implementacji FST loosely inspired przez Morfologick.

Michael McCandless (również) ma dość dobre i lakoniczny pracy explaining how and why Lucene uses a (minimal acyclic) FST do indeksu terminy zapisanie ich Lucene w pamięci, przede wszystkim jako SortedMap<ByteSequence,SomeOutput> i daje podstawowy pomysł jak FSTS działa (tzn jak FST zagęszcza bajt sekwencje [tj. indeksowane terminy], aby wykorzystanie pamięci tego odwzorowania rosło pod liniami). I wskazuje na to, że Lucene również używa.

Dla ciekawskich, dlaczego Lucene używa Skip-Lists, podczas gdy większość baz danych używa (B +) - i/lub (B) -Tekstów, spójrz na the right SO answer w odniesieniu do tego pytania (Skip-Lists vs. B-Trees). Odpowiedź ta daje całkiem dobre, głębokie wyjaśnienie - zasadniczo, , a nie, tyle że powoduje równoległe aktualizacje indeksu "bardziej podatny" (ponieważ możesz zdecydować, aby nie przywracać równowagi B-drzewa natychmiast, uzyskując tym samym o tej samej równoczesnej wydajności jako lista pomijania), ale zamiast tego, Pomiń listy, nie musisz pracować na (opóźnione lub nie) operacji równoważenia (ostatecznie) potrzebne B-drzew (W rzeczywistości, jak pokazuje odpowiedź/odniesienia istnieje prawdopodobnie niewielka różnica w wydajności między drzewkami B i [wielopoziomowymi] listami pomijania, jeśli którekolwiek z nich są "zrobione poprawnie".)