Kvalitetssøk på norsk med æøå

Søk har de siste årene blitt en viktig del av alles internetthverdag. For mange er «å søke» synonymt med «å google», men dersom du vil presentere innholdet ditt på en egen måte eller prioritere sidene annerledes må du implementere et eget søk.

Det finnes mange gode løsninger for å implementere eget søk som er gratis og har åpen kildekode. Disse er ofte basert på Apache Lucene og er enkle å sette opp, men det krever endel jobb å få virkelig gode resultater. Google har brukt mye ressurser på å indeksere hele internettets innhold og prøver å presentere de sidene du er ute etter, ikke bare sider som inneholder det ordet du brukte til å søke.

Google gjør grundige analyser av teksten på nettsidene, denne typen analyse er ikke implementert i de løsningene som er gratis og åpen kildekode. Derfor er de løsningene vi kan implementere selv ved hjelp av Lucene ganske primitive sammenlignet med Google. Dette gjør at vi sannsynligvis ikke klarer å gi like relevante søkeresultater som det vi ville fått om det samme søket hadde blitt utført i Google.

Men fortvil ikke, jeg har jobbet mye med søk i forbindelse med Kantegas eget publiseringssystem, OpenAksess, og skal fortelle deg hvordan et søk fungerer, hva en indeks er, og noen eksempler på hvorfor det er vanskelig å implementere et godt søk. De konkrete eksemplene jeg gir er med utgangspunkt i Solr, som er basert på Lucene.

Kevin Bacon?

Når du gjør et søk er det som regel sider med en bestemt mening du er ute etter. Selv om en side inneholder et av søkeordene betyr ikke det at du har nytte av siden. For eksempel er det ikke trivielt å vite hva du egentlig er ute etter når du bruker søkeordet «bacon», det kan være Francis Bacon, Kevin Bacon, oppskrifter med bacon, eller Wikipediasiden om bacon du er ute etter. Det er slike problemstillinger Google har brukt mye ressurser på å finne løsninger på, ved å utføre grundig språkanalyse og semantisk analyse av de sidene som blir indeksert.Baconsearch

Innmaten i en søkemotor

Det som skjer når et søk blir utført er at søkeordene brukeren har gitt blir sammenlignet med en indeks. Dette er sannsyneligvis en «invertert indeks», altså hvilke dokumenter inneholder hvilke ord. Dersom vi har følgende dokumenter:

D1 Det er barn i barnehagene
D2 Skoler trenger oppussing, det gjør ikke barnehager

blir indeksen slik:

barn D1
barnehagene D1
barnehager D2
det D1, D2
er D1
gjør D2
i D1
ikke D2
oppussing D2
skoler D2
trenger D2

Resultatene av et søk er vanligvis sortert etter relevansen til hvert dokument. Relevans blir avgjort av en algoritme, vanligvis TF-IDF, som beregner en verdi for hvor viktig hvert søkeord er i hvert av dokumentene. Som regel blir det gjort preprossessering av dokumentene før de blir indeksert, som regel konvertering til små bokstaver, stoppord-fjerning og «stemming».

Stoppord er ord som forekommer veldig ofte i de fleste tekster, f.eks. i, er, det. Siden disse ordene forekommer så ofte, som regel i alle dokumentene, gir det ikke noen verdi i å ha dem i indeksen. Stemming er prosessen med å redusere hvert ord til roten sin, både barnehagene og barnehager blir gjort om til barnehag. Dette blir gjort både for hvert ord i dokumentene, og for hvert søkeord som blir gitt av brukeren. Når vi har utført stoppordfjerning og stemming blir indeksen vår seende slik ut:

barn D1
barnehag D1, D2
gjør D2
ikk D2
oppuss D2
skol D2
treng D2

Ved å gjøre dette vil begge dokumentene være med i resultatet når søkeordet er både barnehage, barnehager og barnehagene.

Å være, været, en vær

