Pierwsza na świecie wyszukiwarka: Wycieczka historyczna. Porównanie wyszukiwarek pełnotekstowych

Na tysiącach anonimowych witryn FTP. W tej odmianie użytkownikom dość trudno było znaleźć program odpowiedni do rozwiązania ich problemu.

Co więcej, nie wiedzieli z góry, czy narzędzie, którego szukają, istnieje. Dlatego musieliśmy ręcznie przeglądać magazyny FTP, których struktura była znacząco inna. To właśnie ten problem doprowadził do pojawienia się jednego z kluczowych aspektów nowoczesny świat- Wyszukiwarka internetowa.

Historia stworzenia

Uważa się, że twórcą pierwszej wyszukiwarki był Alan Emtage. W 1989 roku pracował na Uniwersytecie McGill w Montrealu, dokąd przeniósł się z rodzinnego Barbadosu. Jednym z jego zadań jako administratora wydziału technologii informatycznych uniwersytetu było wyszukiwanie programów dla studentów i nauczycieli. Aby ułatwić mu pracę i zaoszczędzić czas, Alan napisał kod, który za niego szukał.

„Zamiast tracić czas na wędrówkę po witrynach FTP i próbowanie dowiedzieć się, co się na nich znajduje, napisałem skrypty, które zrobiły to za mnie” – mówi Alan – „i zrobił to szybko”.

<поле>:<необязательный пробел><значение><необязательный пробел>
Nagrywać<поле>może przyjmować dwie wartości: User-agent lub Disallow. User-agent podał nazwę robota, dla którego opisana została polityka, a Disallow określił sekcje, do których odmówiono dostępu.

Na przykład plik z takimi informacjami uniemożliwia wszystkim robotom dostęp do adresów URL z /cyberworld/map/, /tmp/ lub /foo.html:

# robots.txt dla http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # To jest nieskończona wirtualna przestrzeń URL Disallow: /tmp/ # wkrótce znikną Disallow: /foo. HTML
Ten przykład blokuje dostęp do /cyberworld/map wszystkim robotom z wyjątkiem cybermappera:

# robots.txt dla http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # To jest nieskończona wirtualna przestrzeń URL # Cybermapper wie, dokąd się udać. Klient użytkownika: cybermapper Nie zezwalaj:
Ten plik „wdroży” wszystkie roboty, które będą próbowały uzyskać dostęp do informacji na stronie:

# odejdź Klient użytkownika: * Nie zezwalaj: /

Nieśmiertelny Archie

Archie, stworzony prawie trzydzieści lat temu, przez cały ten czas nie otrzymał żadnych aktualizacji. I oferował zupełnie inne doświadczenia z Internetem. Ale nawet dzisiaj możesz go używać do wyszukiwania potrzebnych informacji. Jednym z miejsc, w którym nadal działa wyszukiwarka Archie, jest Uniwersytet Warszawski. Co prawda większość plików znalezionych przez serwis pochodzi z 2001 roku.


Pomimo tego, że Archie jest wyszukiwarką, nadal oferuje kilka funkcji pozwalających dostosować wyszukiwanie. Oprócz możliwości określenia bazy danych (anonimowy FTP lub indeks polskiej sieci) system oferuje wybór opcji interpretacji wprowadzonego ciągu: jako podciąg, jako wyszukiwanie dosłowne lub Wyrażenie regularne. Masz nawet opcje wyboru wielkości liter i trzy opcje zmiany sposobu wyświetlania wyników: słowa kluczowe, opis lub linki.


Dostępnych jest także kilka opcjonalnych opcji wyszukiwania, które pozwalają na dokładniejszą identyfikację potrzebnych plików. Istnieje możliwość dodania słowa funkcyjne OR i AND, ograniczające obszar wyszukiwania plików do określonej ścieżki lub domeny (.com, .edu, .org itp.), a także ustalające maksymalną liczbę zwracanych wyników.

Chociaż Archie jest bardzo starą wyszukiwarką, nadal zapewnia dość zaawansowaną funkcjonalność podczas wyszukiwania potrzebnego pliku. Jednak w porównaniu do współczesnych wyszukiwarek jest niezwykle prymitywna. „Wyszukiwarki” poszły daleko do przodu - wystarczy rozpocząć wpisywanie żądanego zapytania, a system już oferuje opcje wyszukiwania. Nie wspominając już o zastosowanych algorytmach uczenia maszynowego.

Obecnie uczenie maszynowe jest jedną z głównych części Wyszukiwarki takie jak Google czy Yandex. Przykładem zastosowania tej technologii może być ranking wyszukiwania: ranking kontekstowy, ranking spersonalizowany itp. W tym przypadku bardzo często wykorzystywane są systemy Learning to Rank (LTR).

Uczenie maszynowe umożliwia także „zrozumienie” zapytań wprowadzanych przez użytkownika. Serwis samodzielnie poprawia pisownię, przetwarza synonimy, rozwiązuje problemy niejednoznaczności (co użytkownik chciał znaleźć, informacje o grupie Orły czy o Orłach). Wyszukiwarki samodzielnie uczą się klasyfikować witryny według adresu URL - bloga, zasobu wiadomości, forum itp., A także samych użytkowników, aby tworzyć spersonalizowane wyszukiwanie.

Prapradziadek wyszukiwarek

Archie dał początek wyszukiwarkom takim jak Google, więc w pewnym stopniu można go uznać za prapradziadka wyszukiwarek. To było prawie trzydzieści lat temu. Obecnie branża wyszukiwarek zarabia około 780 miliardów dolarów rocznie.

Jeśli chodzi o Alana Amtage’a, zapytany o straconą szansę na wzbogacenie się, odpowiada z pewną dozą skromności. „Oczywiście, że chciałbym się wzbogacić” – mówi. - Jednak nawet z wydanymi patentami mogę nie zostać miliarderem. Zbyt łatwo o nieścisłości w opisach. Czasami nie wygrywa ten, kto był pierwszy, ale ten, który staje się najlepszy.

Google i inne firmy nie były pierwsze, ale prześcignęły swoich konkurentów, tworząc wielomiliardowy przemysł.

Techniczne problemy tworzenia wyszukiwarka serwisu

    Stworzenie pełnoprawnej wyszukiwarki internetowej jest bardziej złożone, kosztowne i czasochłonne niż utworzenie dużej witryny internetowej.

    To stwierdzenie może wydawać się zaskakujące. Na wielu stronach można znaleźć formularze wyszukiwania w witrynie . Możesz odnieść wrażenie, że skoro formularz wyszukiwania w witrynie jest integralną częścią witryny, to powinien kosztować mniej niż sama witryna.

    To błędne przekonanie potwierdza fakt, że na wielu stronach można znaleźć oferty pobrania różnych skryptów i moduły oprogramowania, zapewniając wyszukiwanie w serwisie.

    Rzeczywiście, na stronie można pobrać i zainstalować formularz umożliwiający wprowadzenie do niej informacji oraz udostępniający uporządkowany zestaw informacji i linków. Ale tego formularza nie można jeszcze nazwać wyszukiwarką witryn. Prawie we wszystkich przypadkach przydatność, kompletność i dokładność uzyskanych wyników bardzo niski. Zamiast pozytywnego efektu instalacji wyszukiwarki, otrzymujesz efekt negatywny.

    Pojawienie się takich wyszukiwarek jest hołdem złożonym modzie. Klient chce mieć wyszukiwarkę. Nie wiedząc, jak oceniać wyniki wyszukiwarki, nie jest w stanie zrozumieć efektywności jej działania.

    W większości przypadków akceptacja i dostarczenie witryny zawierającej wyszukiwarkę wygląda mniej więcej tak. Projektant strony internetowej zaprasza klienta do wpisania słowa dostępnego na stronie i kliknięcia przycisku wyszukiwania. Jeśli wyszukiwarka zwraca wyniki, wszystko jest w porządku. Właściciel witryny jest zachwycony. Projektant stron internetowych milczy na temat dokładności i kompletności tych wyników.

