Superhurtig søgning med Lucene

Lucene er en Java-baseret maskine til indeksering og søgning i tekst. Selv på et gammelt hakkebræt af en computer klarer Lucene uden problemer fritekstsøgning gennem 500 megabyte data med øjeblikkelige svar, som oven i købet er rangordnede. Vidunderet har mange anvendelsesmuligheder, og i to artikler bygger vi en offline-version af den åbne encyklopædi, Wikipedia, med basis i Lucene.

Wikipedia

Fritekstsøgning er nødvendigt, når man arbejder med store mængder af tekst. De fleste større websites tilbyder brugerne bedre eller dårlige søgefaciliteter, som kan finde nålen i den høstak, som stadigt voksende websites udgør. Gode søgemaskiner kan endog rangere resultaterne på forespørgslerne, således at de mest relevante forhåbentlig kommer først.

Problemet
Behovet for fritekstsøgning ses også af, at webbets mest besøgte site - Google - netop er en fritekst-søgemaskine, og endda en temmelig avanceret én af slagsen.

Der er ikke kun websites, som kan have behov for søgemaskiner. Der kan også være behov for søgemaskiner andre steder, hvor tekstmængderne hober sig op. Det kan være dokumenter samlet på et fællesdrev eller i forbindelse med løsninger til dokumenthåndtering.

Løsningen
I forbindelse med fritekstsøgning tænker man ofte på relationsdatabaser og SQL-operatoren LIKE, som benyttes i den sammenhæng. Det kan for eksempel se sådan ud:

SELECT ID FROM ARTIKLER WHERE ARTIKEL_TEKST LIKE '%sommer%';

Denne SQL-sætning vælger samtlige ID-numre fra en tabel, ARTIKLER, hvor feltet ARTIKEL_TEKST indeholder tekst-strengen "sommer". Procent-tegnene har samme mening som asterisk (*) i andre tekst-søgesystemer.

Hvis blot tabellen er tilstrækkelig lille, eller databasemaskinen er hurtig nok, så fungerer denne måde at implementere søgning på helt udmærket.

Men hvis antallet af rækker bliver meget stort, kan det give problemer. Så må man prøve med en egentlig tekst-søgningsmaskine.

Den slags problemer kan godt virke lidt akademiske, så lad os kigge på et konkret eksempel, hvor databasen kommer til kort.

Wikipedia
Encyklopædi-projektet Wikipedia går ud på at skrive en webbaseret encyklopædi - et leksikon - baseret helt på frivilligt arbejde. Alle kan skrive, og alle kan redigere i artiklerne i encyklopædien.

Det kan lyde som noget pjat, men Wikipedia indeholder faktisk mange udmærkede opslag - sammen med adskillige, som er knap så udmærkede. Wikipedia har netop rundet 100.000 artikler ifølge projektets bagmænd, og som man kan forestille sig, bliver det til et temmelig stort leksikon.

Teksterne i Wikipedia udgives under en slags open source-pendant for artikler, og derfor kan alle snuppe sig en kopi af den bagvedliggende database.

Indlejrede databaser

Offline
Hvis man stadig - som denne artikels forfatter - er koblet til nettet via et godt, gammeldags 56k-modem, så er der ikke så meget sjov ved en web-baseret encyklopædi. Da encyklopædiens indhold gerne må kopieres, melder ideen sig om at kreere en offline-version af encyklopædien. Så svært kan det vel heller ikke være, da det blot handler om at kunne søge i en stor tekstmængde.

Den tilgængelige kopi af Wikipedia, er en komprimeret version af et SQL-script til databasen MySQL, og den komprimerede version, som kan hentes fra Wikipedia website, fylder knap 100 megabyte. Udpakket fylder filen omkring 500 megabyte. Det er blot er en tekstfil, som indeholder en masse SQL INSERT-sætninger.

Ideen i vort lille projekt er altså at kunne søge disse data igennem på en helt almindelig skrivebordscomputer, og i særdeleshed på forfatterens halvgamle 1.0 GHz-hakkebræt. Det hele skal være gratis, så de værktøjer vi vælger at benytte, skal være open source eller freeware-baseret.

Til at starte med forsøgte vi at loade dataene ind i en række forskellige databaser. Vi valgte Java som platform, for det er forholdsvist nemt at have med at gøre, og Java er nogenlunde platformsuafhængigt, hvilket er helt i Wikipedias ånd - tror vi nok.

Indlejrede Java-databaser
Vi kiggede på en række open source Java-databaser, og der findes en del udmærkede af slagsen til indlejrede anvendelser, hvor databasen ikke fungerer som en server, men lever inde i et andet program.

Databasen Mckoi gav os i særdeleshed gode resultater. Mckoi er open source, ren Java, og indeholder et ganske pænt udsnit af de almindelige SQL- og JDBC-funktioner.