Det finnes stemming-algoritmer for de fleste språk som fungerer godt, men naiv stemming har to problemer. Det første problemet er at ord som har forskjellig mening blir stemmet til det samme. Et eksempel på dette er været, en vær, (fiske)vær, og (å) være. I vanlig setninger kan «været» bøyes til «vær», men det skal mye til for at meningen kan forveksles med en hann-sau. Når det blir gjort et søk vil det samme dokumentet dukke opp uansett om du søker om været, «å være» eller en vær, siden stemming vil gjøre at det er «vær» som er indeksert. Et annet eksempel er at (en) slange og (å gå på) slang begge vil stemmes til «slang».Værsøk

Det andre problemet er der bøyning gjør at stemming gir et helt annet ord. Eksempler på dette er , gikk og finne, fant. Dette er et problem som oppstår i de fleste språk, og en løsning vil kunne være å bruke «lemmatisering» i stedet for stemming. Da vil lemmaet til hvert ord bli indeksert, noe som krever at man klarer å finne ut hvilken betydning hvert ord har ut fra den konteksten det står i.

På denne måten vet vi mer om innholdet i et dokument, men vi har ennå problemet med å finne ut hvilken side du egentlig er ute etter når du søker etter «bacon». Et annet problem, som er relatert til dette, er når noe har flere stavemåter, eller som ofte blir stavet feil. Et eksempel på dette er navnet Kristoffer, Christoffer. I slike tilfeller kan det være en fordel å indeksere en fonetisk versjon av navnet, slik at det er uttalen som blir indeksert. Men dette gir mest mening når det er snakk om navn.

Bruk av synonymordlister

En måte å omgå disse problemene til en viss grad er å bruke synonymordlister til å indeksere alternative former av ordet sammen med det opprinnelige ordet. Jeg har ikke funnet noen god synonymordliste for norsk, men har funnet noen ressurser på Nasjonalbibliotekets nettsider, og stavekontrollen Open/Libre Office som jeg tror kan brukes etter litt prosessering.

I tillegg til å indeksere synonymer sammen med de opprinnelige ordene kan man øke sannsynligheten for at et relevant dokument blir med i søkeresultatet ved å legge til relaterte ord som ønskes skal gi treff i indeksen. Ved å følge med på hva brukerne søker etter kan man da kompensere for at den semantiske koblingen som finnes mellom ord ikke blir tatt hensyn til ved indeksering.

Flere felter, mer søl?

De fleste dokumentene som indekseres har flere felter. Et typisk eksempel er en artikkel, med tittel, ingress, og brødtekst. Når en bruker utfører et søk ønsker vi som regel å søke i alle disse feltene og vekte treff i de ulike feltene forskjellig, slik at treff i tittelen teller mer enn treff i de andre feltene.

En vanlig fremgangsmåte for å oppnå dette er å bruke en «Dismax»-spørring, disjunction max. Denne søker i alle feltene som er oppgitt, og dersom det er treff i flere felter får selve dokumentet scoren til det feltet som har høyest score. Dette fungerer ofte bra, men det er ikke sikkert det gir den rekkefølgen på søkeresultatene du er ute etter.

Årsaken ligger i det jeg akkurat har nevnt, at det er at det er feltet med høyest score som «vinner». Siden innholdet i de forskjellige feltene ofte har forskjellig skrivestil og lengde er det ikke sikkert at det faktum at tittelen har fått høyere score enn ingressen er så relevant. Dismax gir en score for hvert felt separat, og scoren for et felt i et dokument er avhengig av hvor ofte søkeordet opptrer i dette feltet og hvor mange ganger søkeordet forekommer i dette feltet i alle dokumenter.

Dersom et ord forekommer mange ganger totalt vil treff i et konkret felt resultere i en lavere score enn dersom ordet er sjeldent. Siden tittel, ingress, og brødtekst ofte har forskjellig skrivestil og lengde er det ikke sikkert at det feltet som får høyest score er det som mest nøyaktig sier om hele dokumentet er relevant. Det er flere måter å forbedre denne situasjonen.