Przykłady ilustrujące techniczną złożoność stworzenia skutecznej wyszukiwarki.

Przykład

    Strona poświęcona jest projektowaniu stron internetowych. Główny nacisk położony jest na tworzenie i przeprojektowywanie stron internetowych. Wyrażenie „tworzenie strony internetowej” pojawia się na stronie wielokrotnie, ale nie ma tam zwrotów „produkcja strony internetowej” ani „tworzenie strony internetowej”.

    Wymagane jest umieszczenie w serwisie wyszukiwarki. Algorytm wyszukiwania silnika opiera się na indeksowaniu tekstu znajdującego się w witrynie.Wyszukiwanie odbywa się za pomocą słów kluczowych i kluczowe frazy, zawarte w tekście indeksowanych plików. Podstawowa zasada oceny przydatności informacji tekstowych: częstotliwość występowania słowa kluczowe i frazy.

    Jeśli poprosisz o „tworzenie strony internetowej” lub „tworzenie strony internetowej”, wyszukiwarka nie zwróci żadnych wyników. W końcu na stronie nie ma takich zwrotów. Rozczarowany użytkownik opuści witrynę bez znalezienia potrzebnych informacji.

    Możesz usprawnić działanie wyszukiwarki. Ale w tym celu należy ręcznie skonfigurować wyszukiwarkę, wskazując, do których stron powinny zostać podane linki, jeśli tekst witryny nie zawiera żądanych słów kluczowych lub fraz, ale zawiera inne słowa i frazy o podobnym znaczeniu.

Przykład 2

    Słowo web design pojawia się na stronie wielokrotnie. Odwiedzający może błędnie wpisać: projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych itp. Wszystkie powyższe słowa kluczowe oznaczają to samo pojęcie, ale są zapisywane inaczej. Jednak wyszukiwarka może zgłosić, że nie znaleziono żadnych wyników.

    Gość może mieć na myśli „projektowanie stron internetowych”, ale prosi o inne słowa: studio internetowe, studio internetowe, studio internetowe, studio internetowe, studio internetowe, studio internetowe, studio internetowe, studio internetowe, mastering stron internetowych, studio projektowania stron internetowych, studio projektowe itp. .D. Jeśli podanych słów nie ma na stronie, wyszukiwarka zgłosi brak wyników.

    I w tym przypadku możesz usprawnić działanie wyszukiwarki. Aby to zrobić, należy ręcznie skonfigurować wyszukiwarkę, wskazując, do których stron powinny być podawane linki, jeśli tekst witryny nie zawiera żądanych słów kluczowych lub fraz, ale zawiera inne słowa i frazy o podobnym znaczeniu.

Przykład 3

    Ta sama strona i ta sama wyszukiwarka.

    Zamiast słowa „projektowanie stron internetowych” odwiedzający może błędnie wpisać: projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych, projektowanie stron internetowych itp. Jednak wyszukiwarka może zgłosić, że nie znaleziono żadnych wyników.

    W takim przypadku możesz także naprawić wyszukiwarkę. Wyszukiwarkę należy skonfigurować ręcznie, wskazując, do których stron powinny być podawane linki, jeśli tekst witryny nie zawiera żądanych słów kluczowych lub wyrażeń, ale zawiera inne słowa i wyrażenia o podobnym znaczeniu.

Uwaga:

    Każdy doświadczony użytkownik Internetu może podać wiele przykładów nieprawidłowego działania wyszukiwarek.

    To nie przypadek, że algorytm wyszukiwarki i ocena, na której się opiera na podstawie prośby, uwzględnia i analizuje wiele parametrów.

    Ręczny rozwój wyszukiwarki wymaga wysokiego poziomu umiejętności czytania i pisania, szerokich perspektyw, najwyższych kwalifikacji wykonawcy, głębokiej wiedzy temat biznesowy, monotonna, żmudna praca z wielokrotnym sprawdzaniem tego samego wyniku. Koszt ręcznego dostrojenia wyszukiwarki może być wielokrotnie wyższy niż koszt stworzenia witryny, dla której wyszukiwarka jest przeznaczona.

    Naturalnie przy tworzeniu większości serwisów biznesowych, z budżetem do 40 000 - 50 000 dolarów, ręczne dostrajanie wyszukiwarek nie jest opłacalne.

    Zwiększanie złożoności algorytmu wyszukiwarki z jednej strony może zwiększyć trafność, ale z drugiej strony może prowadzić do nowych błędów.

Streszczenie

    Stworzenie pełnoprawnej wyszukiwarki internetowej jest bardziej złożone, kosztowne i czasochłonne niż utworzenie dużej witryny internetowej.

    Istnieją proste, tanie, skuteczne i sprawdzone alternatywy. rozwiązania techniczne przeszukiwania witryn, które nie wymagają interwencji człowieka i nie nakładają rygorystycznych wymagań dotyczących kompatybilności oprogramowania i sprzętu z serwerem.

    Zastosowanie prostych rozwiązań obwodów pozwala odwiedzającemu szybko znaleźć potrzebne mu informacje, a w rezultacie zwiększyć zyski właściciela witryny.

Kiedy pracownik Netpikova staje przed zadaniem wymagającym czasu (na przykład stworzenie projektu Gwiazdy Śmierci lub zbudowanie kompaktowego urządzenia do zimnej fuzji), myśli przede wszystkim o tym, jak zautomatyzować tę pracę. Wyniki takich refleksji gromadzimy na specjalnej stronie naszego serwisu. Dzisiaj porozmawiamy o tym, jak w trzewiach agencji Netpeak rodzi się nowa przydatna usługa.

Dawno, dawno temu w odległej galaktyce postanowiliśmy zmienić wyszukiwarkę na stronie klienta, aby zwiększyć widoczność stron w bezpłatnych wynikach wyszukiwania.

Zadanie

Stworzono wyszukiwarkę projektu klienta, z którym musieliśmy pracować osobna strona na każdą prośbę. Ponieważ zapytania czasami zawierają literówki, zgromadziła się cała góra takich stron — zarówno poprawnych, jak i zawierających błędy. Ogólnie rzecz biorąc - ponad dwa miliony stron: po równo dla języka rosyjskiego i po angielsku. Strony z błędami zostały zaindeksowane i zatkały wyniki.

Naszym zadaniem było dopilnowanie, aby wszystkie opcje zapytania – zarówno prawidłowe, jak i z błędami – prowadziły na jedną stronę. Przykładowo dla każdego zapytania baseball, basaball, baaeball, baselball istniały osobne strony, ale należało się upewnić, że wszystkie opcje zbiegły się na jednej stronie z prawidłowe żądanie- baseball. W takim przypadku strona będzie odpowiadać prawidłowej formie zapytania i będziemy mogli pozbyć się śmieci w wynikach wyszukiwania.

Przykłady grup:

Warto zaznaczyć, że nie zawsze ufa się agencjom we wdrażaniu zmian w silniku serwisu. Dlatego jesteśmy wdzięczni naszemu klientowi za możliwość realizacji tego projektu.

Cel

Stwórz przejrzysty działający mechanizm umieszczania przekierowań ze stron zawierających frazy na stronę w serwisie klienta zawierającą poprawną frazę.

Jest to konieczne zarówno do usprawnienia przeszukiwania i indeksowania stron docelowych przez wyszukiwarki, jak i do budowania rdzeń semantyczny i wykorzystaj go w rozwoju nowa struktura strona. Oczywiście nie znaliśmy całkowitej liczby języków, w jakich wprowadzono zapytania, ale większość fraz była w języku rosyjskim i angielskim, więc skupiliśmy się na tych językach.

Jak narodziła się nowa metoda

Najprostszym rozwiązaniem, które od razu przychodzi na myśl, jest wpisanie zapytania w Google, a on rzetelnie nam je poprawi. Ale zorganizowanie takiej penetracji jest przedsięwzięciem dość kosztownym. Dlatego ja i moi towarzysze wybraliśmy inną drogę. Nasz matematyk analityczny zdecydował się zastosować podejście lingwistyczne (niespodziewanie!) i zbudować model językowy.

