Kokotekstihakukoneiden vertailu. Case: hakukoneen opettaminen tunnistamaan kielioppivirheet. Hae indeksoitujen asiakirjojen tietokannasta

Hei hub.
Pari kuukautta sitten sain tilauksen kehittää verkkosivusto. Sivusto oli kokoelma käyttäjän lisäämiä artikkeleita. Yksi kohdista tehtävänkuvaus oli haun luominen. Koska Olen suuri pyörän keksimisen fani, joten päätettiin olla käyttämättä hakua Yandexista tai Googlesta.

Säännöllinen haku

Triviaalisin ratkaisu oli jakaa artikkelit sanoiksi, jakaa kysely sanoiksi ja etsiä osumia.
Plussat:

Suuri nopeus. Voidaan käyttää tähän heti mysql taulukko sanoilla
Yksinkertaisuus. Tällaisen algoritmin käsikirjoitus kestäisi vain muutaman kymmenen rivin.

alhainen tarkkuus, virheenkorjauksen puute

Sumea haku

Joten päätettiin tehdä kaikki kuten "aikuiset" tekevät. Nuo. automaattinen virheenkorjaus ja haku ei vain tarkkojen sanojen, vaan myös sanamuotojen perusteella. Koska Halusin enemmän suorituskykyä, hakua ei kirjoitettu PHP:llä, vaan Javalla, joka roikkui jatkuvasti muistissa ja tallensi artikkelihakemiston.

Stemmer

Ensin meidän piti päättää, kuinka yhden sanan eri muodot yleistetään. Oletamme sen identtisiä sanoja Nämä ovat sanoja, joilla on sama juuri. Mutta juuren purkaminen ei ole helppo tehtävä. Ratkaisin tämän ongelman, googletin nopeasti ns. "Potter stemmer" (tekijän verkkosivusto). Potterin varsi tunnistaa sanan juuren, joka ei kuitenkaan aina ole sama kuin leksikaalinen. Lisäksi se on kirjoitettu varten eri kieliä, myös venäjäksi. Venäläinen esimerkki on kuitenkin kirjoitettu PHP:llä ja kirjoitettuani sen uudelleen Javalla yksi yhteen, sain erittäin huono esitys. Ongelma ratkaistiin käyttämällä säännöllisiä lausekkeita. Inhoamisen takia säännöllisiä lausekkeita minä otin valmis esimerkki www.algorithmist.ru/2010/12/porter-stemmer-russian.html (Kiitos kirjoittajalle).
Tuloksena oli suorituskyky 1 miljoonan sanan tasolla sekunnissa.

Kirjoitusvirheiden korjaaminen

Usein käy niin, että käyttäjä tekee virheen kirjoittaessaan pyyntöä. Siksi tarvitsemme algoritmin sanojen samankaltaisuuden määrittämiseksi. Tähän on monia menetelmiä, mutta nopein on 3 gramman menetelmä. Sen olemus on seuraava: Jaamme sanan kolmeen peräkkäiseen kirjaimeen. Teemme samoin toisen kanssa. Esimerkki:
Perustuslaki => CON ONS NST STI TIT ITU TUTS UTS TSIYA
Constitution=> CON ONS NST STT TTU TUTS UTSIYA

Sitten vertaamme näitä kolmosia ja mitä enemmän identtisiä kolmosia saamme, sitä suurempi on sanojen samankaltaisuus.
Yhteensä meillä on 6 kolmoa kahdeksasta eli 75 %.
Tämä menetelmä on hyvä, kun ylimääräinen kirjain puuttuu tai se on lisätty kyselyyn. Mutta kun henkilö korvaa yhden kirjaimen toisella, saamme heti 3 kolmosta. Yleensä ylimääräinen tai puuttuva kirjain on kuitenkin kirjoitusvirhe. Mutta korvattu on kirjoitusvirhe. Millaisia virheitä nämä ovat:

A – o:n ja o-a:n vaihto: maloko, pAbeda, rOdon
E-e, e-e. Bida, Perog
On väärin käyttää pehmeitä ja kovia merkkejä.

Laitetaan siis kaikki yhteen muotoon:

Yksityinen merkkijono korvaa(merkkijonosana) ( sana=sana.korvaa("a","o"); sana=sana.korvaa("e","i"); sana=sana.korvaa("b","p "" sana=sana.korvaa("d","t"); = sana.korvaa("ъ","ь" sana=sana.korvaa("zh","w");

Siksi meidän täytyy käydä läpi kaikki saatavilla olevat sanat ja löytää samankaltaisin. Miljoonalla sanalla tämä on noin 1 s, mikä ei ole hyväksyttävää. Optimoidaan. Aluksi oletetaan, että olemme kiinnostuneita sanoista, joiden pituus eroaa enintään 2 kirjaimella. Sitten huomautamme, että alkaen kolme kirjainta on vain 30 000 muunnelmaa (33 * 33 * 33), joten kokonaisalgoritmi on seuraava:

Merkkijono grammat=get3gram(sana); int i = 0; for (String gram:gramms) ( if (this.tgram_abc[i]==null) this.tgram_abc[i]=new ArrayList(); this.tgram_abc[i].add(id); i++; )

Seuraavaksi teemme saman sanalle, jossa on "pienennetyt" kirjaimet, korvaa sitten nn n:llä ja lisää se kolmanteen taulukkoon ja poista lopuksi kaikki pehmeät merkit.
Nyt voit etsiä samankaltaisia sanoja. Jaamme sanat grammoiksi, löydämme kunkin kolminkertaisen hajautusarvon ja saamme luettelon sanoista, joissa jotkut ovat samanlaisissa asemissa.

HashMap GramBalls=new HashMap(); int AlkuG=(i-2>=0)?i-2:0; int EndG=(i+2); for (int l = len-2; l<=len+2;l++) for (int j=StartG;j<=EndG;j++) if (this.tgram_abc[l][j]!=null) for (int id:this.tgram_abc[l][j]) if (!GramBalls.containsKey(id)) GramBalls.put(id, (1-(double)Math.abs(len-l)/3) /(word.length()-2));

Viimeisellä rivillä on satunnaisesti johdettu kaava, mikä tarkoittaa, että lopussa oleva trigrammi tuo sanan 0,7 pistettä/trigrammien lukumäärä. Ja ensimmäinen tuo 1 pisteen/grammamäärä.
Sitten etsimme samalla tavalla kyselystä "vähennetty" sana ja sana, jolla on korvattu nn ja pehmeät merkit. Totta, 1:n sijasta tulee 0,7 ja 0,3.
Sitten lajittelemme sanat pisteiden mukaan ja valitsemme sanan, jolla on eniten pisteitä. Jos "mestarilla" on kuitenkin vähemmän kuin 0,1 pistettä, palautetaan nolla. Tämä on välttämätöntä, jotta vältetään täysin erilaisten sanojen huomioon ottaminen. Koska Yllä oleva algoritmi määrittää, että "astronautin" ja "astman" samankaltaisuus on 0,05.

Indeksointimekanismi

"Aikuisille" indeksoinnin suorittavat erityiset hämähäkkiohjelmat, jotka ajoittain indeksoivat sivustoja, indeksoivat sisältöä, etsivät linkkejä sivulta ja seuraavat niitä edelleen. Meillä kaikki on yksinkertaista. Kun lisäät sivua, php-skripti lähettää hakukoneellemme pyynnön indeksoida sivu. Seuraavaksi sivu puhdistetaan tunnisteista. Sitten se hajoaa sanoiksi. Tämän jälkeen määritetään sanan kieli. Käymme sanan läpi ja lisäämme jokaiselle kirjaimelle pisteen kielille, jotka tukevat kyseistä merkkiä. Venäjällä se on a-z ja yhdysmerkki "-" englanniksi a-z, yhdysmerkki ja heittomerkki ('). Kaikki symbolit ja numerot laitetaan erilliselle "symbolikielelle".
Tallennusta ja nopeaa hakua varten meillä on joukko sanaluetteloita.

ArrayList WordIndex[tekstikieli][palvelutekstihakemisto][sanakieli]

Tämä luettelo tallentaa sanan sijainnin artikkelissa ja artikkelin id:n.
Samalla tavalla luomme taulukon sanajuurien tallentamiseksi.
Seuraavaksi otamme otsikon ja indeksoimme sen toisena tekstinä.

Haku- ja sijoitusmekanismi

Tämä on minkä tahansa hakukoneen tärkein mekanismi. Käyttäjien mielipide riippuu siitä, kuinka oikein se luo tuloksia.
Kun käyttäjä napsauttaa hakupainiketta, php-skripti välittää pyynnön hakukoneelle. Hän jakaa sen sanoiksi. Vain tässä on yksi ero indeksointiin. Jos artikkelia lisättäessä, kun kohtaamme tuntemattoman sanan, lisäämme sen sanaluetteloon, niin kun kohtaamme kyselyssä tuntemattoman sanan, etsimme samankaltaisinta 3 gramman menetelmällä.
Jakamisen jälkeen jokaisesta sanasta saamme luettelon tekstin id - sanan esiintymispareista.
Selvitetään, kuinka sopiva artikkeli sopii pyyntöön:

Lasketaan kuinka monta sanaa kyselyistä artikkelissa on.(a)
Lasketaan kuinka monta kyselyn juuria artikkelissa on.(b)
Lasketaan kuinka monta sanayhdistelmää on samankaltaisia kuin kyselyn sanayhdistelmiä (c)
Lasketaan kuinka monta juurisanayhdistelmää on samankaltaisia kuin kyselyn sanayhdistelmät (d)
Määritetään kuinka monta sanaa kyselystä esiintyy artikkelissa(e)
Määritetään kuinka monta juurta on kyselystä (f)

Sen jälkeen lisäämme pisteitä jokaiseen artikkeliin seuraavan kaavan mukaan:

Math.log(2*a+1)+ Math.log(2+1)+2+Math.log(c*5+1))+ Math.log(d*3+1)))*(f+ 2) *e));

