Verdens første søkemotor: Historisk ekskursjon. Sammenligning av fulltekst søkemotorer

Eksempler som illustrerer den tekniske kompleksiteten ved å lage en effektiv søkemotor.

Eksempel

Siden er dedikert til webdesign. Hovedfokus er på opprettelse og redesign av nettsider. Uttrykket "oppretting av nettsteder" vises mange ganger på nettstedet, men det er ingen uttrykk "nettstedproduksjon" eller "nettstedutvikling."

Det er påkrevd å inkludere en søkemotor på nettstedet. Motorens søkealgoritme er basert på indeksering av nettstedets tekst.Søket utføres ved hjelp av nøkkelord og nøkkelsetninger, inneholdt i teksten til de indekserte filene. Grunnprinsippet for å vurdere relevansen av tekstinformasjon: hyppighet av forekomst søkeord og fraser.

Hvis du ber om "nettstedutvikling" eller "nettsideproduksjon", vil ikke søkemotoren returnere noen resultater. Tross alt er det ingen slike setninger på nettstedet. En skuffet besøkende vil forlate nettstedet uten å finne informasjonen de trenger.

Du kan forbedre driften av søkemotoren. Men for dette må søkemotoren konfigureres manuelt, og indikerer hvilke sider som skal gis lenker hvis teksten på nettstedet ikke inneholder de forespurte søkeordene eller frasene, men inneholder andre ord og uttrykk som har lignende betydning.

Når en Netpikov-arbeider står overfor en oppgave som krever tid (for eksempel å lage et Death Star-prosjekt eller bygge en kompakt kaldfusjonsenhet), tenker han først og fremst på hvordan han kan automatisere dette arbeidet. Vi samler resultatene av slike refleksjoner på en spesiell side på nettstedet vårt. I dag skal vi snakke om hvordan en ny nyttig tjeneste blir født i dypet av Netpeak-byrået.

For lenge siden, i en galakse langt, langt unna, bestemte vi oss for å endre søkemotoren til en kundes nettsted for å øke synligheten til sider i organisk søk.

Oppgave

Søkemotoren til klientprosjektet som vi måtte jobbe med opprettet egen side for hver forespørsel. Siden søk noen ganger inneholder skrivefeil, har det samlet seg et helt fjell av slike sider – både korrekte og med feil. Generelt - mer enn to millioner sider: like for russisk og på engelsk. Sider med feil ble indeksert og tilstoppet resultatene.

Vår oppgave var å sørge for at alle søkealternativer – både korrekte og med feil – førte til én side. For eksempel, for hvert av søkene baseball, basaball, baaeball, baselball var det sine egne sider, men det var nødvendig å sørge for at alle alternativer konvergerte på én side med riktig forespørsel- baseball. I dette tilfellet vil siden samsvare med riktig form for forespørselen, og vi vil være i stand til å bli kvitt søppel i søkeresultatene.

Eksempler på grupper:

Det er verdt å merke seg at byråer ikke alltid har tillit til å implementere endringer i nettsidemotoren. Så vi er takknemlige overfor vår klient for muligheten til å gjennomføre dette prosjektet.

Mål

Lag en tydelig arbeidsmekanisme for å plassere omdirigeringer fra sider for setninger med feil til en side på klientsiden med riktig setning.

Dette er nødvendig både for å forbedre gjennomsøking og indeksering av landingssider av søkemotorer, og for å bygge semantisk kjerne og bruke det i utviklingen ny struktur nettstedet. Selvfølgelig visste vi ikke det totale antallet språk som søk ble lagt inn på, men hoveddelen av setningene var på russisk og engelsk, så vi fokuserte på disse språkene.

Hvordan en ny metode ble født

Den enkleste løsningen som umiddelbart kommer til tankene er å legge inn spørringer i Google, og det vil ærlig rette det for oss. Men å organisere en slik penetrasjon er en ganske kostbar oppgave. Derfor tok kameratene mine og jeg en annen vei. Vår analytiske matematiker bestemte seg for å bruke en språklig tilnærming (ut av det blå!) og bygge en språkmodell.

Hva betyr det? Vi bestemmer sannsynligheten for å møte et ord på et språk og for hvert ord finner vi sannsynligheten for å gjøre forskjellige feil i det. Alt ville vært bra, og teorien her er vakker, men for å samle inn slik statistikk må du ha et stort oppmerket tekstkorpus for hvert språk (igjen, søkemotorer kommer nærmest dette). Naturligvis dukket det opp spørsmål om hvordan man gjør dette og hvem som skal implementere alt dette i kode. Ingen hadde gjort noe lignende før (hvis du kjenner en sak, legg ut lenken i kommentarfeltet), så metodikken ble utviklet fra bunnen av. Det var flere ideer og det var ikke åpenbart på forhånd hvilken som var best. Derfor forventet vi at utviklingen ville foregå syklisk - forberede en idé, implementering, testing, vurdere kvalitet, og deretter bestemme om vi skulle fortsette å foredle ideen eller ikke.

Implementeringen av teknologien kan deles inn i tre stadier. Les mer om hver av dem.

Etappe nr. 1. Dannelse av problemet. Første rake

Merk følgende! Etter denne linjen vil det være mange begreper som vi prøvde å forklare på et så enkelt språk som mulig.

Siden tilleggsinformasjon (ordbøker, frekvenser, logger) ikke er tilgjengelig, ble det forsøkt å løse problemet med ressursene vi hadde. Vi prøvde ulike metoder gruppering. Hovedtanken er at ord fra samme gruppe ikke skal avvike for mye.

Gruppering- en prosedyre som samler inn data som inneholder informasjon om et utvalg av objekter og deretter ordner objektene i relativt homogene grupper.