Det tog omkring fem timer at loade de 500 megabyte data ind i en tabel i Mckoi, og ved ikke-fritekstsøgninger fik vi efterfølgende svartider, som var helt acceptable.

Men da vi prøvede med en søgning i stil med det tidligere viste SQL-eksempel, kom Mckoi til kort. Det tog databasen omkring et minut at søge igennem de 500 megabyte, som dog var reduceret til 200 megabyte i Mckois database-format.

Et minut er uacceptabelt i forbindelse med interaktive søgninger, hvor der sidder en levende bruger bag skærmen og venter på resultaterne. Vi prøvede så med en ikke-Java løsning for at se, om en database født til computeren kunne klare opgaven bedre.

Lucene siger: Bingo!

Tilbage til MySQL
Her valgte vi naturligt nok MySQL, for den er udover at være hurtig også temmelig portabel. Ydermere er det den samme database, som vores Wikipedia-dump var genereret fra, så det var nemt at putte data ind i MySQL igen. Som en sidste og vigtigt tilgift indeholder MySQL specielle kommandoer, som optimerer kolonner til fritekst-søgning.

Men på vores ældre computer kom MySQL også til kort. Svartiderne var bedre en Mckois, men stadig for høje til at være anvendelige - omkring 30 til 40 sekunder, og det var vel af mærke med indeksering og fritekst-optimering af kolonnerne.

Indeksering med Lucene
Der måtte altså andre midler til for at løse vores problem. Efter eftertænksom grublen i flere minutter, kom vi i tanke om tekst-søgemaskinen Lucene, som er skrevet i Java, er open source og har et helt fantastisk ry.

Lucene er altså ikke en database. Den holder ikke på data, men indekserer kun tekster, som må gemme sig andre steder. Det kan oplagt være i en database, men det kan også blot være flade filer på et drev.

Lucene danner en række filer til indeksering, og de kan også gemmes på harddisken, men man kan også nemt implementere en løsning, hvor disse indekser gemmes et andet sted, eksempelvis i en database.

Bingo!
I modsætning til vores databaser, som brugte omkring fem timer på at tygge vores encyklopædi igennem, tog det blot Lucene 20 minutter at kværne de 500 megabyte. Det er ikke blot belejligt med den kortere processeringstid, det er også en vigtig faktor i udviklingsfasen. Artiklerne gemte vi blot som flade tekstfiler.

Dødsensspændte udførte vi vores allerførste fritekstsøgning i Lucene - og ikke et øje forblev tørt. Svarene kom prompte, helt øjeblikkeligt.

Lucene er nem at anvende, og indeholder masser af smarte søgemuligheder og faciliteter. I den næste artikel går vi tættere på det effektive bæst, og ser på, hvordan den anvendes og implementeres i praksis med udgangspunkt i vores offline-version af Wikipedia.




Brancheguiden
Brancheguide logo
Opdateres dagligt:
Den største og
mest komplette
oversigt
over danske
it-virksomheder
Hvad kan de? Hvor store er de? Hvor bor de?
Ed A/S
Salg af hard- og software.

Nøgletal og mere info om virksomheden
Skal din virksomhed med i Guiden? Klik her

Kommende events
Compliance og strategisk it-sikkerhed efter DORA

Finansielle koncerner har i snit 85 sikkerhedsløsninger i drift – men er i snit op til 100 dage om at opdage et igangværende cyberangreb. Ydermere viser øvelser, at det typisk tager 4-6 uger at rense og genetablere sikker drift af centrale systemer efter et stort angreb. Fokus for dagen vil derfor være på henholdsvis governance samt om, hvordan du som it-leder i den finansielle sektor skal kunne håndtere fremtidens cybertrusler og arbejde effektivt med sikkerhed på et strategisk niveau.

04. april 2024 | Læs mere


EA Excellence Day

Hvad er det, der gør it-arkitektens rolle så vigtig? Og hvad er det for udfordringer inden for områder som cloud, netværk og datacentre, som fylder hos nogle af landets bedste it-arkitekter lige nu? Det kan du her høre mere om og blive inspireret af på denne konference, hvor du også får lejlighed til at drøfte dette med ligesindede.

16. april 2024 | Læs mere


IAM - din genvej til højere sikkerhed uden uautoriseret adgang og datatab

På denne dag udforsker vi de nyeste strategier, værktøjer og bedste praksis inden for IAM, med det formål at styrke virksomheders sikkerhedsposition og effektiviteten af deres adgangsstyringssystemer og dermed minimere risikoen for uautoriseret adgang og datatab. Og hvordan man kommer fra at overbevise ledelsen til rent faktisk at implementere IAM?

18. april 2024 | Læs mere