Kaava luotiin seuraavien periaatteiden mukaisesti:

Sanat menevät juurien edelle
Lauseet ovat tavallisten sanojen edelle
Mitä kattavammin artikkeli kuvaa hakukyselyä, sitä korkeampi on sen luokitus. Lisäksi täydellisyys on avainasemassa

Seuraavaksi käydään otsikot läpi, vain siellä kerrotaan pisteet 10:llä, koska... Otsikko heijastaa artikkelin ydintä.
Lajittelemme ja näyttelemme.
Yllä oleva algoritmi käsittelee 100 pyyntöä sekunnissa 1000 artikkelin indeksillä VPS:ssä, jossa on 1 GHz:n prosessori.
P.S. Tämä artikkeli esittelee vain joitain sumean haun algoritmeja ja ideoita.

Kun Netpikov-työntekijä kohtaa aikaa vaativan tehtävän (esimerkiksi Death Star -projektin luominen tai kompaktin kylmäfuusiolaitteen rakentaminen), hän miettii ennen kaikkea, kuinka tämä työ automatisoidaan. Keräämme tällaisten pohdintojen tulokset verkkosivustomme erityiselle sivulle. Tänään puhumme siitä, kuinka uusi hyödyllinen palvelu syntyy Netpeak-toimiston sisimmässä.

Kauan sitten, kaukaisessa galaksissa, päätimme muuttaa asiakkaan sivuston hakukonetta lisätäksemme sivujen näkyvyyttä orgaanisessa haussa.

Tehtävä

Asiakasprojektin hakukone, jonka kanssa meidän piti työskennellä, loi erillisen sivun jokaiselle pyynnölle. Koska kyselyt sisältävät toisinaan kirjoitusvirheitä, tällaisia sivuja on kertynyt kokonainen - sekä oikeita että virheellisiä. Yleensä - yli kaksi miljoonaa sivua: yhtä paljon venäjäksi ja englanniksi. Sivut, joissa oli virheitä, indeksoitiin ja tukkivat tulokset.

Tehtävämme oli varmistaa, että kaikki kyselyvaihtoehdot - sekä oikeat että virheelliset - johtivat yhdelle sivulle. Esimerkiksi jokaisella kyselyllä baseball, basaball, baaeball, baselball oli omat sivunsa, mutta oli tarpeen varmistaa, että kaikki vaihtoehdot sulautuvat yhdelle sivulle oikealla haulla - baseball. Tässä tapauksessa sivu vastaa oikeaa pyynnön muotoa ja voimme päästä eroon hakutuloksista.

Esimerkkejä ryhmistä:

On syytä huomata, että virastoihin ei aina luoteta muutoksia verkkosivuston moottoriin. Siksi olemme kiitollisia asiakkaallemme mahdollisuudesta toteuttaa tämä projekti.

Kohde

Luo selkeä toimintamekanismi, jonka avulla voit sijoittaa uudelleenohjauksia virheellisten lauseiden sivuilta asiakassivuston sivulle, jolla on oikea lause.

Tämä on tarpeen sekä aloitussivujen indeksoinnin parantamiseksi hakukoneessa että semanttisen ytimen rakentamiseksi ja sen käyttämiseksi uutta sivustorakennetta kehitettäessä. Emme tietenkään tienneet kielten kokonaismäärää, joilla kyselyt syötettiin, mutta suurin osa lauseista oli venäjäksi ja englanniksi, joten keskityimme näihin kieliin.

Kuinka uusi menetelmä syntyi

Yksinkertaisin ratkaisu, joka tulee heti mieleen, on laittaa kyselyt Googleen, ja se korjaa sen rehellisesti puolestamme. Mutta tällaisen leviämisen järjestäminen on melko kallis yritys. Siksi toverini ja minä valitsimme eri reitin. Analyyttinen matemaatikkomme päätti käyttää kielellistä lähestymistapaa (älyttömästä!) ja rakentaa kielimallin.

Mitä se tarkoittaa? Määritämme kielen sanan kohtaamisen todennäköisyyden ja löydämme jokaiselle sanalle todennäköisyydet tehdä siinä erilaisia virheitä. Kaikki olisi hyvin, ja teoria tässä on kaunis, mutta tällaisten tilastojen keräämiseksi tarvitset valtavan merkityn tekstin jokaiselle kielelle (jälleen hakukoneet ovat lähimpänä tätä). Luonnollisesti heräsi kysymyksiä siitä, miten tämä tehdään ja kuka toteuttaa tämän kaiken koodissa. Kukaan ei ollut tehnyt mitään vastaavaa aiemmin (jos tiedät tapauksen, laita linkki kommentteihin), joten menetelmä kehitettiin tyhjästä. Ideoita oli useita, eikä etukäteen ollut selvää, kumpi oli parempi. Siksi odotimme, että kehitystyötä tehdään syklisesti - idean valmistelu, toteutus, testaus, laadun arviointi ja sitten päätettävyys, jatketaanko idean hiomista vai ei.

Tekniikan käyttöönotto voidaan jakaa kolmeen vaiheeseen. Lue lisää jokaisesta niistä.

Vaihe nro 1. Ongelman muodostuminen. Ensimmäinen harava

Huomio! Tämän rivin jälkeen tulee monia termejä, jotka yritimme selittää mahdollisimman yksinkertaisella kielellä.

Koska lisätietoa (sanakirjat, taajuudet, lokit) ei ole saatavilla, ongelmaa yritettiin ratkaista käytettävissämme olevilla resursseilla. Kokeilimme erilaisia klusterointimenetelmiä. Pääajatuksena on, että saman ryhmän sanat eivät saa erota liikaa.

Klusterointi- proseduuri, joka kerää tietoa, joka sisältää tietoa objektinäytteestä ja järjestää sitten kohteet suhteellisen homogeenisiin ryhmiin.

Levenshtein etäisyys näyttää rivin A muutosten (poistot, lisäykset ja korvaukset) vähimmäismäärän, joka on tehtävä rivin B saamiseksi.

Symbolien korvaaminen: sh[e]res — sh[i]res, sh[o]res;
Symbolin lisääminen: sheres - s[p]heres;
Poisto: gol[d][f] - golf, kulta.

Jokaisessa esimerkissä väärin kirjoitetun sanan ja oikean muodon välinen etäisyys on 1 korjaus.

Jaccard-kerroin bi- ja trigrammeissa auttaa selvittämään, kuinka monta yleistä kaksi- tai kolmimerkkisten tavujen yhdistelmää merkkijonoilla A ja B on.

Esimerkki: Tarkastellaan viivoja A = lumilauta ja B = reuna. Bigrammien kertoimen yleinen kaava on:

J = (A:n ja B:n identtisten bigrammien määrä) / (A:n ja B:n bigrammien kokonaismäärä)

Jaetaan rivit isoiksi:

bigrammit A = ( sn, no, ow, wb, bo+, oa, ar, rd+ ) - 8 kpl; bigrammit B = ( bo+, or, rd+, de, er ) - 5 kpl; Siinä on kaksi identtistä plusmerkkiä - bo ja rd.

Trigrameille se on samanlainen, vain kahden kirjaimen sijasta käytetään kolmea. Jaccard-kerroin heille on seuraava:

Esimerkki samankaltaisista sanoista:

A = pesäpallo ja B = baaeball ( ba+, as, se, eb+, ba+, al+, ll+ ) ( ba+, aa, ae, eb+, ba+, al+, ll+ ) J = 5 / (7 + 7 - 5) = 0,56