Levenshtein avstand viser minimum antall endringer (slettinger, innsettinger og erstatninger) i rad A som må gjøres for å oppnå rad B.

• Symbolerstatning: sh[e]res — sh[i]res, sh[o]res;
• Sette inn et symbol: sheres - s[p]heres;
• Fjerning: gol[d][f] - golf, gull.

I hvert av eksemplene er avstanden mellom det feilstavede ordet og riktig form 1 rettelse.

Jaccard-koeffisient på bi- og trigram hjelper til med å finne ut hvor mange vanlige kombinasjoner av to- eller tretegnsstavelser linje A og B har.

Eksempel: La oss se på linjene A = snowboard og B = kant. Den generelle formelen for koeffisienten for bigram er:

J = (antall identiske bigram for A og B) / ( totalt antall bigram i A og B)

La oss dele opp linjene i bigrammer:

bigram for A = ( sn, nei, ow, wb, bo+, oa, ar, rd+ ) - 8 stykker; bigram for B = ( bo+, eller, rd+, de, er ) - 5 stykker; Det er to identiske bigrammer merket med plusstegn - bo og rd.

For trigrammer vil det være likt, bare i stedet for to bokstaver vil tre bli brukt. Jaccard-koeffisienten for dem vil være som følger:

Eksempel på flere lignende ord:

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

Selv om Jaccard-koeffisienten fungerer raskere, tar den ikke hensyn til rekkefølgen av stavelser i et ord. Derfor ble den hovedsakelig brukt for sammenligning med Levenshtein-avstanden. I teorien var alt enkelt her. Klyngeteknikker for små data er ganske enkle å løse, men i praksis viste det seg at for å fullføre sammenbruddet, enten store datakraft, eller årevis (og ideelt sett begge deler). På to ukers arbeid ble det skrevet et manus i Python. Når den ble lansert, leste den fraser fra en fil og utdatagruppelister til en annen fil. Samtidig, som et hvilket som helst program, lastet dette skriptet prosessoren og brukte RAM.

De fleste av metodene som ble testet krevde terabyte minne og uker med CPU-tid. Vi tilpasset metodene slik at programmet trengte 2 gigabyte minne og én kjerne. Imidlertid ble en million forespørsler behandlet på omtrent 4-5 dager. Så fullføringstiden for oppgaven lot fortsatt mye å være ønsket. Resultatet av algoritmen kan presenteres i form av en graf ved å bruke et lite eksempel:

Når det brukes på et klientprosjekt, betyr dette at sider som samsvarer med forespørsler i samme klynge, blir limt sammen med en 301-viderekobling. La oss huske at målet vårt var å lage en tydelig arbeidsmekanisme for å plassere omdirigeringer fra sider for setninger med feil til en side på klientnettstedet med riktig setning. Men selv med dette eksemplet er manglene åpenbare:

1. Det er ikke klart hvordan man finner de riktige skjemaene fra gruppene og om de i det hele tatt er der.
2. Det er ikke kjent hvilke feilterskler som skal brukes. Hvis det er en stor terskel (mer enn 3 feil), så vil gruppene være veldig store og forsøplede hvis den er for liten, vil hvert ord danne sin egen gruppe, som heller ikke passet oss. Det er umulig å finne en universell betydning som er akseptabel for alle grupper.
3. Det er ikke klart hva man skal gjøre med ord som kan klassifiseres samtidig i flere grupper.

Etappe nr. 2. Forenkling. Nytt håp

Vi har redesignet algoritmen, og bringer den nærmere tradisjonelle mekaniske grammatikkkorrigerere. Heldigvis er det nok av dem. Python-biblioteket Enchant ble valgt som base. Dette biblioteket har ordbøker for nesten alle språk i verden, det er ganske enkelt å bruke, og du kan få hint om hva som må rettes. I det forrige stadiet lærte vi mye om hvilke typer søk og hvilke språk disse spørringene kan være på.

Fra åpen tilgang Følgende ordbøker ble samlet inn:

• engelsk (Storbritannia);
• engelsk (USA);
• Tysk;
• Fransk;
• italiensk;
• spansk;
• russisk;
• ukrainsk.

1. Hvis det er riktig (ligger i en av ordbøkene), lar vi det være som det er;
2. Hvis det er feil, får vi en liste med ledetråder og tar den første som kommer over;
3. Vi setter alle ordene sammen til en frase. Hvis vi ikke har kommet over en slik setning før, så oppretter vi en gruppe for den. Den korrigerte formen av uttrykket blir dens "sentrum". Hvis vi har, betyr det at denne frasen allerede har sin egen gruppe, og vi legger til en ny feilaktig form der.

Som et resultat fikk vi midten av gruppen og en liste med ord fra denne gruppen. Her er selvfølgelig alt bedre enn første gang, men en skjult trussel har dukket opp. På grunn av detaljene i prosjektet er det mange egennavn i spørringene. Det er for- og etternavn på personer, byer, organisasjoner, geografiske områder og til og med latinske navn på dinosaurer. I tillegg til dette fant vi ord med feil translitterasjon. Så vi fortsatte å lete etter måter å løse problemet på.

Etappe nr. 3. Supplements og The Force Awakens

Problemet med translitterasjon ble løst ganske enkelt og tradisjonelt. For det første laget vi en ordbok over korrespondanse mellom kyrilliske og latinske bokstaver.

I samsvar med den ble hver bokstav i ordene som ble kontrollert transformert, og det ble notert om det var en ordbokkorreksjon for det resulterende ordet. Hvis translitterasjonsalternativet hadde færrest feil, valgte vi det som riktig. Men egennavn er litt av en nøtt å knekke. Det enkleste alternativet for å fylle på ordbøker viste seg å være å samle ord fra Wikipedia-dumper. Wiki har imidlertid også sine svake sider. Det er ganske mange feilstavede ord der, og metoden for å filtrere dem er ennå ikke ideell. Vi har satt sammen en database med ord som begynner med stor bokstav, og uten skilletegn foran. Disse ordene ble våre kandidater for egennavn. For eksempel, etter å ha behandlet en slik tekst, ble de understrekede ordene lagt til i ordboken:

Ved implementering av algoritmen viste det seg at det å søke etter ledetråder i Enchants utvidede ordbok noen ganger krevde mer enn 3 sekunder per ord. For å fremskynde denne prosessen ble en av implementeringene av Levenshtein-automaten brukt.

Kort sagt, ideen med maskinen er at vi bygger et overgangsskjema ved å bruke den eksisterende ordboken. Samtidig vet vi på forhånd hvor mange rettelser i ord som vil være akseptable for oss. Hver overgang betyr at vi gjør en form for transformasjon på bokstavene i ordet - vi lar bokstaven stå eller bruker en av korrigeringstypene - sletting, erstatning eller innsetting. Og hvert toppunkt er et av alternativene for å endre ordet.

La oss nå si at vi har et ord vi ønsker å sjekke. Hvis det er en feil i det, må vi finne alle rettingsformer som passer oss. Konsekvent begynner vi å bevege oss i henhold til ordningen, og går gjennom bokstavene i ordet som kontrolleres. Når bokstavene går tom, vil vi befinne oss ved ett eller flere hjørner, og de vil vise oss alternativene for de riktige ordene.

Bildet viser en maskin for ordet mat med alle mulige to feil. Pil opp betyr å sette inn et tegn på gjeldende posisjon. En pil diagonalt med en stjerne betyr erstatning, en pil med en epsilon betyr sletting, og en horisontal pil betyr at bokstaven forblir uendret. La oss ha ordet fxood. Det vil tilsvare banen i maskinen 00-10-11-21-31-41 - som tilsvarer å sette inn bokstaven x etter f i ordet mat.

I tillegg utførte vi tilleggsarbeid for å utvide de innsamlede hovedordbøkene, filtrere ut på forhånd ikke-ordbokfraser (navn på produktmodeller og ulike identifikatorer) automatisk, introduserte translitterasjon og søk i en ekstra ordbok.

Hva er resultatet?

Vi jobber fortsatt med å oppgradere algoritmen, men allerede kl sånn som det er nå utvikling, vi har et verktøy som kan rydde opp i søppel, som tagskyer og slå sammen 301-omdirigeringer unødvendige sider. Et slikt verktøy vil være spesielt effektivt for et lite antall feilstavede ord, men det viser også ganske tilfredsstillende resultater på store matriser. En mellomversjon av skriptet ble sendt til klienten for å danne en koblingsblokk. Fra denne blokken vil det være mulig å hente Ytterligere informasjon om rettelser av spørsmål. Vi sendte ikke de fullstendige resultatene av skriptet for implementering, fordi vi fortsatt jobber med å forbedre kvaliteten på skriptet.

Å lage koden og teste den tok totalt 40 timers arbeid av en matematiker-analytiker. Konklusjon: Hvis du en dag trenger å behandle rundt to millioner forespørsler, fortvil ikke. Slike oppgaver kan automatiseres. Det er klart at det vil være svært vanskelig å oppnå 100 % nøyaktighet, men det er mulig å behandle minst 95 % av informasjonen riktig.

Klassifisering

Etter søkeområde (betinget)

Lokalt

Designet for å søke etter informasjon om hvilken som helst del verdensomspennende nettverk, for eksempel over ett eller flere nettsteder, eller over et lokalt nettverk.

Global

Designet for å søke etter informasjon på hele Internett eller en betydelig del av det. Representanter for slike søkemotorer er søkemotorer Google, Yandex, etc. Søkemotorer søker etter informasjon forskjellige typer, for eksempel tekster, videoer, bilder, geografiske objekter, personlige data osv. I dette tilfellet kan filene som en søkemotor kan jobbe med være i tekstformat (for eksempel .html, .htm, .txt, . doc, .rtf...), og grafikk (.gif, .png, .svg...) eller multimedia (video og lyd). Så langt er det vanligste å søke gjennom tekstdokumenter.

Søkeord

Den første informasjonen for søket er søket.

Funksjoner

Søkemotorer utfører flere funksjoner:

Søk etter lenker

Søk etter lenker til sider og andre nettstedsdokumenter.

Auto

Manuell innstilling

Brukerne selv legger til lenker til sidene på sine nettsteder i søkemotordatabasen

Indeksering av nettsidedokumenter

Trekke ut søkerelevant informasjon fra dokumenter, konvertere denne informasjonen til et søkemotorvennlig format og lagre denne informasjonen i en søkemotordatabase

Søk i databasen med indekserte dokumenter

Kan bestå av flere stadier

Finne dokumenter som samsvarer med et søk

Ranger dokumenter i henhold til deres relevans for søk

Dokumentklynger

Notater

se også

Wikimedia Foundation. 2010.

Se hva en "søkemotor" er i andre ordbøker:

Søkemotor- (søkemotor): en webserver som indekserer nettsider på tilgjengelige servere(for eksempel Yandex)... Kilde: INTERNETTRESSURSER. TILGJENGELIGHETSKRAV FOR VISUEDE. GOST R 52872 2007 (godkjent av Order of Rostekhregulirovaniya datert ... ... Offisiell terminologi

søkemotor- Webserver som indekserer nettsider på tilgjengelige servere (for eksempel Yandex). [GOST R 52872 2007] Emner informasjonsteknologi generelt EN søkemotor ... Teknisk oversetterveiledning

På Internett, et spesielt nettsted der en bruker, på en gitt forespørsel, kan motta lenker til nettsteder som samsvarer med denne forespørselen. Søkesystemet består av tre komponenter: 1 søkerobot; 2 systemindekser; og 3 programmer,... ... Finansiell ordbok

På Internett, en søkemotor som: sender en søkeforespørsel til flere søkemotorer; og genererer et sammendrag (på én side) fra de mottatte svarene. På engelsk: Meta-søkemotor Synonymer: Meta caterpillar Engelske synonymer: Metacrawler... ... Finansiell ordbok

Denne artikkelen må omskrives fullstendig. Det kan være forklaringer på diskusjonssiden. Søkemotor programmatisk maskinvarekompleks med et nettgrensesnitt som gir muligheten ... Wikipedia

Søkesystem- – (engelsk søkemotor, synonymer: søkemotor, søkeserver, søkemotor) – Et verktøy for å søke etter informasjon på Internett. Som regel består arbeidet til en søkemotor av to stadier. Spesialprogram (søkerobot, maskingevær, agent,... ... Encyclopedic Dictionary of Media - Søkemotor er et nettsted som gir muligheten til å søke etter informasjon på Internett. De fleste søkemotorer ser etter informasjon på nettsider Verdensveven, men det finnes også systemer som kan søke etter filer på ftp-servere, varer i... ... Wikipedia

Bøker

• I spørsmålet om effektiviteten av å søke etter detaljer på Internett, I. A. Semenov. I følge Berkley-forskning ble informasjonsmengden på Internett i 2003 estimert til 258,85 terabyte, og dette er kun offentlig tilgjengelige data. I følge Internet World Stats er veksten... eBok

• Indekser kan bare opprettes på felt av MyISAM-tabeller.
• Indeksstørrelsen er omtrent halvparten av størrelsen på dataene. Du må imidlertid huske på at du ikke kan deaktivere lagringen av selve tekstene, så til disse 50% må du legge til ytterligere 100% - dataene lagres.
• Indekseringshastigheten er grei i sin rene form, omtrent 1,5 MB/s. Det er klart at du fortsatt må kjøre den gjennom stemmeren. Hvis du fyller indeksen ved å trekke data fra den samme databasen i farten og kjøre den gjennom Perl-porten til den russiske Snowball-stemmeren, får du 314 KB/s. Faktisk har MySQL en arkitektur for å koble stemmer med plugins ("fulltekst parser plugins"), men på en eller annen måte er det ingen plugins i seg selv... :)
• Det er ingen innebygd stemmer, engelske stoppord er innebygd, du kan ikke legge til dine egne. Som standard er et boolsk søk ​​"ELLER", så for å søke med "AND" må du gjøre hvert ord om til et "+ord".
• Det er to moduser - boolsk og normalt ("naturlig språk") søk. Boolsk søk ​​sjekker ganske enkelt om det er ord i dokumentet og støtter logiske operasjoner, fraser og prefikssøk, men returnerer ikke en relevansscore (bare 0 eller 1). Vanlig søk kan gjøre relevans, men ikke operatorer. Derfor, for å støtte begge, må du kjøre den samme forespørselen i to moduser.
  • Prefikssøk i MySQL fortryllende langsom. Med noen få ord, utvidet til prefikser, kan det lett ta 15 eller 40 sekunder. Så den trenger ikke brukes i det hele tatt.
• Den kan ikke søke i flere felt samtidig - det vil si at syntaksen til MATCH() tillater det, men ingen søkeoptimalisering skjer, men en full skanning skjer. Derfor er det bedre å skrive (velg id hvor match(felt1) ...) UNION (velg id hvor match(felt2) ...) .
• Søkehastighet, for søk hentet fra tilfeldige feiltitler, med en grense på 1000 funnet:
  • I 5 tråder på 3 ord - et gjennomsnitt på 175 ms, maksimalt 3,46 sekunder.
  • I 5 tråder på 3 ord er de første 10 resultatene de samme.
  • I 5 tråder på 2 ord - i gjennomsnitt 210 ms, maksimalt 3,1 sek.
  • I 1 tråd på 3 ord - et gjennomsnitt på 63 ms, maksimalt 764 ms.
  • Avhenger hovedsakelig av mengden funnet.
• Den største fordelen er tilstedeværelsen av et "gnist"-søk.

Sphinx (2.0.1-beta)

• Separat søkeserver. Det er grensesnittbiblioteker for det for en haug med forskjellige språk. Det er veldig kult at i 0.9.9, i tillegg til det "native" grensesnittet, dukket SphinxQL opp - et SQL-grensesnitt til Sphinx som bruker MySQL-protokollen, det vil si ved å bruke vanlige MySQL-klienter.
• Opprinnelig var det ingen oppdaterte (sanntids) indekser i Sphinx, det eneste den kunne gjøre var å bygge hele indeksen og deretter søke i den.
• Den vet fortsatt ikke hvordan den skal oppdatere / slette dokumenter i indeksen, den legger bare til normalt. Fjerning utføres ved å merke av for "gammel oppføring", og deretter slette den fra alle søkeresultater hver gang.
• Sanntidsindekser støtter ikke alt - for eksempel støtter de ikke prefikser/infikser og MVA.
• Litt rot med grensesnitt og funksjoner: oppdatering av sanntidsindeksen kun gjennom SphinxQL; søkesyntaksen er forskjellig i alle tre grensesnittene (vanlig, SphinxQL, SphinxSE); 5 søkemoduser, hvorav 4 er foreldet; indekser kan ikke gjenoppbygge sanntidsindekser; Det er umulig å TRUNCATE en indeks med SphinxQL, og du kan ikke se hvor mange poster som er i indeksen...
• Det er her ulempene slutter - det er en søkeserver som du kan kommunisere med ved hjelp av din egen protokoll eller MySQL-protokollen, en haug med forskjellige muligheter, indekserer og søk veldig raskt, indeksstørrelsen er omtrent 1/3 av dataene. Den kan øke med 2 ganger hvis du aktiverer indeksering av eksakte ordformer.
• Innebygde russiske, engelske og tsjekkiske stemmer og Soundex- og Metaphone-forprosessorer (for sammenligning av engelske ord etter lyd). Stemmere for andre språk kan også kobles til, du trenger bare å bygge dem med --with-libstemmer-tasten. Selvfølgelig er det støtte for stoppord. Synonymer også, og det er vanlige, og det er "tokeniserende unntak", som kan inneholde spesialtegn. Det finnes også "blend_chars" - tegn som regnes som både skilletegn og del av ord - for eksempel slik at "AT&T" blir ordene "AT", "T" og "AT&T".
• Blant de kule uvanlige funksjonene - den kan gjøre infikssøk (for de som ønsket å raskt søke etter understreng!), felt med flere verdier (MVA), den kan indeksere etter avsnitt og setninger, og til og med etter innholdet i forhåndsdefinerte HTML-koder. Den kan også fremheve søkte ord i anførselstegn og mye mer. Imidlertid støttes ikke MVA og infikser (ennå?) i oppdaterte indekser.
• Indekseringen er veldig rask - nettohastigheten med en sanntidsindeks er 6,7 MB/s (nedlasting av en SQL-dump), med en vanlig indeks - vanligvis 12 MB/s (nedlasting av en xmlpipe2-dump). "Uren" hastighet (fra Perl, med avlesning av data underveis fra MySQL) - 4,5 MB/s. Med infikser bremser alt naturlig nok ned mye - 440 KB / s, I/O-haugen er 10,5 GB, og indeksen viser seg å være 3 GB i størrelse for 330 MB data.
• Søk er generelt reaktivt:
  • I 5 tråder på 3 ord - i gjennomsnitt 7 ms, maksimalt 75 ms.
  • I 5 tråder på 2 ord - i gjennomsnitt 7 ms, maksimalt 81 ms.
  • I 5 tråder på 3 ord er de 10 første resultatene i gjennomsnitt 5 ms, maksimalt 57 ms.
  • I 1 tråd på 3 ord - i gjennomsnitt 2 ms, maksimalt 35 ms.

Xapian (1.2.6)

• Bibliotek, det er ingen ferdige søkeserver. C++ API er ganske fornuftig. Det ser ut til å støtte konkurransearbeid (mange lesere, en forfatter).
• Mange tilgjengelige bindinger for forskjellige språk: C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua.
• Indeksen er en invertert B-trebasert indeks.
• Det kule er at Xapian ikke trenger å brukes spesifikt som en fulltekstindeks - faktisk er det bare en implementering av en invertert indeks som kan brukes som du vil, fordi det ikke er noen begrensninger på "ordene" som finnes i dokumentet, bortsett fra lengdegrensen på 245 byte. I teorien kan du bruke den som en database.
• Helt ærlig elendig dokumentasjon. En slags samling av opplysninger, som ennå ikke inneholder alt. For å forstå noen punkter, må du dumt klatre inn i koden. Jeg ble frekk og la til og med en feil om dette emnet - bug 564. Vel, det er sant - motoren ser ut til å være ganske bra, men få mennesker vet om den.
• Det er morsomt at da jeg begynte å teste det, fant jeg en merkelig feil - en segfault i libuuid, som ikke tillater å lage en database hvis Image::Magick lastes parallelt. Det viste seg at dette ikke engang var en ImageMagick-feil, men enda mer alvorlig - det var en libc6-feil! I 2.12 og 2.13 er initialiseringen av Thread-Local Storage ved dynamisk lasting av biblioteker ødelagt, åh hvordan. Det ble fikset i 2.14, men Debian er fortsatt 2.13. Jeg la til feil 637239 til Debian (det er også lenker til feil i gentoo og selve libc).
• Perl-bindinger krever etterbehandling for å kunne velge en backend, og som standard er det ikke den nyeste Brass, men den stabile Chert. Etterbehandling er enkelt. Jeg ga dem også en feil om dette emnet - bug 565.
• Det ser ikke ut til å være støtte for ulike felt i indeksen, men det gjøres ved å legge til prefikser i begynnelsen av hvert ord: http://xapian.org/docs/omega/termprefixes.html
  • Dette er den "offisielle tilnærmingen", Xapian kan gjøre det selv, bare spesifiser prefiksene.
  • Denne tilnærmingen har minst en liten ulempe - som standard søker ikke søket i alle felt, og for å søke i alle må du manuelt sette inn OR i spørringen.
  • Ja, dokumentasjonen er igjen ufullstendig og ikke på rett sted - den skal være i Xapians manual, men den er i Omega-manualen, som er en ferdiglaget enkel CGI-søkemotor.
  • Ubehagelig øyeblikk - raskt funnet feil i spørringsparseren - genererer den feil termer for å søke etter ordstammer i felt (som har prefikser). Indekseren tildeler prefikset "Z" til alle stammer i begynnelsen, det vil si at stammen for ordet "ide" i tittelen (si prefikset T) er indeksert som "ZTide". Og spørringsparseren prøver å søke etter "Tida", og finner naturligvis ingenting. Jeg ga dem bug 562 om dette emnet. Fikset, faktisk med én linje.
• Stemmers er innebygd for 15 språk, som vanlig, generert fra Snowball "a. Det er støtte for stoppord (selvfølgelig) og synonymer. Enda mer interessant - det kan rette skrivefeil uten å bruke ordbøker, men bare basert på indekserte data ( må aktiveres ved innstilling). Det vil si, for eksempel, for "Xapain" vil den ærlig foreslå "Xapian" Det er også støtte for å søke etter "uferdige spørringer", det vil si for hint når du skriver inn et søk bokstav for bokstav. Faktisk er dette bare å legge til * til det siste ordet i søket, men tar hensyn til nyansene i søkesyntaksen.
• Det er også "Faceted Search" - beregning av samlede verdier for alle eller nesten alle funnet dokumenter (si, med en grense på 10 000). Det vil si at disse 10 000 dokumentene vil ikke bli returnert til deg, men de vil bli kontrollert og en viss samlet verdi vil bli beregnet ut fra dem. På denne måten kan du for eksempel returnere 10 resultater (side) og samtidig svare på spørsmålet "fra hvilke kategorier ble dokumentene funnet?"
• Det er elendig at hvis du flush() (commit) når du indekserer én gang hver 256. feil, så synker hastigheten fra ~1,5 MB/s til 412 KB/s, og antallet I/O-operasjoner øker kraftig - med 10-20 ganger. I prinsippet er dette oppgitt og logisk for enhver invertert indeks - det er mye mer optimalt å akkumulere endringer enn å prøve å oppdatere en om gangen, fordi antallet oppdaterte tokens øker.
• Størrelsen på indeksen - de skriver at den er omtrent lik størrelsen på dataene, dette er ikke sant, i virkeligheten er det 2 ganger større De skriver at hvis du ikke lagrer ordene i dokumenter, vil det gjøre det bli 2 ganger mindre. Men unnskyld meg, Sphinx lagrer også posisjoner, og indeksen er 2 ganger mindre data. Hvis du kjører xapian-compact (databasedefragmentering) - ja, indeksen synker, men det er fortsatt ca 1,7 ganger mer data igjen.
  • Jepp, grunnen er funnet - Xapian indekserer alltid både det grunnleggende og de nøyaktige formene til ord. Det er umulig å deaktivere indeksering av eksakte skjemaer, det er synd, jeg ga dem bug 563 om dette emnet.
• Søker raskt. Jeg testet det på denne måten: Jeg søkte etter flere tilstøtende ord på minst 2 tegn i lengde, i STEM_ALL-modus, hentet fra feiltitlene (jeg søkte ikke med "ELLER", men med "AND"), og erstattet hvert ord med (ord ELLER tittel: ord ELLER privat: ord), dvs. søk i tre felt i stedet for ett, begrenset antall resultater til 1000.
  • I 5 tråder på 3 ord - gjennomsnittlig 14 ms, maksimalt 135 ms.
  • I 5 tråder på 2 ord - et gjennomsnitt på 29 ms, maksimalt 137 ms.
  • I 5 tråder på 3 ord er de 10 første resultatene i gjennomsnitt 2 ms, maksimalt 26 ms.
  • I 1 tråd på 3 ord - i gjennomsnitt 7 ms, maksimalt 51 ms.
  • Søkehastigheten avhenger hovedsakelig av antall resultater som er funnet, jo lengre tid tar det å søke.

Xapian har 3 backends (implementeringer av selve indeksen) - i nyhetsrekkefølge Flint, Chert og Brass. Det er som i Debian oldstable, stabil og testing :) i 1.2.x er standard backend Chert. Før Flint var det kvarts.

