Jak działa Lucene

Chciałbym się dowiedzieć, jak działa wyszukiwarka lucene tak szybko. Nie mogę znaleźć żadnych przydatnych dokumentów w sieci. Jeśli masz coś do przeczytania (oprócz kodu źródłowego Lucene), daj mi znać.

Zapytanie tekstowe przy użyciu wyszukiwania tekstowego mysql5 z indeksem zajmuje w moim przypadku około 18 minut. Wyszukiwanie lucene dla tego samego zapytania zajmuje mniej niż sekundę.

Lucene to odwrócony indeks pełnotekstowy. Oznacza to, że pobiera wszystkie dokumenty, dzieli je na słowa, a następnie tworzy indeks dla każdego słowa . Ponieważ indeks jest dokładnie dopasowanym ciągiem, nieuporządkowanym, może być niezwykle szybki. Hipotetycznie, nieuporządkowany indeks SQL na varcharpolu może być równie szybki i myślę, że w takim przypadku duże bazy danych mogą bardzo szybko wykonać proste zapytanie o równość ciągów.

Lucene nie musi optymalizować pod kątem przetwarzania transakcji. Kiedy dodajesz dokument, nie musi się upewnić, że zapytania zobaczą go natychmiast . I nie musi optymalizować pod kątem aktualizacji istniejących dokumentów.

Jednak na koniec dnia, jeśli naprawdę chcesz wiedzieć, musisz przeczytać źródło. W końcu obie rzeczy, do których się odnosisz, są open source.

Lucene tworzy duży indeks. Indeks zawiera identyfikator słowa, liczbę dokumentów, w których słowo jest obecne, oraz pozycję słowa w tych dokumentach. Więc kiedy zadajesz zapytanie o jedno słowo, przeszukuje tylko indeks (złożoność czasowa O (1)). Następnie wynik jest oceniany przy użyciu różnych algorytmów. W przypadku kwerend składających się z wielu wyrazów po prostu weź przecięcie zbioru plików, w których występują słowa. W ten sposób Lucene jest bardzo szybki.

Aby uzyskać więcej informacji, przeczytaj ten artykuł autorstwa programistów Google - http://infolab.stanford.edu/~backrub/google.html

Jednym słowem: indeksowanie.

Lucene tworzy indeks twojego dokumentu, który pozwala na znacznie szybsze wyszukiwanie.

Jest taka sama różnica między strukturą danych listy O (N) a strukturą danych z tablicy skrótów O (1). Lista musi przejść przez całą kolekcję, aby znaleźć to, czego szukasz. Tabela skrótów ma indeks, który pozwala jej dokładnie ustalić, gdzie znajduje się żądany element i po prostu go pobrać.

Aktualizacja:

Nie jestem pewien, co masz na myśli, mówiąc „Wyszukiwania indeksu Lucene są dużo szybsze niż wyszukiwania indeksu mysql”.

Domyślam się, że używasz MySQL „GDZIE dokument LIKE '% fraza%'” do wyszukiwania dokumentu. Jeśli to prawda, MySQL musi wykonać skanowanie tabeli w każdym wierszu, który będzie O (N).

Lucene może przeanalizować dokument na tokeny, pogrupować je w n-gramach zgodnie z twoim kierunkiem i obliczyć indeksy dla każdego z nich. To O (1), aby znaleźć słowo w zindeksowanym dokumencie Lucene.

Lucene pracuje z częstotliwością terminów i odwrotną częstotliwością dokumentów . Tworzy indeks mapujący każde słowo z dokumentem i jego licznik częstotliwości, który jest niczym innym jak indeksem odwrotnym w dokumencie.

Przykład :

Plik 1: Pamięć o dostępie swobodnym jest pamięcią główną.

Plik 2: Dyski twarde to pamięć dodatkowa.

Lucene tworzy coś w rodzaju odwróconego indeksu

Plik 1:

Termin: losowy

Częstotliwość: 1

Pozycja: 0

Termin: pamięć

Częstotliwość: 2

Miejsce: 3

Miejsce: 6

Dzięki temu jest w stanie szybko wyszukiwać i odzyskiwać wyszukiwane treści. Jeśli dla zapytania wyszukiwania jest zbyt wiele dopasowań, zwraca wynik na podstawie wagi. Rozważ zapytanie wyszukiwania „Pamięć główna”, które wyszukuje wszystkie 4 słowa indywidualnie, a wynik będzie wyglądał następująco:

Główny

Plik 1: Częstotliwość - 1

Pamięć

Plik 1: Częstotliwość - 2

Plik 2: Częstotliwość - 1

Wynik byłby File1 następnie pliku Plik2 . Aby nie dać się ponieść wagom na najpopularniejszych słowach, takich jak „i”, „lub”, „the” bierze pod uwagę odwrotną częstotliwość dokumentu (tj. „Zmniejsza wagę słowa, które jest najpopularniejsze w zestawie dokumentów).