Vaikka Jaccard-kerroin toimii nopeammin, se ei ota huomioon tavujen järjestystä sanassa. Siksi sitä käytettiin pääasiassa vertailuun Levenshteinin etäisyyteen. Teoriassa kaikki oli täällä yksinkertaista. Pienen datan klusterointitekniikat ovat melko helppoja ratkaista, mutta käytännössä kävi ilmi, että erittelyn loppuun saattamiseksi tarvitaan joko valtava laskentateho tai vuosia (ja ihannetapauksessa molempia). Kahden viikon työssä käsikirjoitus kirjoitettiin Pythonilla. Kun se käynnistetään, se luki lauseita tiedostosta ja tulostaa ryhmäluettelot toiseen tiedostoon. Samaan aikaan, kuten mikä tahansa ohjelma, tämä komentosarja latasi prosessorin ja käytti RAM-muistia.

Suurin osa testatuista menetelmistä vaati teratavuja muistia ja viikkoja suoritinaikaa. Sovitimme menetelmät niin, että ohjelma tarvitsi 2 gigatavua muistia ja yhden ytimen. Miljoona pyyntöä käsiteltiin kuitenkin noin 4-5 päivässä. Tehtävän valmistumisaika jätti siis vielä paljon toivomisen varaa. Algoritmin tulos voidaan esittää graafin muodossa käyttämällä pientä esimerkkiä:

Kun sitä sovelletaan asiakasprojektiin, tämä tarkoittaa, että sivut, jotka vastaavat saman klusterin pyyntöjä, liimataan yhteen 301-uudelleenohjauksella. Muistakaamme, että tavoitteemme oli luoda selkeä toimintamekanismi virheellisten lauseiden sivujen uudelleenohjauksille asiakkaan sivuston sivulle, jolla on oikea lause. Mutta jopa tämän esimerkin kanssa puutteet ovat ilmeisiä:

Ei ole selvää, miten ryhmistä löytää oikeat lomakkeet ja onko niitä ollenkaan.
Ei tiedetä, mitä virherajoja käytetään. Jos kynnys on suuri (yli 3 virhettä), ryhmät ovat erittäin suuria ja roskaisia, jos se on liian pieni, niin jokainen sana muodostaa oman ryhmänsä, mikä ei myöskään sopinut meille. On mahdotonta löytää kaikille ryhmille hyväksyttävää yleismaailmallista merkitystä.
Ei ole selvää, mitä tehdä sanoilla, jotka voidaan luokitella samanaikaisesti useisiin ryhmiin.

Vaihe nro 2. Yksinkertaistaminen. Uusi toivo

Olemme suunnitelleet algoritmin uudelleen ja tuoneet sen lähemmäksi perinteisiä mekaanisia kieliopin korjaajia. Onneksi niitä riittää. Pohjaksi valittiin Python-kirjasto Enchant. Tässä kirjastossa on sanakirjoja lähes kaikille maailman kielille, se on melko helppokäyttöinen ja saat vihjeitä korjattavaa. Edellisessä vaiheessa opimme paljon kyselytyypeistä ja siitä, millä kielillä nämä kyselyt voivat olla.

Seuraavat sanakirjat kerättiin avoimesta pääsystä:

englanti (UK);
englanti (USA);
Saksan kieli;
Ranskan kieli;
Italialainen;
Espanja;
Venäjän kieli;
ukrainalainen.

Jos se on oikein (sijaitsee yhdessä sanakirjoista), jätämme sen sellaisenaan;
Jos se on väärin, saamme luettelon vihjeistä ja otamme ensimmäisen vastaantulevan;
Yhdistimme kaikki sanat takaisin lauseeksi. Jos emme ole aiemmin törmänneet tällaiseen lauseeseen, luomme sille ryhmän. Ilmauksen korjatusta muodosta tulee sen "keskus". Jos on, se tarkoittaa, että tällä lauseella on jo oma ryhmä ja lisäämme siihen uuden virheellisen muodon.

Tuloksena saimme ryhmän keskuksen ja sanaluettelon tältä ryhmältä. Täällä tietysti kaikki on paremmin kuin ensimmäisellä kerralla, mutta piilotettu uhka on ilmestynyt. Projektin erityispiirteistä johtuen kyselyissä on paljon erisnimiä. On olemassa ihmisten, kaupunkien, organisaatioiden, maantieteellisten alueiden etu- ja sukunimiä ja jopa dinosaurusten latinankielisiä nimiä. Tämän lisäksi löysimme sanoja, joiden translitterointi oli virheellinen. Joten jatkoimme ratkaisujen etsimistä ongelman ratkaisemiseksi.

Vaihe nro 3. Lisäravinteet ja The Force Awakens

Translitterointiongelma ratkaistiin yksinkertaisesti ja perinteisesti. Ensin teimme sanakirjan kyrillisistä ja latinalaisista kirjaimista.

Sen mukaisesti tarkistettujen sanojen jokainen kirjain muunnettiin ja todettiin, oliko tuloksena olevalle sanalle sanakirjakorjausta. Jos translitterointivaihtoehdossa oli vähiten virheitä, valitsimme sen oikeaksi. Mutta oikeat nimet ovat pähkinää särkyttäväksi. Helpoin tapa täydentää sanakirjoja osoittautui sanojen keräämiseksi Wikipedian kaatopaikoista. Wikillä on kuitenkin myös heikkoutensa. Siellä on melko paljon väärin kirjoitettuja sanoja, eikä niiden suodatusmenetelmä ole vielä ihanteellinen. Olemme koonneet tietokannan sanoista, jotka alkavat isolla kirjaimella ja joiden edessä ei ole välimerkkejä. Näistä sanoista tuli ehdokkaitamme erisnimiksi. Esimerkiksi tällaisen tekstin käsittelyn jälkeen alleviivatut sanat lisättiin sanakirjaan:

Algoritmia toteutettaessa kävi ilmi, että vihjeiden etsiminen Enchantin lisätyssä sanakirjassa vaati joskus yli 3 sekuntia sanaa kohden. Tämän prosessin nopeuttamiseksi käytettiin yhtä Levenshtein-automaatin toteutuksista.

Lyhyesti sanottuna koneen idea on, että rakennamme siirtymäkaavion olemassa olevan sanakirjan avulla. Samalla tiedämme etukäteen, kuinka monta sanakorjausta hyväksymme. Jokainen siirtymä tarkoittaa, että teemme jonkinlaisen muunnoksen sanan kirjaimille - jätämme kirjaimen tai käytämme jotakin korjaustyypeistä - poistamista, korvaamista tai lisäämistä. Ja jokainen kärkipiste on yksi vaihtoehdoista sanan muuttamiseen.

Sanotaan nyt, että meillä on sana, jonka haluamme tarkistaa. Jos siinä on virhe, meidän on löydettävä kaikki meille sopivat korjausmuodot. Johdonmukaisesti alamme liikkua järjestelmän mukaan, käymällä läpi tarkistettavan sanan kirjaimet. Kun kirjaimet loppuvat, löydämme itsemme yhdestä tai useammasta kärjestä, ja ne näyttävät meille oikeiden sanojen vaihtoehdot.

Kuvassa näkyy kone sanalle ruoka, jossa on kaikki mahdolliset kaksi virhettä. Ylösnuoli tarkoittaa merkin lisäämistä nykyiseen kohtaan. Nuoli vinottain tähdellä tarkoittaa korvaamista, nuoli epsilonilla tarkoittaa poistamista ja vaakasuora nuoli tarkoittaa, että kirjain pysyy ennallaan. Otetaan sana fxood. Se vastaa koneen polkua 00-10-11-21-31-41 - mikä vastaa x-kirjaimen lisäämistä f:n jälkeen sanaan ruoka.

Lisäksi teimme lisätyötä kerättyjen pääsanakirjojen laajentamiseksi, suodatimme etukäteen ei-sanakirjalausekkeet (tuotemallien nimet ja erilaiset tunnisteet) automaattisesti, otimme käyttöön translitteroinnin ja haun lisäsanakirjassa.

Mikä on tulos?

Algoritmin päivitystyö on vielä kesken, mutta jo tässä kehitysvaiheessa meillä on työkalu, jolla voidaan siivota roskat, kuten tagipilvet, ja liimata tarpeettomia sivuja yhteen 301-uudelleenohjauksilla. Tällainen työkalu on erityisen tehokas pienelle määrälle väärin kirjoitettuja sanoja, mutta se näyttää myös melko tyydyttäviä tuloksia suurilla taulukoilla. Skriptin väliversio lähetettiin asiakkaalle linkityslohkon muodostamiseksi. Tämän lohkon avulla voit kerätä lisätietoja kyselyn korjauksista. Emme lähettäneet skriptin täydellisiä tuloksia käyttöönotettaviksi, koska työskentelemme edelleen käsikirjoituksen laadun parantamiseksi.

Koodin luominen ja testaus veivät matemaatikko-analyytikon työtä yhteensä 40 tuntia. Johtopäätös: jos jonain päivänä joudut käsittelemään noin kaksi miljoonaa pyyntöä, älä masennu. Tällaiset tehtävät voidaan automatisoida. On selvää, että 100% tarkkuuden saavuttaminen on erittäin vaikeaa, mutta on mahdollista käsitellä vähintään 95% tiedosta oikein.