Co to znaczy? Określamy prawdopodobieństwo napotkania słowa w danym języku i dla każdego słowa obliczamy prawdopodobieństwo popełnienia w nim różnych błędów. Wszystko byłoby w porządku, a teoria tutaj jest piękna, ale aby zebrać takie statystyki, musisz mieć ogromny korpus tekstowy ze znacznikami dla każdego języka (znowu wyszukiwarki są najbliżej tego). Naturalnie pojawiły się pytania, jak to zrobić i kto to wszystko zaimplementuje w kodzie. Nikt wcześniej czegoś takiego nie zrobił (jeśli znasz przypadek, wrzuć link w komentarzu), więc metodologię opracowano od podstaw. Pomysłów było kilka i nie było z góry wiadomo, który z nich będzie lepszy. Dlatego spodziewaliśmy się, że rozwój będzie prowadzony cyklicznie – przygotowanie pomysłu, wdrożenie, przetestowanie, ocena jakości, a następnie podjęcie decyzji, czy dalej udoskonalać pomysł, czy nie.

Wdrożenie technologii można podzielić na trzy etapy. Przeczytaj więcej o każdym z nich.

Etap nr 1. Formacja problemu. Pierwsza graba

Uwaga! Po tej linijce będzie wiele terminów, które staraliśmy się wyjaśnić możliwie najprostszym językiem.

Ponieważ nie było dostępnych dodatkowych informacji (słowniki, częstotliwości, logi), próbowano rozwiązać problem przy pomocy zasobów, którymi dysponowaliśmy. Próbowaliśmy różne metody grupowanie. Główną ideą jest to, że słowa z tej samej grupy nie powinny się zbytnio różnić.

Grupowanie- procedura, która zbiera dane zawierające informacje o próbie obiektów, a następnie porządkuje obiekty w stosunkowo jednorodne grupy.

Odległość Levenshteina pokazuje minimalną liczbę zmian (usunięć, wstawień i zamian) w wierszu A, które należy wprowadzić, aby uzyskać wiersz B.

  • Zastąpienie symbolu: sh[e]res — sh[i]res, sh[o]res;
  • Wstawienie symbolu: sheres - s[p]heres;
  • Usunięcie: gol[d][f] - golf, złoto.

W każdym z przykładów odległość między błędnie napisanym słowem a poprawną formą wynosi 1 korektę.

Współczynnik Jaccarda w bi- i trygramach pomaga dowiedzieć się, ile wspólnych kombinacji dwu- lub trzyznakowych sylab mają ciągi A i B.

Przykład: Rozważmy linie A = snowboard i B = border. Ogólny wzór na współczynnik dla bigramów to:

J = (liczba identycznych bigramów dla A i B) / ( Łączna biggramy w A i B)

Podzielmy linie na biggramy:

bigramy dla A = ( sn, no, ow, wb, bo+, oa, ar, rd+ ) - 8 sztuk; bigramy dla B = ( bo+, or, rd+, de, er ) - 5 sztuk; Istnieją dwa identyczne bigramy oznaczone znakami plus - bo i rd.

W przypadku trygramów będzie podobnie, tyle że zamiast dwóch liter zostaną użyte trzy. Współczynnik Jaccarda będzie dla nich następujący:

Przykład większej liczby podobnych słów:

A = baseball i B = baaeball ( ba+, as, se, eb+, ba+, al+, ll+ ) ( ba+, aa, ae, eb+, ba+, al+, ll+ ) J = 5 / (7 + 7 - 5) = 0,56

Chociaż współczynnik Jaccarda działa szybciej, nie uwzględnia kolejności sylab w słowie. Dlatego też używano jej głównie do porównań z odległością Levenshteina. Teoretycznie wszystko było tutaj proste. Techniki grupowania małych danych są dość łatwe do rozwiązania, jednak w praktyce okazało się, że aby dokończyć podział, albo ogromne moc obliczeniowa lub lata (a najlepiej jedno i drugie). W ciągu dwóch tygodni pracy powstał skrypt w Pythonie. Po uruchomieniu czyta frazy z pliku i listy grup wyjściowych do innego pliku. Jednocześnie, jak każdy program, skrypt ten ładował procesor i wykorzystywał pamięć RAM.

Większość testowanych metod wymagała terabajtów pamięci i tygodni czasu procesora. Dostosowaliśmy metody tak, aby program potrzebował 2 gigabajtów pamięci i jednego rdzenia. Jednak milion wniosków zostało przetworzonych w ciągu około 4-5 dni. Zatem czas realizacji zadania nadal pozostawiał wiele do życzenia. Wynik algorytmu można przedstawić w postaci wykresu na małym przykładzie:

W przypadku zastosowania do projektu klienta oznacza to, że strony pasujące do żądań w tym samym klastrze zostaną sklejone razem z przekierowaniem 301. Pamiętajmy, że naszym celem było stworzenie przejrzystego działającego mechanizmu umieszczania przekierowań ze stron zawierających frazy z błędami na stronę witryny klienta zawierającą poprawną frazę. Ale nawet w tym przykładzie niedociągnięcia są oczywiste:

  1. Nie jest jasne, jak znaleźć odpowiednie formularze z grup i czy w ogóle one tam są.
  2. Nie wiadomo, jakie progi błędu zastosować. Jeśli próg będzie duży (więcej niż 3 błędy), wówczas grupy będą bardzo duże i zaśmiecone, jeśli będzie za mały, wówczas każde słowo utworzy własną grupę, co również nam nie odpowiadało. Nie da się znaleźć jakiegoś uniwersalnego znaczenia akceptowalnego dla wszystkich grup.
  3. Nie jest jasne, co zrobić ze słowami, które można jednocześnie podzielić na kilka grup.

Etap nr 2. Uproszczenie. Nowa nadzieja

Przeprojektowaliśmy algorytm, przybliżając go do tradycyjnych mechanicznych korektorów gramatycznych. Na szczęście jest ich wystarczająco dużo. Jako bazę wybrano bibliotekę Pythona Enchant. W tej bibliotece znajdują się słowniki dla niemal każdego języka świata, jest ona dość prosta w obsłudze i można uzyskać wskazówki, co należy poprawić. Podczas poprzedniego etapu dowiedzieliśmy się wiele o rodzajach zapytań i w jakich językach mogą być te zapytania.

Z otwarty dostęp Zebrano następujące słowniki:

  • Angielski brytyjski);
  • angielski (USA);
  • Niemiecki;
  • Francuski;
  • Włoski;
  • Hiszpański;
  • Rosyjski;
  • Ukraiński.
  1. Jeżeli jest poprawny (znajduje się w którymś ze słowników) to zostawiamy tak jak jest;
  2. Jeśli jest błędny, otrzymujemy listę wskazówek i wybieramy pierwszą, która się pojawi;
  3. Wszystkie słowa łączymy w jedno zdanie. Jeśli nie spotkaliśmy się wcześniej z taką frazą, to tworzymy dla niej grupę. Poprawiona forma frazy staje się jej „centrum”. Jeśli tak, oznacza to, że to wyrażenie ma już swoją grupę i dodajemy tam nową błędną formę.

W rezultacie otrzymaliśmy centrum grupy i listę słów z tej grupy. Tutaj oczywiście wszystko jest lepsze niż za pierwszym razem, ale pojawiło się ukryte zagrożenie. Ze względu na specyfikę projektu w zapytaniach pojawia się duża ilość nazw własnych. Pojawiają się imiona i nazwiska osób, miast, organizacji, obszarów geograficznych, a nawet łacińskie nazwy dinozaurów. Oprócz tego znaleźliśmy słowa z nieprawidłową transliteracją. Dlatego nadal szukaliśmy sposobów rozwiązania problemu.

Etap nr 3. Suplementy i Przebudzenie Mocy