PostgreSQL Textsearch (9.1)

• Indeksen er invertert basert på GIN (Generalized Inverted Index). Tidligere kalt Tsearch2, skapt av Oleg Bartunov og Fedor Sigaev.
• Det er innebygde stemmer, støtte for stoppord, synonymer, en synonymordbok (noe sånt som en ordbok med begreper, erstatter ord med andre "foretrukket"), ISpell-ordbøker (selv om de sies å være fryktelig trege under initialisering).
• Ved indeksering er det mulig å knytte en "vekt" til hvert leksem, som egentlig ikke er en "vekt", men en analog av Xapian-prefikset, det vil si navnet på feltet som leksemet kom fra. Det kan bare være 4 slike "vekter" - A, B, C, D, og ​​i fremtiden kan de brukes når du søker. Et eksempel på å konstruere tsvector "a fra to felt med "vekter": setweight(to_tsvector(coalesce(title,""), "A") || setweight(to_tsvector(coalesce(keyword,"")), "B") .
• Spise skille funksjoner for å rangere resultater og fremheve søkte ord i sitater. Rangering kan gjøres ved å tilordne numeriske vekter til ABCD "vektene" ovenfor (som er "feltene"). Dessuten er vektene som standard lik (0,1, 0,2, 0,4, 1,0).
• Den indekserte datatypen kalles tsvector (tekstsøkevektor). PostgreSQL lar deg lage funksjonelle indekser, og standardmanualen foreslår å lage nettopp disse - CREATE INDEX i ON t USING gin(to_tsvector(<поле>)). Så her er det: ikke gjør det! Ellers vil du bli veldig ubehagelig overrasket over hastigheten på forespørsler. Sørg for å lage en egen kolonne av typen tsvector , legg til tsvector-ene dine i den, og lag en indeks på den.
  • Jeg skal forklare hvorfor: funksjonen for rangering av resultater er separat, og fungerer også med tsvector ". Hvis den ikke er lagret, må den beregnes på et øyeblikk med hver forespørsel for hvert dokument, og dette har en veldig dårlig effekt på ytelsen , spesielt når spørringen finner mange dokumenter. Det vil si, hvis du tar med sortering etter relevans i spørringen din - ORDER BY ts_rank(to_tsvector(field), ) DESC - vil være mye tregere enn MySQL :).
  • Samtidig, som en optimalisering av diskplass, trenger du ikke å lagre full tekst dokumenter i indeksen.