Indeksejä voidaan luoda vain MyISAM-taulukoiden kenttiin.
Indeksin koko on noin puolet datan koosta. Sinun on kuitenkin pidettävä mielessä, että et voi poistaa itse tekstien tallennusta käytöstä, joten tähän 50%:iin on lisättävä vielä 100% - tiedot tallennetaan.
Indeksointinopeus on puhtaassa muodossaan kohtuullinen, noin 1,5 MB/s. On selvää, että sinun täytyy silti ajaa se varren läpi. Jos täytät indeksin vetämällä tiedot samasta tietokannasta lennossa ja ajamalla ne Russian Snowball stemmerin Perl-portin kautta, saat 314 KB/s. Itse asiassa MySQL:ssä on arkkitehtuuri stemmerien yhdistämiseen laajennuksilla ("fulltext parser plugins"), mutta jotenkin itse liitännäisiä ei ole... :)
Sisäänrakennettua varsaa ei ole, englanninkieliset lopetussanat on upotettu, et voi lisätä omiasi. Oletusarvoisesti Boolen haku on "OR", joten jos haluat etsiä käyttämällä "AND", sinun on muutettava jokainen sana "+sanaksi".
On kaksi tilaa - Boolen ja normaali ("luonnollinen kieli") haku. Boolen haku vain tarkistaa, onko asiakirjassa sanoja, ja tukee Boolen operaatioita, lauseita ja etuliitehakuja, mutta ei palauta osuvuuspisteitä (vain 0 tai 1). Säännöllinen haku voi olla merkityksellinen, mutta ei operaattorit. Siksi, jotta voit tukea molempia, sinun on suoritettava sama pyyntö kahdessa tilassa.
- Etuliitehaku MySQL:ssä lumoava hidas. Muutamalla sanalla, joka on laajennettu etuliitteisiin, se voi kestää helposti 15 tai 40 sekuntia. Sitä ei siis tarvitse käyttää ollenkaan.
Se ei voi etsiä useista kentistä samanaikaisesti - eli MATCH():n syntaksi sallii sen, mutta hakua ei optimoida, vaan suoritetaan täysi tarkistus. Siksi on parempi kirjoittaa (valitse id missä match(kenttä1) ...) UNION (valitse id jossa match(kenttä2) ...) .
Hakunopeus satunnaisista virheiden otsikoista otettujen kyselyjen kohdalla, rajoitus 1000 löydettyä:
- 5 säiettä 3 sanalla - keskimäärin 175 ms, maksimi 3,46 sekuntia.
- 5 säiettä 3 sanalla, ensimmäiset 10 tulosta ovat samat.
- 5 säiettä kahdella sanalla - keskimäärin 210 ms, maksimi 3,1 sekuntia.
- 1 säikeessä 3 sanalla - keskimäärin 63 ms, maksimi 764 ms.
- Riippuu lähinnä löydetystä määrästä.
Suurin etu on "kipinä"-haun läsnäolo.

Sphinx (2.0.1-beta)

Erillinen hakupalvelin. Sitä varten on käyttöliittymäkirjastoja useille eri kielille. On erittäin siistiä, että versiossa 0.9.9 "alkuperäisen" käyttöliittymän lisäksi ilmestyi SphinxQL - SQL-rajapinta Sphinxille MySQL-protokollaa käyttävien eli tavallisten MySQL-asiakkaiden avulla.
Aluksi Sphinxissä ei ollut päivitettyjä (reaaliaikaisia) indeksejä, ainoa asia, jonka se pystyi tekemään, oli rakentaa koko indeksi ja sitten etsiä sitä.
Se ei vieläkään osaa päivittää/poistaa asiakirjoja hakemistossa oikein, se vain lisää normaalisti. Poistaminen suoritetaan valitsemalla "vanha merkintä" -valintaruutu ja poistamalla se joka kerta kaikista hakutuloksista.
Reaaliaikaiset indeksit eivät tue kaikkea - esimerkiksi ne eivät tue etuliitteitä/infixejä ja MVA:ta.
Hieman sotkua käyttöliittymien ja ominaisuuksien kanssa: reaaliaikaisen indeksin päivittäminen vain SphinxQL:n kautta; hakusyntaksi on erilainen kaikissa kolmessa rajapinnassa (säännöllinen, SphinxQL, SphinxSE); kappaletta 5 hakutilaa, joista 4 on vanhentunutta; indeksoija ei voi rakentaa uudelleen reaaliaikaisia indeksejä; Indeksiä on mahdotonta katkaista SphinxQL:n avulla, etkä näe, kuinka monta tietuetta indeksissä on...
Tähän loppuvat haitat - on hakupalvelin, jonka kanssa voit kommunikoida käyttämällä omaa protokollaa tai MySQL-protokollaa, joukko erilaisia mahdollisuuksia, indeksoi ja hakee erittäin nopeasti, indeksin koko on noin 1/3 tiedosta. Se voi kasvaa 2 kertaa, jos otat käyttöön tarkkojen sanamuotojen indeksoinnin.
Sisäänrakennetut venäjän, englannin ja tšekkiläiset varsiosat sekä Soundex- ja Metaphone-esiprosessorit (englanninkielisten sanojen vertaamiseen äänen perusteella). Myös muiden kielten stemmerit voidaan yhdistää, sinun tarvitsee vain rakentaa ne --with-libstemmer-näppäimellä. Tietysti stop-sanoilla on tukea. Myös synonyymejä, ja on tavallisia, ja on "tokenizing poikkeuksia", jotka voivat sisältää erikoismerkkejä. On myös "blend_chars" - merkkejä, joita pidetään sekä erottimina että sanojen osana - esimerkiksi niin, että "AT&T" muuttuu sanoiksi "AT", "T" ja "AT&T".
Hienoista epätavallisista ominaisuuksista - se voi tehdä infix-haun (niille, jotka halusivat etsiä nopeasti alimerkkijonon perusteella!), moniarvoisia kenttiä (MVA), se voi indeksoida kappaleiden ja lauseiden mukaan ja jopa ennalta määritettyjen HTML-tunnisteiden sisällön perusteella. Se voi myös korostaa etsittyjä sanoja lainausmerkeissä ja paljon muuta. Päivitetyissä indekseissä ei kuitenkaan tueta (vielä?) MVA:ta ja infixejä.
Indeksointi on erittäin nopeaa - nettonopeus reaaliaikaisella indeksillä on 6,7 MB/s (SQL-vedostiedoston lataaminen), tavallisella indeksillä - yleensä 12 MB/s (xmlpipe2-vedostiedoston lataaminen). "Epäpuhdas" nopeus (Perlistä, lennossa tietojen lukeminen MySQL:stä) - 4,5 MB/s. Lisäysten kanssa kaikki luonnollisesti hidastuu paljon - 440 KB / s, I/O-keko on 10,5 Gt ja indeksi on 3 Gt kooltaan 330 Mt dataa.
Haku on yleensä reaktiivinen:
- 5 säiettä 3 sanalla - keskimäärin 7 ms, maksimi 75 ms.
- 5 säiettä kahdella sanalla - keskimäärin 7 ms, maksimi 81 ms.
- 5 säiettä kolmella sanalla, 10 ensimmäistä tulosta keskimäärin 5 ms, maksimi 57 ms.
- 1 säikeessä 3 sanalla - keskimäärin 2 ms, maksimi 35 ms.

Xapian (1.2.6)