Problem transliteracji został rozwiązany dość prosto i tradycyjnie. Po pierwsze, stworzyliśmy słownik korespondencji pomiędzy literami cyrylicy i alfabetu łacińskiego.

Zgodnie z nią każda litera w sprawdzanym wyrazie została przekształcona i odnotowano, czy w powstałym słowie nastąpiła korekta słownikowa. Jeśli opcja transliteracji miała najmniej błędów, to wybieraliśmy ją jako poprawną. Ale nazwy własne to orzech do zgryzienia. Najprostszą opcją na uzupełnienie słowników okazało się zbieranie słów ze zrzutów Wikipedii. Wiki ma jednak także swoje słabe strony. Jest tam sporo błędnie napisanych słów, a metoda ich filtrowania nie jest jeszcze idealna. Stworzyliśmy bazę danych słów rozpoczynających się z dużej litery i bez znaków interpunkcyjnych przed nimi. Te słowa stały się naszymi kandydatami na nazwy własne. Przykładowo po przetworzeniu takiego tekstu do słownika dodano podkreślone słowa:

Podczas wdrażania algorytmu okazało się, że wyszukiwanie wskazówek w rozszerzonym słowniku Enchant wymagało czasami więcej niż 3 sekundy na słowo. Aby przyspieszyć ten proces, wykorzystano jedną z implementacji automatu Levenshteina.

Krótko mówiąc, idea maszyny polega na tym, że budujemy schemat przejścia, korzystając z istniejącego słownika. Jednocześnie wiemy z góry, ile poprawek w słowach będzie dla nas akceptowalnych. Każde przejście oznacza, że ​​dokonujemy pewnego rodzaju przekształcenia liter w słowie – pozostawiamy literę lub stosujemy jeden z rodzajów korekty – skreślenie, zamianę lub wstawienie. A każdy wierzchołek jest jedną z opcji zmiany słowa.

Załóżmy teraz, że mamy słowo, które chcemy sprawdzić. Jeśli jest w nim błąd, musimy znaleźć wszystkie formy sprostowania, które nam odpowiadają. Konsekwentnie zaczynamy poruszać się według schematu, przeglądając litery sprawdzanego słowa. Kiedy skończą się litery, znajdziemy się w jednym lub kilku wierzchołkach, a oni pokażą nam opcje poprawnych słów.

Obrazek przedstawia maszynę do słowa jedzenie ze wszystkimi dwoma możliwymi błędami. Strzałka w górę oznacza wstawienie znaku w bieżącej pozycji. Strzałka po przekątnej z gwiazdką oznacza zamianę, strzałka z epsilonem oznacza usunięcie, a strzałka pozioma oznacza, że ​​litera pozostaje niezmieniona. Użyjmy słowa fxood. Będzie to odpowiadać ścieżce w maszynie 00-10-11-21-31-41 - co jest równoznaczne z wstawieniem litery x po f do słowa food.

Dodatkowo wykonaliśmy dodatkowe prace mające na celu poszerzenie gromadzonych słowników głównych, automatyczne odfiltrowanie z góry fraz pozasłownikowych (nazwy modeli produktów i różne identyfikatory), wprowadziliśmy transliterację i wyszukiwanie w dodatkowym słowniku.

Jaki jest wynik?

Wciąż pracujemy nad ulepszeniem algorytmu, ale już na na tym etapie rozwoju, mamy narzędzie, które może oczyścić śmieci, takie jak chmury tagów, i scalić przekierowania 301 niepotrzebne strony. Takie narzędzie będzie szczególnie skuteczne w przypadku niewielkiej liczby błędnie napisanych słów, ale daje też całkiem zadowalające wyniki na dużych tablicach. Pośrednia wersja skryptu została wysłana do klienta w celu utworzenia bloku linkującego. Z tego bloku będzie można zbierać Dodatkowe informacje o korektach zapytań. Nie przesłaliśmy do realizacji pełnych wyników skryptu, ponieważ wciąż pracujemy nad poprawą jakości skryptu.

Stworzenie kodu i jego przetestowanie zajęło łącznie 40 godzin pracy matematyka-analityka. Wniosek: jeśli pewnego dnia będziesz musiał przetworzyć około dwóch milionów żądań, nie rozpaczaj. Takie zadania można zautomatyzować. Oczywiste jest, że osiągnięcie 100% dokładności będzie bardzo trudne, ale możliwe jest prawidłowe przetworzenie co najmniej 95% informacji.

Klasyfikacja

Według obszaru wyszukiwania (warunkowo)

Lokalny

Zaprojektowany do wyszukiwania informacji na temat dowolnej części ogólnoświatowa sieć na przykład w jednej lub większej liczbie witryn albo w sieci lokalnej.

Światowy

Zaprojektowany do wyszukiwania informacji w całym Internecie lub jego znacznej części. Przedstawicielami takich wyszukiwarek są wyszukiwarki Google, Yandex itp. Wyszukiwarki wyszukują informacje różne rodzaje, na przykład teksty, filmy, obrazy, obiekty geograficzne, dane osobowe itp. W tym przypadku pliki, z którymi może pracować wyszukiwarka, mogą mieć format tekstowy (na przykład .html, .htm, .txt, . doc, .rtf...) i grafikę (.gif, .png, .svg...) lub multimedia (wideo i dźwięk). Na razie najczęstszym sposobem jest przeszukiwanie dokumentów tekstowych.

Wyszukiwana fraza

Początkową informacją dotyczącą wyszukiwania jest zapytanie wyszukiwania.

Funkcje

Wyszukiwarki spełniają kilka funkcji:

Wyszukaj linki

Szukaj łączy do stron i innych dokumentów witryny.

Automatyczny

Tryb ręczny

Użytkownicy sami dodają linki do stron swoich serwisów do bazy wyszukiwarki

Indeksowanie dokumentów serwisu

Wyodrębnianie informacji istotnych dla wyszukiwania z dokumentów, konwertowanie tych informacji na format przyjazny dla wyszukiwarek i przechowywanie tych informacji w bazie danych wyszukiwarki

Przeszukaj bazę zaindeksowanych dokumentów

Może składać się z kilku etapów

Znajdowanie dokumentów pasujących do wyszukiwanego hasła

Ranking dokumentów według ich trafności dla zapytań

Grupowanie dokumentów

Notatki

Zobacz też


Fundacja Wikimedia. 2010.