Tie breaker

En av dem er å følge med på hvilke score de forskjellige feltene ofte ligger i, og justere ved å legge til «tie breaker». For eksempel

score = max(scores) + tie * sum(otherscores)

der «tie» er et tall mellom 0.0 og 1.0.

Det er ingenting som hjelper deg med å finne ut hva denne skal være, så du må selv finne frem til hva som er en god verdi, og evt. endre den etter hvert som dokumentene du legger til i indeksen gjør at score endrer seg. 

Samlefelt

En bedre måte er å ha ett stort felt i tillegg til de opprinnelige feltene, og kopiere alle feltene inn i samlefeltet. Ved å da søke i samlefeltet slipper man at treff i ett felt overskygger de andre, og ved å bruke «boost queries» og «boost functions»  mot de feltene man mener burde vektes ekstra oppnår man muligens ønsket resultat. Med denne teknikken er det lett å legge til at nyere innhold skal vektes høyere enn gammelt, at noen sidetyper skal vektes høyere enn andre eller at helt andre ting skal påvirke vektingen.

æøå

ISOAsUTF8

Tekst kodet i Latin-1, men blir lest som om den er UTF-8

UTF8AsISO

Dersom teksten er kodet i UTF-8 og blir lest som Latin-1 blir dette resultatet

Dette er tegn du sikkert har opplevd å se, og er ikke uvanlig når man ikke er bevisst på hvordan teksten vi har lagres og leses.

I en datamaskin er alt i bunnen en serie av null og en. Det betyr at all tekst som blir vist på skjermen din, overført over internett og lagret på disken din er kun nuller og enere. Dette betyr at hver bokstav må kodes som en serie av null og en. Det finnes veldig mange tegnsett for dette, og det er viktig at en tekst blir lest med det tegnsettet den er skrevet med, ellers kan noen av tegnene bli mistolket.

De to tegnsettene som er mest vanlig i vår del av internettet er ISO-8859-1(Latin-1) og UTF-8. De 127 første tegnene(a-Z,0-9, med flere) er kodet likt i de fleste tegnsett, mens det varierer hvordan bokstaver utenfor det engelske alfabetet kodes.

Det er ingen måte å vite med hvilket tegnsett en tekst er laget bortsett fra å bli fortalt det og å prøve å tolke den, og se om den ser riktig ut.

Når man jobber med norske tekster er det vanligvis bokstavene æ,ø, og å som skaper problemer når teksten leses inn med feil tegnsett. 

Dette har ikke noe direkte å gjøre med søk, men er problemer man lett kommer bort i når man jobber med tekster som bruker andre tegn enn bare vanlige bokstaver og tall.

Det skal ikke mye til for å unngå dette problemet. Det er beste er å kun bruke koding basert på unicode, feks UTF-8, og være bevisst på hvilen koding de eksterne kildene du har bruker. For en fin gjennomgang av dette se «The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)»

Konklusjon

Google har skapt forventninger om at alt skal være mulig å finne med å søke. Med verktøy som Solr og Lucene er det lett å sette opp noe som lar deg søke i det innholdet du har, men det er en stor utfordring å få til virkelig gode resultater.

Jeg har forsøkt å demonstrere hvordan en søkemotor fungerer, og prøvd å illustrere noen av utfordringene man møter i forbindelse med implementering av søk og behandling av tekst generelt.

Dette innlegget er basert på en lyntale jeg holdt på Javazone 2013.

Litt om forfatteren

Marvin

Marvin Bredal Lillehaug

Marvin Bredal Lillehaug er systemutvikler i Kantega og er opptatt av at kode skal være lettleselig og vedlikeholdbart.
Han har en master i intelligente systemer fra NTNU, med fordypning i forklaringsbeviste Case-based reasoning-systemer.
comments powered by Disqus