Kirjasto, valmiita hakupalvelinta ei ole. C++ API on melko järkevä. Se näyttää tukevan kilpailutyötä (paljon lukijoita, yksi kirjoittaja).
Joukko saatavilla olevia sidoksia eri kielille: C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua.
Indeksi on käänteinen B-puupohjainen indeksi.
Hienoa on, että Xapiania ei tarvitse käyttää nimenomaan kokotekstihakemistona - itse asiassa se on vain käänteisen indeksin toteutus, jota voidaan käyttää haluamallasi tavalla, koska "sanoilla" ei ole rajoituksia. 245 tavun pituusrajoitusta lukuun ottamatta. Teoriassa voit käyttää sitä tietokantana.
Suoraan sanottuna surkea dokumentaatio. Jonkinlainen tietokokoelma, joka ei vielä sisällä kaikkea. Ymmärtääksesi joitain kohtia, sinun on tyhmästi kiivettävä koodiin. Tulin röyhkeäksi ja laitoin virheen jopa tähän aiheeseen - bugi 564. No, se on totta - moottori näyttää olevan melko hyvä, mutta harvat ihmiset tietävät siitä.
Hassua, että kun aloin testaamaan, löysin oudon bugin - libuuidissa segfaultin, joka ei salli tietokannan luomista, jos Image::Magick ladataan rinnakkain. Kävi ilmi, että tämä ei ollut edes ImageMagick-virhe, vaan vielä vakavampi - se oli libc6-virhe! 2.12:ssa ja 2.13:ssa Thread-Local Storagen alustus kirjastoja dynaamisesti ladattaessa on rikki, oi kuinka. Se korjattiin versiossa 2.14, mutta Debianissa on edelleen 2.13. Lisäsin Debianiin bugin 637239 (myös gentoossa ja itse libc:ssä on linkkejä).
Perl-sidokset vaativat viimeistelyn voidakseen valita taustaohjelman, ja oletuksena se ei ole uusin Brass, vaan vakaa Chert. Viimeistely on helppoa. Annoin heille myös bugin tästä aiheesta - bugi 565.
Hakemistossa ei näytä olevan tukea eri kentille, mutta se tehdään lisäämällä jokaisen sanan alkuun etuliitteet: http://xapian.org/docs/omega/termprefixes.html
- Tämä on "virallinen lähestymistapa", Xapian voi tehdä sen itse, määritä vain etuliitteet.
- Tällä lähestymistavalla on ainakin yksi pieni haittapuoli - oletusarvoisesti kysely ei etsi kaikista kentistä, ja jos haluat etsiä kaikista, sinun on lisättävä kyselyyn manuaalisesti TAI.
- Kyllä, dokumentaatio on jälleen epätäydellinen eikä ole oikeassa paikassa - sen pitäisi olla Xapianin käsikirjassa, mutta se on Omega-oppaassa, joka on valmis yksinkertainen CGI-hakukone.
- Epämiellyttävä hetki - löytyi nopeasti bugi kyselyn jäsentäjässä - se luo väärin termejä etsimään sanarunkoja kentistä (joissa on etuliitteet). Indeksoija määrittää alussa kaikkiin varsiin etuliite "Z", eli otsikon sanan "idea" runko (esimerkiksi etuliite T) indeksoidaan nimellä "ZTide". Ja kyselyn jäsentäjä yrittää etsiä sanalla "Tida" eikä tietenkään löydä mitään. Annoin heille bugin 562 tästä aiheesta. Korjattu itse asiassa yhdellä rivillä.
Stemmerit ovat sisäänrakennettuja 15 kielelle, kuten tavallista, luotu Snowballista "a. Pysäytyssanoja (tietysti) ja synonyymejä on tuki. Vielä mielenkiintoisempaa - se voi korjata kirjoitusvirheet ilman sanakirjoja, mutta vain indeksoitujen tietojen perusteella ( on otettava käyttöön asettamalla). Eli esimerkiksi "Xapain" ehdottaa rehellisesti "Xapian" -toimintoa. Tuki on myös "lopettamattomien kyselyiden" etsimiseen, toisin sanoen vihjeille kyselyä kirjaimelta syötettäessä. Itse asiassa tämä on vain *:n lisääminen haun viimeiseen sanaan, mutta ottaen huomioon kyselyn syntaksin vivahteet.
Siellä on myös "Faceted Search" - kokonaisarvojen laskeminen kaikille tai melkein kaikki löydetyt asiakirjat (esimerkiksi enintään 10 000). Toisin sanoen näitä 10 000 dokumenttia ei palauteta sinulle, vaan ne tarkistetaan ja niistä lasketaan jokin kokonaisarvo. Esimerkiksi tällä tavalla voit palauttaa 10 tulosta (sivu) ja samalla vastata kysymykseen "mistä luokista asiakirjat löydettiin?"
On kurjaa, että jos teet flush() (commit) -toiminnon indeksoidessasi kerran 256 bugin välein, nopeus ~1,5 MB/s laskee 412 KB/s:iin ja I/O-toimintojen määrä kasvaa huomattavasti - 10-20 ajat. Periaatteessa tämä on todettu ja loogista mille tahansa käänteiselle indeksille - on paljon optimaalisempaa kerätä muutoksia kuin yrittää päivittää yksi kerrallaan, koska päivitettyjen merkkien määrä kasvaa.
Indeksin koko - he kirjoittavat, että se on suunnilleen yhtä suuri kuin tietojen koko, tämä ei ole niin, todellisuudessa se on 2 kertaa suurempi He kirjoittavat, että jos et tallenna sanojen paikkoja asiakirjoissa tulee 2 kertaa pienemmäksi. Mutta anteeksi, Sphinx tallentaa myös asemat, ja sen indeksi on 2 kertaa vähemmän tietoa. Jos käytät xapian-compactia (tietokannan eheytys) - kyllä, indeksi pienenee, mutta dataa on vielä noin 1,7 kertaa enemmän jäljellä.
- Jep, syy on löydetty - Xapian indeksoi aina sekä perusasiat että tarkat sanamuodot. Tarkkojen lomakkeiden indeksointia ei voi poistaa käytöstä, se on sääli, annoin heille bugin 563 tästä aiheesta.
Hakee nopeasti. Testasin sitä näin: Etsin useita vierekkäisiä vähintään 2 merkin pituisia sanoja STEM_ALL-tilassa, jotka oli otettu virheiden otsikoista (en etsinyt sanalla "OR", vaan "AND") ja korvasin jokaisen sanan. kanssa (sana TAI otsikko: sana TAI yksityinen: sana), eli haettaessa kolmea kenttää yhden sijaan, tulosten määrä rajoitettiin 1000:een.
- 5 säiettä 3 sanalla - keskimäärin 14 ms, maksimi 135 ms.
- 5 säiettä kahdella sanalla - keskimäärin 29 ms, maksimi 137 ms.
- 5 säiettä kolmella sanalla, 10 ensimmäistä tulosta keskimäärin 2 ms, maksimi 26 ms.
- 1 säikeessä 3 sanalla - keskimäärin 7 ms, maksimi 51 ms.
- Hakunopeus riippuu pääasiassa löydettyjen tulosten määrästä, sitä kauemmin haku kestää.

Xapianilla on 3 taustaa (itse indeksin toteutuksia) - uutuusjärjestyksessä Flint, Chert ja Brass. Se on kuin Debianin vanhassa vakaassa, vakaa ja testaava :) versiossa 1.2.x oletustausta on Chert. Ennen Flinttiä oli kvartsia.

PostgreSQL-tekstihaku (9.1)