Zobacz, czym jest „wyszukiwarka” w innych słownikach:

    Wyszukiwarka- (wyszukiwarka): serwer WWW indeksujący strony internetowe dostępne serwery(na przykład Yandex)... Źródło: ZASOBY INTERNETOWE. WYMAGANIA DOSTĘPNOŚCI DLA OSÓB NIEWIDZĄCYCH. GOST R 52872 2007 (zatwierdzony rozporządzeniem Rostekhregulirovaniya z dnia... ... Oficjalna terminologia

    wyszukiwarka- Serwer WWW indeksujący strony internetowe na dostępnych serwerach (na przykład Yandex). [GOST R 52872 2007] Tematy technologia informacyjna w ogóle EN wyszukiwarka ... Przewodnik tłumacza technicznego

    W Internecie specjalna witryna internetowa, na której użytkownik na określone żądanie może otrzymać linki do stron odpowiadających temu żądaniu. System wyszukiwania składa się z trzech elementów: 1 robota poszukiwawczego; 2 indeksy systemowe; i 3 programy,... ... Słownik finansowy

    W Internecie wyszukiwarka, która: wysyła żądanie wyszukiwania do kilku wyszukiwarek; i generuje podsumowanie (na jednej stronie) otrzymanych odpowiedzi. W języku angielskim: Meta wyszukiwarka Synonimy: Meta caterpillar Angielskie synonimy: Metacrawler... ... Słownik finansowy

    Artykuł ten należy całkowicie przepisać. Na stronie dyskusji mogą znajdować się wyjaśnienia. Wyszukiwarka programowo kompleks sprzętowy z interfejsem internetowym, który zapewnia możliwość... Wikipedii

    System wyszukiwania- – (wyszukiwarka angielska, synonimy: wyszukiwarka, serwer wyszukiwania, wyszukiwarka) – narzędzie służące do wyszukiwania informacji w Internecie. Z reguły praca wyszukiwarki składa się z dwóch etapów. Specjalny program (szukaj robota, karabin maszynowy, agent,... ... Encyklopedyczny Słownik Mediów – Wyszukiwarka to serwis WWW umożliwiający wyszukiwanie informacji w Internecie. Większość wyszukiwarek szuka informacji na stronach internetowych Sieć WWW, ale są też systemy, które potrafią wyszukiwać pliki serwery FTP, towary w... ...Wikipedii

Książki

  • Na temat efektywności wyszukiwania konkretów w Internecie I. A. Semenov. Według badań Berkley ilość informacji w Internecie w 2003 roku szacowana była na 258,85 terabajtów i są to wyłącznie dane publicznie dostępne. Według Internet World Stats wzrost... eBook
  • Indeksy można tworzyć wyłącznie na polach tabel MyISAM.
  • Rozmiar indeksu jest w przybliżeniu o połowę mniejszy od rozmiaru danych. Trzeba jednak pamiętać, że nie da się wyłączyć zapisywania samych tekstów, więc do tych 50% trzeba doliczyć kolejne 100% – dane zostaną zapisane.
  • Szybkość indeksowania jest przyzwoita w czystej postaci, około 1,5 MB/s. Oczywiste jest, że nadal musisz przepuścić go przez łodygę. Jeśli wypełnisz indeks, pobierając w locie dane z tej samej bazy danych i przepuszczając je przez port Perla rosyjskiego rdzenia Snowball, otrzymasz 314 KB/s. Tak naprawdę MySQL ma architekturę umożliwiającą łączenie stemmerów z wtyczkami („wtyczki do analizatora pełnotekstowego”), ale jakoś nie ma samych wtyczek... :)
  • Nie ma wbudowanego rdzenia, wbudowane są angielskie słowa stop, nie można dodawać własnych. Domyślnie wyszukiwaniem logicznym jest „OR”, więc aby wyszukiwać za pomocą „AND”, musisz zamienić każde słowo na „+słowo”.
  • Istnieją dwa tryby wyszukiwania – logiczne i normalne („język naturalny”). Wyszukiwanie logiczne po prostu sprawdza, czy w dokumencie znajdują się słowa i obsługuje je operacje logiczne, fraz i wyszukiwań prefiksów, ale nie zwraca wyniku trafności (tylko 0 lub 1). Regularne wyszukiwanie może mieć znaczenie, ale nie operatory. Dlatego, aby obsłużyć oba, musisz uruchomić to samo żądanie w dwóch trybach.
    • Wyszukiwanie prefiksów w MySQL uroczy powolny. W przypadku kilku słów rozwiniętych w przedrostki może to z łatwością zająć 15 lub 40 sekund. Więc w ogóle nie trzeba go używać.
  • Nie może wyszukiwać w kilku polach jednocześnie - to znaczy, że składnia MATCH() na to pozwala, ale nie następuje optymalizacja wyszukiwania, ale następuje pełne skanowanie. Dlatego lepiej napisać (wybierz id gdzie mecz(pole1) ...) UNION (wybierz id gdzie mecz(pole2) ...) .
  • Szybkość wyszukiwania zapytań pochodzących z losowych tytułów błędów, z limitem znalezionych 1000:
    • W 5 wątkach na 3 słowach - średnio 175 ms, maksymalnie 3,46 sekundy.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników jest takich samych.
    • W 5 wątkach na 2 słowach - średnio 210 ms, maksymalnie 3,1 sek.
    • W 1 wątku na 3 słowach - średnio 63 ms, maksymalnie 764 ms.
    • Zależy głównie od znalezionej ilości.
  • Główną zaletą jest obecność wyszukiwania „iskrowego”.

Sfinks (2.0.1-beta)

  • Oddzielny serwer wyszukiwania. Istnieją dla niego biblioteki interfejsów dla wielu różnych języków. Bardzo fajnie, że w wersji 0.9.9 oprócz „natywnego” interfejsu pojawił się SphinxQL - interfejs SQL do Sphinxa wykorzystujący protokół MySQL, czyli korzystający ze zwykłych klientów MySQL.
  • Początkowo w Sphinxie nie było aktualizowanych (w czasie rzeczywistym) indeksów; jedyne, co mógł zrobić, to zbudować cały indeks, a następnie go przeszukać.
  • Nadal nie wie, jak poprawnie zaktualizować/usunąć dokumenty w indeksie, dodaje tylko normalnie. Usunięcie następuje poprzez zaznaczenie checkboxu „stary wpis”, a następnie każdorazowe usunięcie go ze wszystkich wyników wyszukiwania.
  • Indeksy czasu rzeczywistego nie obsługują wszystkiego - na przykład nie obsługują przedrostków/wrostków i MVA.
  • Trochę bałaganu z interfejsami i funkcjami: aktualizacja indeksu w czasie rzeczywistym tylko poprzez SphinxQL; składnia wyszukiwania jest inna we wszystkich trzech interfejsach (zwykły, SphinxQL, SphinxSE); kawałki 5 trybów wyszukiwania, z czego 4 są przestarzałe; indeksator nie może odbudować indeksów w czasie rzeczywistym; Niemożliwe jest SKRÓCENIE indeksu przy użyciu SphinxQL i nie można zobaczyć, ile rekordów znajduje się w indeksie...
  • Na tym kończą się wady - jest serwer wyszukiwania, z którym można się komunikować za pomocą własnego protokołu lub protokołu MySQL, masa różnych możliwości, indeksowania i wyszukiwania bardzo szybko, wielkość indeksu to około 1/3 danych. Może wzrosnąć 2-krotnie, jeśli włączysz indeksowanie dokładnych form wyrazów.
  • Wbudowane rdzenie rosyjskie, angielskie i czeskie oraz preprocesory Soundex i Metaphone (do porównywania angielskich słów według dźwięku). Można również podłączyć stemmery dla innych języków, wystarczy je zbudować za pomocą klucza --with-libstemmer. Oczywiście istnieje obsługa słów stop. Synonimy też, i są zwykłe, i istnieją „wyjątki tokenizujące”, które mogą zawierać znaki specjalne. Istnieją również „blend_chars” – znaki, które są uważane zarówno za ograniczniki, jak i część słów – na przykład tak, że „AT&T” staje się słowami „AT”, „T” i „AT&T”.
  • Wśród ciekawych, nietypowych funkcji - może wykonywać wyszukiwanie infiksowe (dla tych, którzy chcieli szybko wyszukiwać według podciągu!), Pola wielowartościowe (MVA), może indeksować według akapitów i zdań, a nawet według zawartości predefiniowanych tagów HTML. Może także wyróżniać wyszukiwane słowa w cudzysłowie i wiele więcej. Jednak MVA i infiksy nie są (jeszcze?) obsługiwane w zaktualizowanych indeksach.
  • Indeksowanie jest bardzo szybkie - prędkość sieci przy indeksowaniu w czasie rzeczywistym wynosi 6,7 MB/s (pobieranie zrzutu SQL), przy zwykłym indeksie - ogólnie 12 MB/s (pobieranie zrzutu xmlpipe2). „Nieczysta” prędkość (z Perla, z bieżącym odczytem danych z MySQL) - 4,5 MB/s. W przypadku infiksów wszystko naturalnie znacznie spowalnia - 440 KB / s, sterta we/wy wynosi 10,5 GB, a indeks okazuje się mieć rozmiar 3 GB dla 330 MB danych.
  • Wyszukiwanie jest zazwyczaj reaktywne:
    • W 5 wątkach na 3 słowach - średnio 7 ms, maksymalnie 75 ms.
    • W 5 wątkach na 2 słowach - średnio 7 ms, maksymalnie 81 ms.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników wynosi średnio 5 ms, maksymalnie 57 ms.
    • W 1 wątku na 3 słowach - średnio 2 ms, maksymalnie 35 ms.

Xapian (1.2.6)

  • Biblioteka, nie ma gotowego serwera wyszukiwania. Interfejs API C++ jest całkiem rozsądny. Wydaje się, że wspiera pracę konkurencyjną (wielu czytelników, jeden pisarz).
  • Wiele dostępnych wiązań dla inne języki: C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua.
  • Indeks jest indeksem opartym na odwróconym drzewie B.
  • Fajną rzeczą jest to, że Xapian nie musi być używany specjalnie jako indeks pełnotekstowy - w rzeczywistości jest to po prostu implementacja indeksu odwróconego, którego można używać według własnego uznania, ponieważ nie ma ograniczeń dotyczących „słów” zawartych w dokumencie, z wyjątkiem limitu długości wynoszącego 245 bajtów. Teoretycznie można go używać jako bazy danych.
  • Szczerze mówiąc kiepska dokumentacja. Coś w rodzaju zbioru informacji, który nie zawiera jeszcze wszystkiego. Aby zrozumieć niektóre punkty, musisz głupio wejść do kodu. Zrobiłem się bezczelny i nawet umieściłem błąd w tym temacie - błąd 564. Cóż, to prawda - silnik wydaje się być całkiem niezły, ale niewiele osób o tym wie.
  • Zabawne, że kiedy zacząłem to testować, znalazłem dziwny błąd - segfault w libuuid, który nie pozwala na utworzenie bazy danych, jeśli Image::Magick jest ładowany równolegle. Okazało się, że nie był to nawet błąd ImageMagick, ale jeszcze poważniejszy - był to błąd libc6! W wersjach 2.12 i 2.13 inicjalizacja Thread-Local Storage podczas dynamicznego ładowania bibliotek jest zepsuta, och, jak. Zostało to naprawione w wersji 2.14, ale Debian nadal ma wersję 2.13. Dodałem błąd 637239 do Debiana (są też linki do błędów w Gentoo i samej bibliotece libc).
  • Wiązania Perla wymagają wykończenia, aby móc wybrać backend i domyślnie nie jest to najnowszy Brass, ale stabilny Chert. Wykończenie jest łatwe. Dałem im też błąd w tym temacie - błąd 565.
  • Wydaje się, że indeks nie obsługuje różnych pól, ale można to zrobić poprzez dodanie przedrostków na początku każdego słowa: http://xapian.org/docs/omega/termprefixes.html
    • To jest „oficjalne podejście”, Xapian może to zrobić sam, wystarczy podać prefiksy.
    • Takie podejście ma przynajmniej jedną małą wadę - domyślnie zapytanie nie przeszukuje wszystkich pól, a aby przeszukać wszystkie, należy ręcznie wstawić do zapytania OR.
    • Tak, dokumentacja znowu jest niekompletna i nie na właściwym miejscu - powinna być w instrukcji Xapiana, ale jest w instrukcji Omega, która jest gotową, prostą wyszukiwarką CGI.
    • Nieprzyjemny moment - szybko odnaleziony błąd w parserze zapytań - błędnie generuje terminy do wyszukiwania rdzeni wyrazów w polach (które posiadają przedrostki). Indeksator przypisuje wszystkim tematom na początku przedrostek „Z”, co oznacza, że ​​rdzeń słowa „idea” w tytule (powiedzmy przedrostek T) jest indeksowany jako „ZTide”. A parser zapytań próbuje wyszukiwać według „Tida” i oczywiście nic nie znajduje. Dałem im błąd 562 w tym temacie. W rzeczywistości naprawiono jedną linią.
  • Stemmers jest wbudowany dla 15 języków, jak zwykle, generowanych z Snowballa. a. Jest wsparcie dla słów przerywanych (oczywiście) i synonimów. Co jeszcze ciekawsze - może poprawiać literówki bez korzystania ze słowników, a jedynie w oparciu o zaindeksowane dane ( musi być włączone poprzez ustawienie). Oznacza to, że np. dla „Xapain” będzie szczerze sugerować „Xapian”. Dostępna jest także obsługa wyszukiwania „niedokończonego zapytania”, czyli podpowiedzi przy wprowadzaniu zapytania litera po literze Zasadniczo jest to po prostu dodanie * do ostatniego słowa w wyszukiwaniu, ale z uwzględnieniem niuansów składni zapytania.
  • Istnieje również „Wyszukiwanie fasetowe” - obliczanie wartości zagregowanych dla wszystkich lub prawie wszyscy znalezione dokumenty (powiedzmy z limitem 10 000). Oznacza to, że te 10 000 dokumentów nie zostanie Ci zwrócone, ale zostaną sprawdzone i obliczona zostanie z nich pewna łączna wartość. Przykładowo, możesz w ten sposób zwrócić 10 wyników (strony) i jednocześnie odpowiedzieć na pytanie „z jakich kategorii znaleziono dokumenty?”
  • Kiepskie jest to, że jeśli podczas indeksowania raz na 256 błędów wykonasz funkcję Flush() (commit), to prędkość z ~1,5 MB/s spadnie do 412 KB/s, a liczba operacji we/wy znacznie wzrośnie - o 10-20 czasy. W zasadzie jest to określone i logiczne dla każdego odwróconego indeksu - o wiele bardziej optymalne jest kumulowanie zmian niż próba aktualizacji pojedynczo, ponieważ liczba aktualizowanych tokenów wzrasta.
  • Rozmiar indeksu - piszą, że jest w przybliżeniu równy rozmiarowi danych, tak nie jest, w rzeczywistości jest 2 razy większy. Piszą, że jeśli nie przechowujesz pozycji słów w dokumentach, tak będzie stać się 2 razy mniejsza. Ale przepraszam, Sphinx przechowuje także pozycje, a jego indeks to 2 razy mniej danych. Jeśli uruchomisz xapian-compact (defragmentacja bazy danych) - tak, indeks maleje, ale nadal pozostaje około 1,7 razy więcej danych.
    • Tak, powód został znaleziony - Xapian zawsze indeksuje zarówno podstawy, jak i dokładne formy słów. Nie da się wyłączyć indeksowania dokładnych formularzy, szkoda, dałem im błąd 563 w tym temacie.
  • Wyszukuje szybko. Przetestowałem to w ten sposób: wyszukałem kilka sąsiadujących ze sobą słów o długości co najmniej 2 znaków w trybie STEM_ALL, wziętych z tytułów błędów (szukałem nie „OR”, ale „AND”) i zastąpiłem każde słowo with (słowo OR tytuł: słowo LUB prywatne: słowo), czyli wyszukiwanie w trzech polach zamiast w jednym, ograniczyło liczbę wyników do 1000.
    • W 5 wątkach na 3 słowach - średnio 14 ms, maksymalnie 135 ms.
    • W 5 wątkach na 2 słowach - średnio 29 ms, maksymalnie 137 ms.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników wynosi średnio 2 ms, maksymalnie 26 ms.
    • W 1 wątku na 3 słowach - średnio 7 ms, maksymalnie 51 ms.
    • Szybkość wyszukiwania zależy głównie od liczby znalezionych wyników, im więcej, tym dłużej trwa wyszukiwanie.

Xapian posiada 3 backendy (implementacje samego indeksu) - według nowości Flint, Chert i Brass. To tak jak w Debianie oldstable, stabilnym i testowym :) w wersji 1.2.x domyślnym backendem jest Chert. Przed Flintem był Quartz.