• Søkeoperatorer inkluderer AND, OR og NOT og prefikssøk. Det er ikke noe søk etter nærliggende ord, eksakte former eller uttrykk.
• Indeksstørrelsen er et sted rundt 150 % av datastørrelsen, hvis tekstene i seg selv ikke er lagret, men bare tsvector "er lagres.
• Indekseringshastighet - mens det er lite data, 1,5 MB/s, synker den sakte ettersom indeksen vokser, men hvis selve tekstene ikke lagres, så ser det ut til at det legger seg. For alle de samme bugzilla-dataene var resultatet et gjennomsnitt på 522 KB/s, selv om det ved slutten av indekseringen var mindre enn ved begynnelsen.
• Søkehastighet:
  • I 5 tråder på 3 ord - et gjennomsnitt på 28 ms, maksimalt 2,1 sekunder.
  • I 5 tråder på 2 ord - et gjennomsnitt på 54 ms, maksimalt 2,3 sekunder.
  • I 5 tråder på 3 ord er de 10 første resultatene i gjennomsnitt 26 ms, maksimalt 611 ms.
  • I 1 tråd på 3 ord - i gjennomsnitt 10 ms, maksimalt 213 ms.

Lucene, Solr (3.3)

• Lucene er et Java-søkebibliotek (ikke en server), det er veldig vanskelig å gjennomgå og teste det fullstendig - motoren er den kraftigste (men også den mest monstrøse) av alle de som er anmeldt.
• Det faktum at dette er et bibliotek skrevet i Java er dens største ulempe - å få tilgang til Java fra andre språk er vanskelig, derfor har Lucene også problemer med grensesnitt :(. Ytelse fra Java kan også lide noe, men mest sannsynlig er det veldig ukritisk.
  • Av bindingene til språk er det bare en fullstendig levende PyLucene - en JVM med Lucene ombord legges til Python-prosessen, og en viss JCC sørger for interaksjon. Men jeg vil sterkt vurdere om jeg skal bruke en slik kombinasjon...
• For å forbedre situasjonen er det Solr – tross alt en søkeserver implementert som en webtjeneste med XML/JSON/CSV-grensesnitt. For å kjøre, krever det en servletbeholder - Tomcat, eller for å gjøre det enklere - Jetty. Nå kan du jobbe med det fra mange språk.
• Det er oppgitt at indekseringshastigheten til Lucene er "som, veldig høy", mer enn 20 MB/s, mens det kreves veldig lite minne (fra 1 MB), og inkrementell indeksering (for ett dokument) er like raskt som å indeksere et sett dokumenter på en gang. Indeksstørrelsen er oppgitt til 20-30 % av datastørrelsen.
• Lucene er veldig utvidbar, så det er mange forskjellige funksjoner og gadgets, spesielt når de kombineres med Solr og andre biblioteker:
  • 31 innebygde stemmer, en haug med analysatorer - behandler lyd (Soundex, Metaphone og varianter), forkortelser, stoppord, synonymer, "beskytte ord" (omvendt av stoppord), fraser, helvetesild, ordseparasjon (Wi-Fi , WiFi - > Wi Fi), URL-er og så videre, mange ulike alternativer generering av spørringer (for eksempel FuzzyLikeThisQuery - søk etter "en spørring som ligner på den gitte").
  • Indeksreplikering, automatisk clustering (gruppering) av søkeresultater (Carrot2), søkerobot (Nutch), støtte for parsing av binære dokumenter (Word, PDF, etc.) ved hjelp av Tika.
  • Det er til og med en gadget for å "heve" gitte resultater for gitte søk, uavhengig av normal rangering (hei, SEO).
  • Og selv det er ikke alt.
• Indeksstørrelsen er helt Lucene-lignende - 20 % av dataene. Solrs indekseringshastighet for 256 dokumenter per forespørsel, uten mellomliggende bindinger, var 2,75 MB/s, og med commits for hver 1024 dokumenter - 2,3 MB/s. Hvis du ikke forplikter deg, så spiser det opp mer minne - jeg har rundt 110 MB bosatt, hvis du forplikter - 55 MB.
• Solr søkehastighet:
  • I 5 tråder på 3 ord - gjennomsnittlig 25 ms, maksimalt 212 ms.
  • I 5 tråder på 2 ord - et gjennomsnitt på 35 ms, maksimalt 227 ms.
  • I 5 tråder på 3 ord er de 10 første resultatene i gjennomsnitt 15 ms, maksimalt 190 ms.
  • I 1 tråd på 3 ord - gjennomsnittlig 11 ms, maksimalt 79 ms.

2.3.3.4, Lucene++ 3.0.3.4

• Lucene er skrevet i Java, og derfor er det en rekke porter av det til forskjellige språk, hvorav de mest livlige er C++- og C#-portene - , Lucene++ og Lucene.NET. Det finnes andre porter, men de er (halv)forlatte og/eller ustabile.
• Ikke alt er perfekt med CLucene heller:
  • Lucene utvikler seg langsommere - mens Lucene allerede er 3.3, tilsvarer CLucene stabil (0.9.2.1) fortsatt Lucene 1.9, og den har ikke engang stemmer, og CLucene "testing" er Lucene 2.3.
  • Det er få/utdaterte språkbindinger, for eksempel støtter Perl-bindinger kun 0.9.2.1. Den heter «Skriv din egen». Etter å ha brukt et par timer, lappet jeg dem (og ga en feil til forfatterne) og la til og med støtte for stemmere, som heldigvis fortsatt eksisterer i 2.3. Generelt er disse bindingene litt fuktige, jeg har allerede fanget og lappet en annen segfault.
  • Tilsynelatende er det feil, dokumentasjonen på Internett er utdatert (men du kan generere normal dokumentasjon ved å bruke doxygen fra kilden), den ligger på SourceForge, hvor alt er tregt og trist, og feilsporeren lukker fra tid til annen feil seg selv (hvis ingen svarer dem O_O ).
• Når det gjelder funksjoner, er de fleste av Lucene-funksjonene i portene. Naturligvis er det ingen Solr-funksjoner.
• CLucene-indekseringshastighet - jeg fikk 3,8 MB/s. Ikke de 20+ deklarert av Lucene, men dette er med en stemmer og gjennom et Perl-grensesnitt, så det er ganske bra.
• Indeksstørrelsen viste seg i likhet med Lucene/Solr å være omtrent 20% av datastørrelsen - dette er rekord blant alle motorer, og tilsvarer de oppgitte 20-30%!
• Lucene++ skiller seg fra CLucene på følgende måter:
  • Implementeringen er mer komplett og nyere (3.0.3.4), for eksempel finnes det analysatorer for forskjellige språk med innebygde stoppord.
  • Lucene++ overalt bruker shared_ptr (automatisk telling av referanser til objekter ved bruk av C++-maler). Dessuten er dette veldig merkbart selv under kompilering; det tar veldig lang tid sammenlignet med CLucene.
  • Bindingene er enda verre enn i CLucene - det er bare halvdøde for Python, generert av SWIG - det vil si at de sannsynligvis flyter som jævler, og det er generelt ukjent om de fungerer, selv om jeg, for å være ærlig, ikke engang umiddelbart forstå hvordan du lager Perl normalt -bindinger til disse shared_ptrs.
  • Lucene++ ser ut til å bli brukt veldig lite, å dømme etter det faktum at det bare er 9 feil i feilsporeren.
• Søkehastighet - målinger som ligner på Xapian-målinger, bruker bare MultiFieldQueryParser i stedet for å erstatte ord med disjunksjoner:
  • I 5 tråder på 3 ord oppnås et gjennomsnitt på 10 ms, med maksimalt 212 ms.
  • I 5 tråder på 2 ord - et gjennomsnitt på 19 ms, maksimalt 201 ms.
  • I 5 tråder på 3 ord er de 10 første resultatene i gjennomsnitt 3 ms, maksimalt 26 ms.
  • I 1 tråd på 3 ord - i gjennomsnitt 4 ms, maksimalt 39 ms.
  • Igjen, det avhenger hovedsakelig av mengden funnet, som tilsvarer notatet om kompleksiteten til søket.

For de i tanken

• En invertert indeks samsvarer med hvert ord med settet med dokumenter det vises i, i motsetning til en direkte indeks, som samsvarer med et dokument med et sett med ord. Nesten alle fulltekstsøkemotorer bruker inverterte indekser, fordi de er raske å søke etter, selv om de er vanskeligere å oppdatere enn direkte indekser.
• Stemmer - fra det engelske ordet "stem" - grunnlaget for ordet. Han biter av slutten på ordene og gjør dem om til stammer. Designet slik at ordet "katt" skal matche "katter" og "katt", og så videre. Snowball - DSL for å skrive stemmer.
• Stoppord er en liste over svært ofte brukte ord (preposisjoner, konjunksjoner osv.), som det ikke nytter å indeksere, fordi de inneholder liten betydning og finnes nesten overalt.
• Posisjonsinformasjon - posisjonene til ord i dokumenter, lagret i en indeks, for videre søk etter setninger eller bare ord som ikke befinner seg lenger fra hverandre enn ...
• Prefikssøk (ord*) - søk etter ord som begynner med et gitt ord (for eksempel katter*). Noen ganger kalt et jokertegn-søk, men strengt tatt er et jokertegn et søk etter ord som begynner med et gitt prefiks og slutter med et gitt suffiks (for eksempel ko*a - vil finne både ordet "katt" og "koala"). .
• Bugzilla er en åpen kildekode-feilsporer som brukes i selskapet vårt, på innholdet som søket ble testet på.

sammenligningstabell

Rangering av resultater og sortering etter ulike felt er overalt.

I tillegg:

Konklusjon

Den enkleste og raskeste motoren er Sphinx. Ulempen er at de oppdaterte indeksene der ennå ikke er veldig brukbare - de kan kun brukes hvis du aldri sletter noe fra indeksen. Hvis dette løses, vil problemet med valg forsvinne helt, Sphinx vil gjøre alt.

Også rask, svært funksjonell, effektiv og utvidbar, men ikke den enkleste å bruke motoren - Lucene. Hovedproblemet med grensesnitt er enten Java- eller C++-porter og problemer med bindinger. Det vil si at hvis du ikke skriver i Java, C++, Python eller Perl, må du bruke Solr. Solr spiser allerede litt minne, indekserer og søker litt saktere, det kan være upraktisk som en egen Java-server i en servletbeholder, men den har en enorm haug med forskjellige muligheter.

Xapian... Søker raskt, indekserer ikke særlig godt, og selve indeksen er for stor. Plusset er en haug med grensesnitt for forskjellige språk (C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua). Hvis en modus ser ut til å deaktivere indeksering av eksakte skjemaer, vil størrelsen på indeksen umiddelbart reduseres med en faktor 2.

Hvis du allerede bruker PostgreSQL og er villig til å tåle ikke veldig høye indekseringshastigheter og fullstendig fravær av vanskelige søkeoperatorer, kan du bruke Textsearch, fordi det søker raskere enn MySQL og er ganske sammenlignbart med de andre. Men du må huske at indeksen må opprettes på en reell kolonne av typen tsvector , og ikke på uttrykket to_tsvector().

MySQL FULLTEXT kan også brukes i enkle tilfeller når databasen er liten. Men under ingen omstendigheter bør du gjøre en MATCH (flere felt) og under ingen omstendigheter bruke prefikssøk.

Eventuelle endringer i denne artikkelen vil bli overskrevet i løpet av neste replikeringsøkt. Hvis du har en seriøs kommentar om teksten i artikkelen, skriv den ned i "diskusjon"-delen.