Indeksi on käänteinen GIN:n (Generalized Inverted iNdex) perusteella. Aikaisemmin nimeltään Tsearch2, jonka ovat luoneet Oleg Bartunov ja Fedor Sigaev.
Siellä on sisäänrakennettuja varsiosia, tuki lopetussanoille, synonyymeille, tesaurus (jokin käsitesanakirja, korvaa sanat muilla "ensisijaisilla"), ISpell-sanakirjoja (vaikka niiden sanotaan olevan hirveän hitaita alustuksen aikana).
Indeksoinnissa on mahdollista liittää jokaiseen lekseemiin ”painotus”, joka ei itse asiassa ole ”painotus”, vaan Xapian-etuliitteen analogi, eli sen kentän nimi, josta lekseemi on peräisin. Tällaisia "painoja" voi olla vain 4 - A, B, C, D, ja tulevaisuudessa niitä voidaan käyttää haussa. Esimerkki tsvectorin "a" rakentamisesta kahdesta kentästä, joissa on "painot": setweight(to_tsvector(yhdistää(otsikko,""), "A") || setweight(to_tsvector(yhdistää(avainsana,")), "B") .
Syödä erillinen toimintoja tulosten rankaisemiseen ja haettujen sanojen korostamiseen sitaateissa. Järjestys voidaan tehdä määrittämällä numeerisia painotuksia yllä oleville ABCD "painoille" (jotka ovat "kenttiä"). Lisäksi oletusarvoisesti painot ovat yhtä suuria kuin (0,1, 0,2, 0,4, 1,0).
Indeksoitua tietotyyppiä kutsutaan tsvectoriksi (tekstihakuvektoriksi). PostgreSQL mahdollistaa funktionaalisten indeksien luomisen, ja oletusopas ehdottaa juuri näiden luomista - CREATE INDEX i ON t USING gin(to_tsvector(<поле>)). Joten tässä se on: älä tee sitä! Muuten tulet erittäin epämiellyttävänä yllättymään pyyntöjen nopeudesta. Muista luoda erillinen sarake, jonka tyyppi on tsvector, lisää siihen tsvector "s" ja luo siihen hakemisto.
- Selitän miksi: tulosten luokittelutoiminto on erillinen ja toimii myös tsvectorin kanssa. Jos sitä ei tallenneta, se on laskettava lennossa jokaisen asiakirjan jokaisen pyynnön yhteydessä, ja tällä on erittäin huono vaikutus suorituskykyyn , varsinkin kun kysely löytää monia asiakirjoja, toisin sanoen jos sisällytät kyselyösi lajittelun osuvuuden mukaan - ORDER BY ts_rank(to_tsvector(field), ) DESC - tulee olemaan paljon hitaampaa kuin MySQL :).
- Samanaikaisesti levytilan optimoinnin vuoksi sinun ei tarvitse tallentaa dokumenttien koko tekstiä hakemistoon.
Hakuoperaattoreita ovat AND, OR ja NOT sekä etuliitehaku. Lähellä olevia sanoja, tarkkoja muotoja tai lauseita ei etsitä.
Indeksin koko on jossain 150 % datan koosta, jos itse tekstejä ei tallenneta, vaan tallennetaan vain tsvector "s.
Indeksointinopeus - vaikka dataa on vähän, 1,5 MB/s, se laskee hitaasti indeksin kasvaessa, mutta jos itse tekstejä ei tallenneta, se näyttää rauhoittuvan. Kaikilla samoilla bugzilla-tiedoilla tulos oli keskimäärin 522 KB/s, vaikka indeksoinnin lopussa se oli pienempi kuin alussa.
Hakunopeus:
- 5 säiettä 3 sanalla - keskimäärin 28 ms, enintään 2,1 sekuntia.
- 5 säiettä kahdella sanalla - keskimäärin 54 ms, enintään 2,3 sekuntia.
- 5 säiettä kolmella sanalla, 10 ensimmäistä tulosta keskimäärin 26 ms, maksimi 611 ms.
- 1 säikeessä 3 sanalla - keskimäärin 10 ms, maksimi 213 ms.

Lucene, Solr (3.3)

Lucene on Java-hakukirjasto (ei palvelin), sitä on erittäin vaikea tarkistaa ja testata kokonaan - moottori on tehokkain (mutta myös hirvein) kaikista arvioiduista.
Se, että tämä on Java-kielellä kirjoitettu kirjasto, on sen suurin haitta - Javaan pääsy muista kielistä on vaikeaa, minkä vuoksi Lucenella on myös ongelmia käyttöliittymien kanssa :(. Myös Java-suorituskyky saattaa kärsiä jonkin verran, mutta todennäköisesti se on erittäin kritiikitöntä.
- Kielten sidoksista on olemassa vain täysin elävä PyLucene - Python-prosessiin lisätään JVM, jossa on Lucene, ja tietty JCC varmistaa vuorovaikutuksen. Mutta harkitsen vahvasti, käyttäisinkö tällaista yhdistelmää...
Tilanteen parantamiseksi on Solr - loppujen lopuksi hakupalvelin, joka on toteutettu verkkopalveluna XML/JSON/CSV-liitännöillä. Toimiakseen se vaatii servlet-säiliön - Tomcat, tai yksinkertaistamiseksi - Jetty. Nyt voit työskennellä sen kanssa useilla kielillä.
Sanotaan, että Lucenen indeksointinopeus on "kuten, erittäin korkea", yli 20 MB/s, kun taas tarvitaan hyvin vähän muistia (alkaen 1 Mt) ja inkrementaalinen indeksointi (yhdelle asiakirjalle) on yhtä nopea kuin indeksoida joukko asiakirjoja kerralla. Indeksin kooksi ilmoitetaan 20-30 % datan koosta.
Lucene on hyvin laajennettavissa, joten siinä on paljon erilaisia ominaisuuksia ja vempaimia, varsinkin kun se yhdistetään Solrin ja muiden kirjastojen kanssa:
- 31 sisäänrakennettua stemmeriä, joukko analysaattoreita - prosessoi ääntä (Soundex, Metaphone ja muunnelmat), lyhenteet, lopetussanat, synonyymit, "suojaussanat" (stop-sanojen käänteinen), lauseet, vyöruusu, sanaerottelu (Wi-Fi) , WiFi - > Wi-Fi), URL-osoitteita ja niin edelleen, monia eri vaihtoehtoja kyselyiden luomiseen (esimerkiksi FuzzyLikeThisQuery - hae "kyselyn kaltainen kysely").
- Indeksin replikointi, hakutulosten automaattinen klusterointi (ryhmittely) (Carrot2), hakurobotti (Nutch), tuki binääridokumenttien jäsentämiseen (Word, PDF jne.) Tikan avulla.
- Siellä on jopa gadget, jolla "korottaa" tiettyjä tuloksia tietyille kyselyille, riippumatta normaalista sijoituksesta (hei, SEO).
- Eikä siinäkään vielä kaikki.
Indeksin koko on täysin Lucenen kaltainen - 20% tiedoista. Solrin indeksointinopeus 256 asiakirjalle pyyntöä kohden ilman välivarastointia oli 2,75 Mt/s ja 2,3 Mt/s 1024 asiakirjan siirrolla. Jos et sitoudu, se kuluttaa enemmän muistia - minulla on noin 110 Mt asukasta, jos sitoudut - 55 MB.
Solr-hakunopeus:
- 5 säiettä 3 sanalla - keskimäärin 25 ms, maksimi 212 ms.
- 5 säiettä kahdella sanalla - keskimäärin 35 ms, maksimi 227 ms.
- 5 säiettä kolmella sanalla, ensimmäiset 10 tulosta ovat keskimäärin 15 ms, maksimi 190 ms.
- 1 säikeessä 3 sanalla - keskimäärin 11 ms, enintään 79 ms.

2.3.3.4, Lucene++ 3.0.3.4

Lucene on kirjoitettu Java-kielellä, ja siksi siitä on olemassa useita portteja eri kielille, joista vilkkaimpia ovat C++- ja C#-portit - , Lucene++ ja Lucene.NET. Muita portteja on, mutta ne ovat (puoli)hylättyjä ja/tai epävakaita.
Kaikki ei ole täydellistä myöskään CLucenen kanssa:
- Lucene kehittyy hitaammin - vaikka Lucene on jo 3.3, CLucene stable (0.9.2.1) vastaa edelleen Lucene 1.9:ää, eikä siinä ole edes varsia, ja CLucene "testaus" on Lucene 2.3.
- Kielisidoksia on vähän/vanhentuneita, esimerkiksi Perl-sidokset tukevat vain versiota 0.9.2.1. Sen nimi on "kirjoita oma". Muutaman tunnin viettämisen jälkeen korjasin ne (antaen bugin tekijöille) ja jopa lisäsin tuen stemmereille, jotka onneksi ovat edelleen olemassa 2.3:ssa. Yleensä nämä siteet ovat hieman kosteat, olen jo saanut kiinni ja paikannut toisen segfaultin.
- Ilmeisesti siellä on bugeja, Internetin dokumentaatio on vanhentunut (mutta voit luoda normaalin dokumentaation lähteestä peräisin olevan doxygenin avulla), sitä isännöidään SourceForgessa, jossa kaikki on hidasta ja surullista, ja vianseurantaohjelma sulkee ajoittain bugit itse (jos kukaan ei vastaa niihin O_O ).
Ominaisuuksien osalta suurin osa Lucenen ominaisuuksista on porteissa. Solr-ominaisuuksia ei tietenkään ole.
CLucenin indeksointinopeus - sain 3,8 MB/s. Ei Lucenen ilmoittama 20+, mutta tämä on stemmerillä ja Perl-käyttöliittymän kautta, joten se on melko hyvä.
Indeksikoko, kuten Lucene/Solr, osoittautui noin 20 % datan koosta - tämä on ennätys kaikkien moottoreiden joukossa ja vastaa ilmoitettua 20-30 %!
Lucene++ eroaa CLucenesta seuraavilla tavoilla:
- Toteutus on täydellisempi ja uudempi (3.0.3.4), esimerkiksi analysaattoreita eri kielille, joissa on sisäänrakennetut stop-sanat.
- Lucene++ joka paikassa käyttää share_ptr (automaattinen viittausten laskenta objekteihin C++-malleja käyttäen). Lisäksi tämä on hyvin havaittavissa jopa kokoamisen aikana, ja se kestää hyvin kauan verrattuna CLuceneen.
- Sidokset ovat vielä huonommat kuin CLucenessa - Pythonille on vain puolikuolleita, SWIG:n tuottamia - eli ne luultavasti virtaavat kuin paskiaiset, eikä yleensä tiedetä, toimivatko ne, vaikka rehellisesti sanottuna en edes ymmärtää heti, kuinka Perl saa normaalisti -sidotut näihin share_ptrs-tiedostoihin.
- Lucene++ näyttää olevan käytössä hyvin vähän, päätellen siitä, että vikaseurantaohjelmassa on vain 9 bugia.
Hakunopeus – mittaukset, jotka ovat samanlaisia kuin Xapian-mittaukset, käyttämällä vain MultiFieldQueryParseria sen sijaan, että sanat korvataan disjunktioilla:
- 5 säikeessä 3 sanalla saadaan keskimäärin 10 ms, maksimi 212 ms.
- 5 säikeessä kahdella sanalla - keskimäärin 19 ms, enintään 201 ms.
- 5 säiettä kolmella sanalla, 10 ensimmäistä tulosta keskimäärin 3 ms, maksimi 26 ms.
- 1 säikeessä 3 sanalla - keskimäärin 4 ms, maksimi 39 ms.
- Jälleen se riippuu pääasiassa löydetystä määrästä, joka vastaa huomautusta haun monimutkaisuudesta.

Tankissa oleville

Käänteinen hakemisto vastaa jokaisen sanan asiakirjojen joukkoon, jossa se esiintyy, toisin kuin suora indeksi, joka vastaa asiakirjaa sanajoukon kanssa. Lähes kaikki täystekstihakukoneet käyttävät käänteisiä indeksejä, koska ne ovat nopeasti haettavissa, vaikka niitä onkin vaikeampi päivittää kuin suoria indeksejä.
Stemmer - englannin sanasta "stem" - sanan perusta. Hän puree pois sanojen loput ja muuttaa ne varreksi. Suunniteltu niin, että sana "kissa" vastaa sanaa "kissa" ja "kissa" ja niin edelleen. Lumipallo - DSL varsiosien kirjoittamiseen.
Pysäytyssanat ovat luettelo erittäin usein käytetyistä sanoista (prepositiot, konjunktiot jne.), joita on turha indeksoida, koska niillä on vähän merkitystä ja niitä löytyy melkein kaikkialta.
Sijaintitiedot - sanojen paikat asiakirjoissa, tallennettu hakemistoon, lisähakua varten lauseita tai vain sanoja, jotka eivät ole kauempana toisistaan kuin ...
Etuliitehaku (sanat*) - etsi tietyllä sanalla alkavia sanoja (esimerkiksi kissat*). Joskus sitä kutsutaan jokerimerkkihauksi, mutta tarkasti ottaen jokerimerkkihaku tarkoittaa sanojen hakua, jotka alkavat tietyllä etuliitteellä ja päättyvät tiettyyn päätteeseen (esimerkiksi ko*a - löytää sekä sanat "kissa" että "koala"). .
Bugzilla on yrityksessämme käytössä oleva avoimen lähdekoodin vianseurantaohjelma, jonka sisältöä testattiin.

vertailu Taulukko

	MySQL	PostgreSQL	Xapian	Sfinksi	Solr	CLuseeni
Indeksoinnin nopeus	314 KB/s	522 KB/s	1,36 Mt/s	4,5 Mt/s	2,75 Mt/s	3,8 Mt/s
Hakunopeus	175 ms / 3,46 s	28 ms / 2,1 s	14 ms / 135 ms	7ms / 75ms	25 ms / 212 ms	10 ms / 212 ms
Indeksin koko	150 %	150 %	200 %	30 %	20 %	20 %
Toteutus	DBMS	DBMS	Kirjasto	Palvelin	Palvelin	Kirjasto
Käyttöliittymä	SQL	SQL	API	API, SQL	Verkkopalvelu	API
Sidokset	∀	∀	9	6 + ∀	8	3.5
Hakuoperaattorit	&*"	&*	&*"N-~	&*"N-	&*"N-~	&*"N-~
Simmers	Ei	15	15	15	31	15+CJK
Lopeta sanat, synonyymit	Ei	Joo	Joo	Joo	Joo	Joo
Soundex	Ei	Ei	Ei	Joo	Joo	Ei
Taustavalo	Ei	Joo	Ei	Joo	Joo	Joo

Tulosten luokittelu ja lajittelu eri kenttien mukaan on kaikkialla.

Lisäksi:

Johtopäätös

Yksinkertaisin ja nopein moottori on Sphinx. Huono puoli on, että siellä päivitetyt indeksit eivät ole vielä kovin käyttökelpoisia - niitä voidaan käyttää vain, jos et koskaan poista indeksistä mitään. Jos tämä korjataan, valintaongelma katoaa kokonaan, Sphinx tekee kaiken.

Myös nopea, erittäin toiminnallinen, tehokas ja laajennettava, mutta ei helpoin käyttää moottori - Lucene. Suurin ongelma liitännöissä on joko Java- tai C++-portit ja ongelmat sidoksissa. Eli jos et kirjoita Java-, C++-, Python- tai Perl-kielellä, sinun on käytettävä Solria. Solr syö jo vähän muistia, indeksoi ja etsii hieman hitaammin, se voi olla hankalaa erillisenä Java-palvelimena servlet-säiliössä, mutta siinä on valtava joukko erilaisia ominaisuuksia.

Xapian... Hakee nopeasti, indeksoi huonosti, ja itse indeksi on liian suuri. Sen plussa on joukko käyttöliittymiä eri kielille (C++, Java, Perl, Python, PHP, Tcl, C#, Ruby, Lua). Jos tila näyttää estävän tarkkojen lomakkeiden indeksoinnin, indeksin koko pienenee välittömästi kertoimella 2.

Jos käytät jo PostgreSQL:ää ja olet valmis sietämään liian korkeita indeksointinopeuksia ja hankalia hakuoperaattoreita, voit käyttää Textsearchia, koska se hakee nopeammin kuin MySQL ja on melko verrattavissa muihin. Mutta sinun on muistettava, että indeksi on luotava todelliseen sarakkeeseen, jonka tyyppi on tsvector, eikä to_tsvector()-lausekkeelle.

MySQL FULLTEXT voidaan käyttää myös yksinkertaisissa tapauksissa, kun tietokanta on pieni. Älä kuitenkaan missään olosuhteissa tee MATCHia (useita kenttiä) etkä missään tapauksessa käytä etuliitehakua.

Kaikki tähän artikkeliin tehdyt muutokset korvataan seuraavan replikointiistunnon aikana. Jos sinulla on vakava kommentti artikkelin tekstistä, kirjoita se "keskustelu"-osioon.

Luokittelu

Hakualueen mukaan (ehdollisesti)

Paikallinen

Suunniteltu etsimään tietoa mistä tahansa World Wide Webin osasta, esimerkiksi yhdestä tai useammasta sivustosta tai paikallisesta verkosta.

Maailmanlaajuinen

Suunniteltu etsimään tietoa koko Internetistä tai sen merkittävästä osasta. Tällaisten hakukoneiden edustajia ovat hakukoneet Google, Yandex jne. Hakukoneet etsivät erityyppistä tietoa, esimerkiksi tekstejä, videoita, kuvia, maantieteellisiä kohteita, henkilötietoja jne. Samaan aikaan hakukoneen hakemat tiedostot voi toimia joko tekstimuodossa (esim. .html, .htm, .txt, .doc, .rtf...), grafiikassa (.gif, .png, .svg...) tai multimediassa (video ja ääni ). Toistaiseksi yleisin on haku tekstidokumenteista.

Hakulauseke

Haun aloitustieto on hakukysely.

Toiminnot

Hakukoneet suorittavat useita toimintoja:

Etsi linkkejä

Etsi linkkejä sivuille ja muihin sivuston asiakirjoihin.

Auto

Manuaalitila

Käyttäjät itse lisäävät hakukoneiden tietokantaan linkkejä sivustojensa sivuille

Verkkosivuston asiakirjojen indeksointi

Hakuun liittyvien tietojen poimiminen asiakirjoista, tietojen muuntaminen hakukoneystävälliseen muotoon ja tietojen tallentaminen hakukoneen tietokantaan

Hae indeksoitujen asiakirjojen tietokannasta

Voi koostua useista vaiheista

Hakukyselyä vastaavien asiakirjojen etsiminen

Asiakirjojen järjestys sen mukaan, ovatko ne hakukyselyissä

Asiakirjojen klusterointi

Huomautuksia

Katso myös

Hakukoneet(lista)
Ovat yleisiä
Alueellinen	Accoona (Kiina/USA) Alleba (Filippiinit) Ansearch (Australia/USA/UK/Uusi-Seelanti) Aport (Venäjä) Daum (Etelä-Korea) Guruji.com (Intia) [email protected] (Venäjä) Maktoob (Lähi-itä) Meta.ua (Ukraina) Miner.hu (Unkari) Najdi.si (Slovenia) Onkosh (Lähi-itä) Rambler (Venäjä) Rediff (Intia) SAPO (Portugali) Search.ch (Sveitsi) Sesam (Norja/Ruotsi) Walla! (Israel)
...johtajia
Temaattinen
Metahaku	AskNet.ru Brainboost Clusty Dogpile FarSEER exactus.ru Excite HotBot Info.com Ixquick Krozilo Mamma Metacrawler MetaLib Nygma Myriad Search SideStep Surfwax Turbo10 WebCrawler GlobalFileSearch
Avaa / vapaa
Lasten	AGAKIDS (Venäjä) Ask Kids (Iso-Britannia) Frag Finn (Saksa) Kids AOL (USA) Kids Yahoo! (USA) Quintura Children (Venäjä) Yandex-perhe (Venäjä) Gogul (Venäjä)

Wikimedia Foundation. 2010.

Katso, mitä "hakukone" on muissa sanakirjoissa:

Hakukone- (hakukone): Web-palvelin, joka indeksoi verkkosivut saatavilla olevilla palvelimilla (esimerkiksi Yandex)... Lähde: INTERNET-RESURSSIT. KÄYTTÖPALVELUVAATIMUKSET NÄKÖVAMMAISILLE. GOST R 52872 2007 (hyväksytty Rostekhregulirovaniyan määräyksellä, päivätty... ... Virallinen terminologia

hakukone- Web-palvelin, joka indeksoi saatavilla olevien palvelimien verkkosivut (esimerkiksi Yandex). [GOST R 52872 2007] Aiheet tietotekniikka yleisesti EN hakukone ... Teknisen kääntäjän opas

Internetissä erityinen verkkosivusto, jolla käyttäjä voi tietystä pyynnöstä vastaanottaa linkkejä sivustoille, jotka vastaavat tätä pyyntöä. Hakujärjestelmä koostuu kolmesta osasta: 1 hakurobotti; 2 järjestelmäindeksiä; ja 3 ohjelmaa,...... Taloussanakirja

Internetissä hakukone, joka: lähettää hakupyynnön useille hakukoneille; ja luo yhteenvedon (yhdelle sivulle) vastaanotetuista vastauksista. Englanniksi: Meta-hakukone Synonyymit: Meta caterpillar Englanninkieliset synonyymit: Metacrawler... ... Taloussanakirja

Tämä artikkeli on kirjoitettava kokonaan uudelleen. Keskustelusivulla voi olla selityksiä. Hakukoneohjelmisto- ja laitteistokompleksi web-käyttöliittymällä, joka tarjoaa mahdollisuuden ... Wikipedia

Hakujärjestelmä- – (englanninkielinen hakukone, synonyymit: hakukone, hakukone, hakukone) – Työkalu tiedon etsimiseen Internetistä. Hakukoneen työ koostuu pääsääntöisesti kahdesta vaiheesta. Erikoisohjelma (hakurobotti, kone, agentti,... ... Encyclopedic Dictionary of Media - Hakukone on verkkosivusto, joka tarjoaa mahdollisuuden etsiä tietoa Internetistä. Useimmat hakukoneet etsivät tietoa World Wide Web -sivustoilta, mutta on myös järjestelmiä, jotka voivat etsiä tiedostoja ftp-palvelimista, tuotteista ... ... Wikipediasta

Kirjat

Internetistä yksityiskohtien etsimisen tehokkuudesta I. A. Semenov. Berkleyn tutkimuksen mukaan Internetissä olevan tiedon määräksi arvioitiin vuonna 2003 258,85 teratavua, ja tämä on vain julkisesti saatavilla olevaa dataa. Internet World Statsin mukaan kasvu... e-kirja

Internet-aikakauden alkuvuosina miljoonia tiedostoja tallennettiin tuhansille nimettömille FTP-sivustoille. Tässä lajikkeessa käyttäjien oli melko vaikea löytää ongelmaansa sopivaa ohjelmaa.

Lisäksi he eivät tienneet etukäteen, oliko etsimä työkalu olemassa. Siksi jouduimme tarkastelemaan manuaalisesti FTP-tallennustilaa, jonka rakenne oli merkittävästi erilainen. Juuri tämä ongelma johti yhden modernin maailman keskeisen puolen - Internet-haun - syntymiseen.

/ kuva Mariana abasolo

Luomisen historia

Uskotaan, että ensimmäisen hakukoneen luoja oli Alan Emtage. Vuonna 1989 hän työskenteli McGill Universityssä Montrealissa, jonne hän muutti kotiseudultaan Barbadokselta. Yksi hänen tehtävistään yliopiston tietotekniikan osaston ylläpitäjänä oli löytää ohjelmia opiskelijoille ja opettajille. Helpottaakseen työtään ja säästääkseen aikaa Alan kirjoitti koodin, joka etsi hänet.

"Sen sijaan, että tuhlasin aikaani FTP-sivustoilla kiertelemiseen ja yrittäessäni selvittää, mitä niillä on, kirjoitin skriptejä, jotka tekivät sen puolestani", Alan sanoo, "ja tein sen nopeasti."

<поле>:<необязательный пробел><значение><необязательный пробел>
Ennätys<поле>voi olla kaksi arvoa: User-agent tai Disallow. User-agent määritti robotin nimen, jolle käytäntö kuvattiin, ja Disallow määritti osat, joihin pääsy evättiin.

Tällaisia tietoja sisältävä tiedosto esimerkiksi estää kaikilta roboteilta pääsyn URL-osoitteisiin, joissa on /cyberworld/map/ tai /tmp/ tai /foo.html:

# robots.txt for http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # Tämä on ääretön virtuaalinen URL-avaruus Disallow: /tmp/ # nämä katoavat pian Disallow: /foo. html
Tämä esimerkki estää pääsyn hakemistoon /cyberworld/map kaikille roboteille paitsi cybermapperille:

# robots.txt for http://www.example.com/ User-agent: * Disallow: /cyberworld/map/ # Tämä on ääretön virtuaalinen URL-avaruus # Cybermapper tietää minne mennä. User-agent: cybermapper Estä:
Tämä tiedosto "ottaa käyttöön" kaikki robotit, jotka yrittävät käyttää sivuston tietoja:

# mene pois User-agent: * Disallow: /

Kuolematon Archie

Lähes kolme vuosikymmentä sitten luotu Archie ei ole saanut päivityksiä koko tämän ajan. Ja se tarjosi täysin erilaisen Internet-kokemuksen. Mutta vielä nykyäänkin voit käyttää sitä löytääksesi tarvitsemasi tiedot. Yksi paikoista, jossa Archie-hakukone edelleen isännöi, on Varsovan yliopisto. Totta, suurin osa palvelun löytämistä tiedostoista on vuodelta 2001.

Huolimatta siitä, että Archie on hakukone, se tarjoaa silti useita ominaisuuksia hakusi mukauttamiseen. Tietokannan määrittämisen (anonyymi FTP tai puolalainen verkkohakemisto) lisäksi järjestelmä tarjoaa vaihtoehtoja syötetyn merkkijonon tulkitsemiseen: alimerkkijonona, sanatarkasti hakuna tai säännöllisenä lausekkeena. Sinulla on jopa vaihtoehtoja kirjainkoon valintaan ja kolme vaihtoehtoa tulosten näyttötavan muuttamiseen: avainsanat, kuvaus tai linkit.

On myös useita valinnaisia hakuparametreja, joiden avulla voit tunnistaa tarvitsemasi tiedostot tarkemmin. On mahdollista lisätä palvelusanoja OR ja AND, rajata tiedostojen hakualue tiettyyn polkuun tai verkkotunnukseen (.com, .edu, .org jne.) sekä asettaa palautettavien tulosten enimmäismäärä.

Vaikka Archie on hyvin vanha hakukone, se tarjoaa silti varsin tehokkaita toimintoja, kun etsit tarvitsemaasi tiedostoa. Nykyaikaisiin hakukoneisiin verrattuna se on kuitenkin erittäin alkeellista. "Hakukoneet" ovat menneet pitkälle - sinun tarvitsee vain alkaa syöttää haluttu kysely, ja järjestelmä tarjoaa jo hakuvaihtoehtoja. Puhumattakaan käytetyistä koneoppimisalgoritmeista.

Nykyään koneoppiminen on yksi hakukoneiden, kuten Googlen tai Yandexin, pääosista. Esimerkki tämän tekniikan käytöstä voisi olla hakusijoitus: kontekstuaalinen sijoitus, henkilökohtainen sijoitus jne. Tässä tapauksessa Learning to Rank (LTR) -järjestelmiä käytetään hyvin usein.

Koneoppiminen mahdollistaa myös käyttäjän syöttämien kyselyiden "ymmärtämisen". Sivusto korjaa itsenäisesti oikeinkirjoituksen, käsittelee synonyymejä, ratkaisee epäselvyyksiä (mitä käyttäjä halusi löytää, tietoa Eagles-ryhmästä tai kotkista). Hakukoneet oppivat itsenäisesti luokittelemaan sivustoja URL-osoitteen mukaan - blogi, uutisresurssi, foorumi jne. sekä käyttäjät itse luomaan henkilökohtaisen haun.

Hakukoneiden isoisoisoisä

Archie synnytti Googlen kaltaiset hakukoneet, joten jollain tapaa sitä voidaan pitää hakukoneiden isoisoisänä. Tämä oli melkein kolmekymmentä vuotta sitten. Nykyään hakukoneteollisuus ansaitsee noin 780 miljardia dollaria vuodessa.

Mitä tulee Alan Amtageen, kun häneltä kysytään menetetystä tilaisuudesta rikastua, hän vastaa jonkin verran vaatimattomalla tavalla. "Tietenkin haluaisin rikastua", hän sanoo. – En kuitenkaan ehkä tule miljardööriksi edes myönnetyillä patenteilla. Kuvauksiin on liian helppoa tehdä epätarkkuuksia. Joskus ei voita se, joka oli ensimmäinen, vaan se, josta tulee paras."

Google ja muut yritykset eivät olleet ensimmäisiä, mutta ne menestyivät kilpailijoitaan paremmin ja loivat usean miljardin dollarin teollisuuden.