Wyszukiwanie tekstowe PostgreSQL (9.1)

  • Indeks jest odwracany w oparciu o GIN (Generalized Inverted iNdex). Wcześniej nazywany Tsearch2, stworzony przez Olega Bartunova i Fedora Sigaeva.
  • Istnieją wbudowane rdzenie, obsługa słów kończących, synonimów, tezaurus (coś w rodzaju słownika pojęć, zastępuje słowa innymi „preferowanymi”), słowniki ISpell (choć podobno są strasznie powolne podczas inicjalizacji).
  • Podczas indeksowania do każdego leksemu można dołączyć „wagę”, która w rzeczywistości nie jest „wagą”, ale odpowiednikiem prefiksu Xapian, czyli nazwą pola, z którego leksem pochodzi. Takie „wagi” mogą być tylko 4 - A, B, C, D i w przyszłości można ich używać podczas wyszukiwania. Przykład konstrukcji tsvector "a z dwóch pól z "wagami": setweight(to_tsvector(coalesce(title,""), "A") || setweight(to_tsvector(coalesce(keyword,"")), "B") .
  • Jeść oddzielny funkcje rankingowania wyników i podświetlania wyszukiwanych słów w cytatach. Rankingu można dokonać poprzez przypisanie wag liczbowych do powyższych „wag” ABCD (które stanowią „pola”). Ponadto domyślnie wagi są równe (0,1, 0,2, 0,4, 1,0).
  • Indeksowany typ danych nazywany jest tsvector (wektor wyszukiwania tekstu). PostgreSQL umożliwia tworzenie indeksów funkcjonalnych, a domyślna instrukcja sugeruje utworzenie właśnie takich - CREATE INDEX i ON t USING gin(to_tsvector(<поле>)). Oto więc: nie rób tego! W przeciwnym razie będziesz bardzo niemile zaskoczony szybkością realizacji żądań. Pamiętaj, aby utworzyć osobną kolumnę typu tsvector , dodać do niej tsvector „s i utworzyć na niej indeks.
    • Wyjaśnię dlaczego: funkcja rankingu wyników jest oddzielna i działa również z tsvector ". Jeśli nie jest przechowywana, musi być obliczana na bieżąco przy każdym żądaniu każdego dokumentu, a to ma bardzo zły wpływ na wydajność , zwłaszcza gdy zapytanie znajdzie wiele dokumentów.To znaczy, jeśli głupio uwzględnisz w zapytaniu sortowanie według trafności - ORDER BY ts_rank(to_tsvector(pole), ) DESC - będzie znacznie wolniejszy niż MySQL :).
    • Jednocześnie, w celu optymalizacji miejsca na dysku, nie musisz go przechowywać pełny tekst dokumenty w indeksie.
  • Operatory wyszukiwania obejmują AND, OR i NOT oraz wyszukiwanie prefiksowe. Nie ma wyszukiwania pobliskich słów, dokładnych formularzy ani fraz.
  • Rozmiar indeksu wynosi około 150% rozmiaru danych, jeśli same teksty nie są przechowywane, ale przechowywane są tylko wektory tsvector.
  • Szybkość indeksowania - choć danych jest mało, 1,5 MB/s, powoli spada wraz ze wzrostem indeksu, ale jeśli same teksty nie są przechowywane, to wydaje się, że się uspokaja. Dla wszystkich tych samych danych z Bugzilli, wynik wyniósł średnio 522 KB/s, chociaż pod koniec indeksowania było to mniej niż na początku.
  • Szybkość wyszukiwania:
    • W 5 wątkach na 3 słowach - średnio 28 ms, maksymalnie 2,1 sekundy.
    • W 5 wątkach na 2 słowach - średnio 54 ms, maksymalnie 2,3 sekundy.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników średnio 26 ms, maksymalnie 611 ms.
    • W 1 wątku na 3 słowach - średnio 10 ms, maksymalnie 213 ms.

Lucene, Solr (3.3)

  • Lucene jest biblioteką wyszukiwania Java (nie serwerem), bardzo trudno jest ją całkowicie przejrzeć i przetestować - silnik jest najpotężniejszy (ale także najbardziej monstrualny) ze wszystkich recenzowanych.
  • Jej główną wadą jest fakt, że jest to biblioteka napisana w Javie - dostęp do Javy z innych języków jest utrudniony, dlatego też Lucene ma problemy z interfejsami :(. Wydajność z Javy też może nieco ucierpieć, ale najprawdopodobniej tak jest bardzo bezkrytyczny.
    • Z powiązań z językami istnieje tylko całkowicie działający PyLucene - do procesu Pythona dodawana jest JVM z Lucene na pokładzie, a pewna JCC zapewnia interakcję. Ale mocno bym się zastanowił, czy zastosować taką kombinację...
  • Aby poprawić sytuację, pojawił się Solr - w końcu serwer wyszukiwania zaimplementowany jako usługa sieciowa z interfejsami XML/JSON/CSV. Do działania potrzebny jest kontener serwletów - Tomcat, lub dla uproszczenia - Jetty. Teraz możesz z nim pracować w wielu językach.
  • Stwierdza się, że prędkość indeksowania Lucene jest „prawie bardzo wysoka”, ponad 20 MB/s, podczas gdy wymagana jest prawie bardzo mała pamięć (od 1 MB), a indeksowanie przyrostowe (dla jednego dokumentu) jest równie szybkie jak jednoczesne indeksowanie zestawu dokumentów. Rozmiar indeksu określa się na 20–30% rozmiaru danych.
  • Lucene jest bardzo rozszerzalna, więc istnieje wiele różnych funkcji i gadżetów, szczególnie w połączeniu z Solr i innymi bibliotekami:
    • 31 wbudowanych rdzeni, mnóstwo analizatorów - przetwarzanie dźwięku (Soundex, Metaphone i ich odmiany), skróty, słowa stop, synonimy, „protectwords” (odwrotność słów stop), frazy, półpasiec, separacja słów (Wi-Fi , WiFi -> Wi Fi), adresy URL i tak dalej, wiele różne opcje generowanie zapytań (np. FuzzyLikeThisQuery - wyszukaj „zapytanie podobne do podanego”).
    • Replikacja indeksów, automatyczne klastrowanie (grupowanie) wyników wyszukiwania (Carrot2), robot wyszukujący (Nutch), obsługa analizowania dokumentów binarnych (Word, PDF itp.) przy użyciu Tika.
    • Istnieje nawet gadżet pozwalający „podnieść” podane wyniki dla danych zapytań, niezależnie od normalnego rankingu (witaj, SEO).
    • A nawet to nie wszystko.
  • Rozmiar indeksu jest całkowicie podobny do Lucene - 20% danych. Szybkość indeksowania Solra dla 256 dokumentów na żądanie, bez zatwierdzeń pośrednich, wyniosła 2,75 MB/s, a przy zatwierdzeniach co 1024 dokumenty – 2,3 MB/s. Jeśli nie zatwierdzisz, zżera więcej pamięci - mam około 110 MB rezydentnych, jeśli zatwierdzisz - 55 MB.
  • Szybkość wyszukiwania Solr:
    • W 5 wątkach na 3 słowach - średnio 25 ms, maksymalnie 212 ms.
    • W 5 wątkach na 2 słowach - średnio 35 ms, maksymalnie 227 ms.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników średnio 15 ms, maksymalnie 190 ms.
    • W 1 wątku na 3 słowach - średnio 11 ms, maksymalnie 79 ms.

2.3.3.4, Lucene++ 3.0.3.4

  • Lucene jest napisany w Javie i dlatego istnieje wiele jego portów na różne języki, z których najbardziej aktywne są porty C++ i C# - , Lucene++ i Lucene.NET. Istnieją inne porty, ale są one (częściowo) opuszczone i/lub niestabilne.
  • Z CLucene też nie wszystko jest idealne:
    • Lucene rozwija się wolniej - o ile Lucene ma już wersję 3.3, CLucene stabilny (0.9.2.1) nadal odpowiada Lucene 1.9, a nawet nie ma łodyg, a CLucene „testuje” to Lucene 2.3.
    • Istnieje kilka/nieaktualnych powiązań językowych, na przykład powiązania Perla obsługują tylko wersję 0.9.2.1. Nazywa się to „Napisz własne”. Po spędzeniu kilku godzin załatałem je (oddając błąd autorom), a nawet dodałem obsługę stemmerów, które na szczęście nadal istnieją w wersji 2.3. Ogólnie te wiązania są trochę wilgotne, wyłapałem już i załatałem kolejnego segfaulta.
    • Najwyraźniej są błędy, dokumentacja w Internecie jest nieaktualna (ale możesz wygenerować normalną dokumentację za pomocą doxygen ze źródła), jest hostowana na SourceForge, gdzie wszystko jest powolne i smutne, a moduł śledzenia błędów od czasu do czasu zamyka błędy siebie (jeśli nikt na nie nie odpowiada O_O ).
  • Jeśli chodzi o funkcje, większość funkcji Lucene znajduje się w portach. Naturalnie nie ma żadnych funkcji Solr.
  • Szybkość indeksowania Clucene - mam 3,8 MB/s. Nie 20+ zadeklarowane przez Lucene, ale to jest z łodygą i interfejsem Perla, więc jest całkiem nieźle.
  • Rozmiar indeksu, podobnie jak Lucene/Solr, okazał się wynosić około 20% rozmiaru danych - to rekord wśród wszystkich silników i odpowiada deklarowanym 20-30%!
  • Lucene++ różni się od CLucene pod następującymi względami:
    • Implementacja jest bardziej kompletna i nowsza (3.0.3.4), na przykład istnieją analizatory dla różnych języków z wbudowanymi słowami stop.
    • Lucen++ wszędzie wykorzystujeshared_ptr (automatyczne zliczanie odniesień do obiektów przy użyciu szablonów C++). Co więcej, jest to bardzo zauważalne nawet podczas kompilacji; zajmuje to bardzo dużo czasu w porównaniu do CLucene.
    • Wiązania są jeszcze gorsze niż w CLucene - są tylko półmartwe dla Pythona, generowane przez SWIG - czyli pewnie płyną jak dranie i ogólnie nie wiadomo, czy działają.Chociaż szczerze mówiąc, nawet tego nie wiem natychmiast zrozumiesz, jak sprawić, by Perl normalnie powiązał się z tymi wspólna_ptrs.
    • Lucene++ wydaje się być używany bardzo rzadko, sądząc po tym, że w narzędziu do śledzenia błędów jest tylko 9 błędów.
  • Szybkość wyszukiwania - pomiary podobne do pomiarów Xapian, tylko przy użyciu MultiFieldQueryParser zamiast zastępowania słów dysjunkcjami:
    • W 5 wątkach na 3 słowach uzyskuje się średnio 10 ms, maksymalnie 212 ms.
    • W 5 wątkach na 2 słowach - średnio 19 ms, maksymalnie 201 ms.
    • W 5 wątkach na 3 słowach pierwsze 10 wyników średnio 3 ms, maksymalnie 26 ms.
    • W 1 wątku na 3 słowach - średnio 4 ms, maksymalnie 39 ms.
    • Ponownie zależy to głównie od znalezionej ilości, co odpowiada uwadze o złożoności poszukiwań.

Dla tych w zbiorniku

  • Indeks odwrócony dopasowuje każde słowo do zestawu dokumentów, w których się pojawia, w przeciwieństwie do indeksu bezpośredniego, który dopasowuje dokument do zestawu słów. Prawie wszystkie wyszukiwarki pełnotekstowe używają indeksów odwróconych, ponieważ można je szybko wyszukiwać, chociaż są trudniejsze do aktualizacji niż indeksy bezpośrednie.
  • Stemmer - od angielskiego słowa „rdzeń” - podstawa słowa. Odgryza końcówki słów, zamieniając je w łodygi. Zaprojektowane tak, aby słowo „kot” pasowało do słów „koty” i „kot” i tak dalej. Snowball - DSL do pisania stemerów.
  • Stopwordy to lista bardzo często używanych słów (przyimków, spójników itp.), których nie ma sensu indeksować, bo zawierają niewiele znaczeń i można je znaleźć niemal wszędzie.
  • Informacje pozycyjne - pozycje słów w dokumentach, przechowywane w indeksie, w celu dalszego wyszukiwania fraz lub po prostu słów znajdujących się nie dalej od siebie niż ...
  • Wyszukiwanie prefiksowe (słowa*) - szukaj słów zaczynających się na podane słowo (np. koty*). Czasami nazywane wyszukiwaniem wieloznacznym, ale ściśle rzecz biorąc, wyszukiwanie wieloznaczne to wyszukiwanie słów rozpoczynających się od danego przedrostka i kończących się na podanym sufiksie (na przykład ko*a - znajdzie zarówno słowo „kot”, jak i „koala”) .
  • Bugzilla to narzędzie do śledzenia błędów o otwartym kodzie źródłowym stosowane w naszej firmie, na podstawie którego przetestowano wyszukiwanie.

tabela porównawcza

MySQL'aPostgreSQLXapianaSfinksSolrCLucen
Szybkość indeksowania314 KB/s522 KB/s1,36 MB/s4,5 MB/s2,75 MB/s3,8 MB/s
Szybkość wyszukiwania175 ms / 3,46 sek28 ms / 2,1 sek14 ms / 135 ms7ms/75ms25 ms / 212 ms10 ms / 212 ms
Rozmiar indeksu 150 % 150 % 200 % 30 % 20 % 20 %
RealizacjaDBMSDBMSBibliotekaserwerserwerBiblioteka
InterfejsSQL-aSQL-aAPIAPI, SQLSerwis internetowyAPI
Wiązania 9 6 + ∀ 8 3.5
Operatory wyszukiwania &*" &* &*"N-~&*"N- &*"N-~&*"N-~
PędyNIE 15 15 15 31 15+CJK
Zatrzymaj słowa, synonimyNIETakTakTakTakTak
SoundexNIENIENIETakTakNIE
PodświetlenieNIETakNIETakTakTak

Ranking wyników i sortowanie według różnych dziedzin jest wszędzie.

Dodatkowo:

Wniosek

Najprostszym i najszybszym silnikiem jest Sphinx. Wadą jest to, że zaktualizowane indeksy nie są jeszcze zbyt przydatne - można ich używać tylko wtedy, gdy nigdy nie usuniesz niczego z indeksu. Jeśli zostanie to naprawione, problem selekcji zniknie całkowicie, Sfinks zrobi wszystko.

Również szybki, bardzo funkcjonalny, wydajny i rozszerzalny, ale nie najłatwiejszy w obsłudze silnik - Lucene. Głównym problemem związanym z interfejsami są porty Java lub C++ oraz problemy z powiązaniami. Oznacza to, że jeśli nie piszesz w Javie, C++, Pythonie lub Perlu, musisz użyć Solr. Solr już zjada trochę pamięci, indeksuje i przeszukuje nieco wolniej, może być niewygodny jako oddzielny serwer Java w kontenerze serwletów, ale ma ogromną masę różnych możliwości.

Xapian... Wyszukuje szybko, indeksuje niezbyt dobrze, a sam indeks jest za duży. Jego plusem jest masa interfejsów dla różnych języków (C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua). Jeśli wydaje się, że tryb wyłącza indeksowanie dokładnych formularzy, rozmiar indeksu zostanie natychmiast zmniejszony dwukrotnie.

Jeśli już korzystasz z PostgreSQL i chcesz pogodzić się z niezbyt wysokimi prędkościami indeksowania i całkowitym brakiem trudnych operatorów wyszukiwania, możesz użyć Textsearch, ponieważ wyszukuje szybciej niż MySQL i jest całkiem porównywalny z innymi. Należy jednak pamiętać, że indeks musi zostać utworzony na rzeczywistej kolumnie typu tsvector, a nie na wyrażeniu to_tsvector().

MySQL FULLTEXT można również zastosować w prostych przypadkach, gdy baza danych jest mała. Jednak w żadnym wypadku nie należy dokonywać DOPASOWANIA (kilka pól) i pod żadnym pozorem nie używać wyszukiwania prefiksowego.

Wszelkie zmiany w tym artykule zostaną nadpisane podczas następnej sesji replikacji. Jeśli masz poważną uwagę dotyczącą tekstu artykułu, zapisz ją w sekcji „dyskusja”.