Apache Lucene

Apache Lucene je biblioteka napisana u Java programskom jeziku koja omogućava pretragu visokih performansi velike količine podataka. Besplatna je i pogodna za skoro svaku aplikaciju kojoj je potrebna ovakva vrsta pretrage. Najpre ćemo objasniti odakle potreba za ovakvom bibliotekom kao i način na koji radi. Nakon toga ćemo videti kako se instalira i koristi.

Lucene indeksi

Vrlo često je potrebno pretražiti veliku količinu podataka. Primer može biti elektronska prodavnica kod koje kupci svakodnevno pretražuju veliki asortiman proizvoda po različitim kriterijumima i očekuju da se rezultati pretrage pojave u istom trenutku kao i da budu relevantni onome što je traženo. Relacione baze podataka uglavnom nisu pogodne za ovakve pretrage. To je zbog toga što su dizajn i arhitektura relacionih baza podataka takvi da one više služe za samo skladištenje podataka, dok su pretrage dosta sporije. Podaci se čuvaju u tabelama u normalnim formama, što znači da nema suvišnih podataka a prostor se čuva maksimalno. U slučajevima pretrage velike količine podataka podaci se često mogu naći u više različitih tabela zbog samog dizajna relacione baze, što dosta usporava dobijanje rezultata pretrage. Za ubrzanje pretrage podataka koriste se indeksi. To su dodatne strukture podataka koje sadrže jednu ili više kolona tabele i kod koje su podaci sortirani. Sortirane podatke možemo mnogo brže pretražiti pomoću struktura kao što je B stablo.

Indeksi koji se koriste u relacionim bazama podataka uglavnom koriste liste i stabla za pretragu. Lucene indeks se razlikuje po tome što koristi nizove.

Funckionisanje Lucene indeksa ćemo najbolje objasniti kroz primer. Neka su dati sledeći dokumenti:

Posmatraćemo reči: data, index, lucene, term, sql. Možemo da napravimo sledeću matricu pripadnosti datih reči dokumentima:

Svaka vrsta prestavlja jedan od gore pomenutih dokumenata, i popunjena je brojevima pojavljivanja svake od zadatih reči.

Ono što možemo primetiti jeste da imamo dosta polja popunjenih nulama. Ako zamislimo mnogo veći broj dokumenata, većina reči će se par puta pojaviti u vrlo malom broju dokumenata, dok će sama matrica uglavnom biti popunjena nulama. To se pokazuje Zipfovim zakonom koji govori o tome da se mali broj reči pojavljuje često. Informacija o tome da se neka reč ne nalazi u dokumentu nam čak nije ni potrebna, samo bespotrebno zauzima memoriju.

Zbog toga ćemo čuvati samo podatke koji nas interesuju. Imaćemo niz n-torki od kojih svaka sadrži reč i niz podataka koji prestavljaju ID dokumenta i broj pojavljivanja reči u tom dokumentu. Ukoliko neki dokument ne sadrži tu reč, nećemo imati podatak o pripadnosti tom dokumentu. Podaci o pripadnosti su sortirani po ID-u dokumenta. Matrica izgleda kao na slici:

U primeru sa slike, reč data se pojavljuje u prvom dokumentu jednom i u drugom dokumentu jednom, dok se reč sql pojavljuje samo u drugom dokumentu jednom.

Na ovaj način smo uštedeli memoriju. Ali, sada umesto jednog podatka o pripadnosti imamo dva (ID dokumenta i broj pojavljivanja). Međutim, to ne predstavlja problem jer se vrlo malo reči pojavljuje često. Dakle, dobili smo vrlo kompaktnu strukturu koja je i pogodna za pretragu (zbog činjenice da su podaci sortirani po ID-u dokumenta).

Struktura koju smo kreirali predstavlja Lucene indeks. Sada čemo videti kako se vrši pretraga pomoću tog indeksa.

U sledećem primeru vršićemo pretragu reči data, index i sql. Najpre ćemo učitati ceo indeks a potom izdvojiti vrste koje opisuju pripadnost reči koje pretražujemo.

Pokazivači su na početku postavljeni na podatak koji ima najmanji ID dokumenta svake vrste (podaci su sortirani po ID-u dokumenta). U prvom koraku tražimo koliko reči pripada dokumentu čiji je ID jednak 1. U našem primeru, to su dve reči, data i index, tj. rezultat prvog poklapanja će biti oblika [1, f(1 ,1, 0)] i to se naziva delimično poklapanje. Sada pokazivače pomeramo za jedno mesto, kako bismo izračunali rezultat poklapanja drugog dokumenta. Ukoliko je pokazivač već na podatku koji opisuje drugi dokument (kao kod reči sql), pokazivač ne pomeramo. Sada imamo potpuno poklapanje (sve tri reči se nalaze u dokumentu čiji je ID jednak 2), i ono je oblika [2, f(1, 1, 1)]. Postupak je prikazan na sledećoj slici.

Postupak koji smo primenili u prethodnom primeru se naziva linearno spajanje, koje je primenjeno nad 3 sortirana niza. Ovo je najbrži način da se dođe do željenih rezultata i upravo to koristi Lucene biblioteka prilikom pretrage. Dok se to izvodi primenjuje se Scoring funkcija. Na osnovu rezultata te funkcije odlučujemo šta prikazujemo od rezultata i u kom redosledu (u našem primeru u kom se dokumentu najviše pojavljuju zadate reči). To je funkcija koja kao argumente dobija ID dokumenta kao i broj pojavljivanja svake od reči i vraća ocenu poklapanja. Jedna prostija varijanta ove funkcije bi bila da se za svaku reč odredi da li pripada dokumentu (1 – pojavljuje se jednom ili više puta, 0 – ne pojavljuje se), i primeni operacija AND nad rezultatima za svaku reč.

\(f(Q,D) = \prod_{q \in Q}{1 : n_q > 0 \brace 0 : n_q = 0}\)

gde su:

• Q – skup reči
• D – skup dokumenata
• n_q – broj pojavljivanja reči q u dokumentu

Rezultat bi bio 0 ukoliko se bar jedna od reči ne pojavljuje u dokumentu, a 1 ako se sve reči pojavljuju u dokumentu bar jednom. Nešto komplikovanije ocenjivanje za koje ćemo dati samo formulu je:

\(f(Q,D) = \sum_{q \in Q}\frac{n_q}{n_q + \frac{k|D|}{avg|D|}} \cdot \log\frac{|C|}{df_q}\)

Više o funkcijama ocenjivanja možete pronaći na sledećem linku : Scoring.

Videli smo kako se indeks kreira i kako se vrši pretraga. Ostalo je da vidimo još šta se dešava sa indeksima kada se neki dokument doda ili obriše.

Koristeći Lucene terminologiju, indeksi se predstavljaju na sledeći način:

Segment je zapravo matrica koju smo prethodno opisali. Podaci o pripadnosti reči dokumentu su skraćeno napisani samo kao niz ID-ova dokumenata. Ono što je bitno jeste da segmenti ne mogu da se menjaju. To znači da kada dodajemo novi dokument, ne smemo da promenimo već postojeći segment nego dodajemo novi segment koji se tiče samo tog dokumenta čime se podaci dupliraju. Na taj način dobijamo veliki broj segmenata što dodatno troši memoriju. Zbog toga Lucene nakon dodavanja novog segmenta kreira segment koji nastaje spajanjem starog i novog segmenta. Na sledećoj slici možemo videti dodavanje novog segmenta kao i naknadno spajanje indeksa.

Ako posmatramo mnogo veći broj dokumenata i reči, spajanje bi se moglo predstaviti na sledeći način:

Dakle, kreiraju se pojedinačni segmenti za svaki dokument koji se potom spajaju u zajedničke segmente.

Ako obrišemo neki dokument, podatak o tom dokumentu unutar indeksa tj. referenca na taj dokument se ne briše u tom trenutku. U tabeli dokumenata se dodaje jedan bit čija je vrednost 1 ako dokument postoji a 0 ako je obrisan. Na osnovu tog bita se zna tokom pretrage da li treba uzimati dokument u razmatranje. Tek kada se ponovo izvrši spajanje segmenata, reference na dokument koji je obrisan se ignorišu i ne ubacuju u novi segment i to zapravo predstavlja brisanje. Dakle, sam dokument se briše odmah dok reference ostaju dok ne dođe do dodavanja novih segmenata.

Sada kada smo se upoznali sa funkcionisanjem Lucene indeksa možemo preći na njihovo korišćenje u konkretnim primerima.

Instalacija

Za upotrebu biblioteke Lucene potrebno je imati instaliranu Javu i to verziju 8. Osim Jave, za potrebe pokretanja primera koji će biti dat u nastavku, potrebno je instalirati Eclipse IDE.

Java

Instalaciju za Javu možete preuzeti ovde.

Eclipse

Za potrebe demonstracije primera koji će biti dati u nastavku, potrebno je instalirati Eclipse IDE. Instalaciju možete preuzeti na sledećem linku: Ecplipse download.

Lucene

Zip arhiva Lucene biblioteke se može preuzeti na sledećem linku: Lucene 6.6.0 Ukoliko imate problema sa preuzimanjem, posetite stranu Apache Lucene Download gde se nalazi nekoliko dodatnih linkova za preuzimanje zip arhive.

Kada se preuzimanje završi, raspakujte arhivu na željenu lokaciju.

Priprema okruženja

Prvo ćemo pokrenuti Eclipse IDE i kreirati novi Java projekat.

Sada je potrebno uključiti Lucene biblioteku. Desnim klikom na kreirani projekat i odabirom stavke Properties otvara se sledeći prozor:

Klikom na Build path stavku levog menija, dobijamo prozor u kome možemo da dodajemo eksterne biblioteke u projekat.

Nakon toga, klikom na dugme Add External JARs… otvara se prozor u kome treba pronaći Lucene 6.6.0 direktorijum, gde se na sledećim putanjama nalaze JAR fajlovi koje treba uključiti:

• analysis/common/lucene-analyzers-common-6.6.0.jar
• core/lucene-core-6.6.0.jar
• demo/lucene-demo-6.6.0.jar
• queryparser/lucene-queryparser-6.6.0.jar

Nakon dodavanja svig JAR fajlova, izgled prozora je sledeći:

Klikom na dugme OK je završeno uključivanje Lucene biblioteke u projekat.

Primer

Zadatak će biti da napravimo indeks za pretragu fajlova. Za zadatu reč treba da dobijemo spisak fajlova u kojima se ta reč pojavljuje sortiranih po broju pojavljivanja.

Najpre ćemo pokazati kako se kreira Lucene indeks nad nekim podacima, a potom i kako se vrši pretraga.

Kreiranje indeksa

Kreiraćemo klasu IndexFiles.java u projektu LuceneDemo koji smo prethodno napravili i u njoj ćemo kreirati indekse za pretragu dokumenata. Ideja je da prođemo kroz sve fajlove i kreiramo indekse. Ulaz u ovaj program jeste putanja do fajlova koje želimo da indeksiramo kao i putanja do direktorijuma gde ćemo čuvati indekse.

Za kreiranje indeksa koristi se objekat klase IndexWriter. Za kreiranje objekta, konstruktoru se prosleđuju direktorijum gde se čuvaju indeksi i objekat klase IndexWriterConfig (konfiguracija za kreiranje indeksa). Konstruktoru konfiguracije prosleđujemo objekat klase Analyzer i metodom setOpenMode(OpenMode openMode) postavljamo da li želimo da kreiramo novi indeks ili da izmenimo stari. Objekat Analyzer klase služi da vrši analizu teksta koji ćemo kasnije pretraživati (koristiće se i prilikom pretrage). U nastavku je dat kod koji kreira IndexWriter objekat i poziva funkciju u kojoj ćemo kreirati indekse.

boolean create = true; //false for update String indexPath = "index"; String docsPath = "test data"; Directory dir = FSDirectory.open(Paths.get(indexPath)); Analyzer analyzer = new StandardAnalyzer(); IndexWriterConfig iwc = new IndexWriterConfig(analyzer); if (create) { iwc.setOpenMode(OpenMode.CREATE); } else { iwc.setOpenMode(OpenMode.CREATE_OR_APPEND); } IndexWriter writer = new IndexWriter(dir, iwc); indexDocs(writer, docDir); writer.close(); 

Funckija void indexDocs(IndexWriter writer, Path path) ima zadatak da prođe kroz sve fajlove koje indeksiramo (path je putanja do direktorijuma gde su smešteni) i za svaki fajl pozove funckiju za indeksiranje koju ćemo kasnije objasniti.

static void indexDocs(final IndexWriter writer, Path path) throws IOException { if (Files.isDirectory(path)) { Files.walkFileTree(path, new SimpleFileVisitor() { @Override public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException { try { indexDoc(writer, file, attrs.lastModifiedTime().toMillis()); } catch (IOException ignore) { // don't index files that can't be read. } return FileVisitResult.CONTINUE; } }); } else { indexDoc(writer, path, Files.getLastModifiedTime(path).toMillis()); } } 

Sada dolazimo do kreiranja samog indeksa. Fajlovi iz primera su zapravo dokumenti o kojima smo već pričali. Svaki dokument može imati više polja pretrage. U našem primeru to će biti putanja do fajla, vreme poslednje izmene fajla i sadržaj fajla. Dakle, kreiraćemo objekat klase Document i u njega dodati polja pretrage što su objekti klase Field. O tome koji sve tipovi polja postoje pričaćemo malo kasnije. Nakon što dodamo željena polja, pomoću objekta klase IndexWriter dodajemo dokument metodom addDocument(Document doc) ili ga menjamo metodom updateDocument(Term term, Document doc). Kod izmene dokumenta, argument term služi za idenktifikaciju dokumenta, kako bi se on obrisao ako postoji. U nastavku je data funkcija koja kreira indeks.

static void indexDoc(IndexWriter writer, Path file, long lastModified) throws IOException { try (InputStream stream = Files.newInputStream(file)) { Document doc = new Document(); Field pathField = new StringField("path", file.toString(), Field.Store.YES); doc.add(pathField); doc.add(new LongPoint("modified", lastModified)); doc.add(new TextField("contents", new BufferedReader(new InputStreamReader(stream, StandardCharsets.UTF_8)))); if (writer.getConfig().getOpenMode() == OpenMode.CREATE) { System.out.println("adding " + file); writer.addDocument(doc); } else { System.out.println("updating " + file); writer.updateDocument(new Term("path", file.toString()), doc); } } } 

Ostalo je nešto da kažemo o klasi Field. Ona ima podklase kao što su: TextField, StringField, LongPoint, IntPoint, FloatPoint,… Koju ćemo odabrati zavisi od toga šta pretražujemo. LongPoint smo iskoristili kod datuma, jer ga predstavljamo u obliku milisekundi što zahteva tip podatka long. Polje ovog tipa omogućava brze pretrage vezane za opseg. StringField i TextField se koriste za pretragu teksta s tim što TextField tekst deli na reči dok StringField sve posmatra kao jednu reč.

Pretraga

Sada ćemo pokazati kako se vrši pretraga pomoću Lucene indeksa.

Prvo je potrebno pročitati indeks. Za čitanje indeksa koristi se objekat klase IndexReader. Čita iz direktorijuma u kome smo sačuvali indekse. Nakon toga, potrebno je kreirati objekat klase IndexSearcher kome se u konstruktoru prosleđuje objekat klase IndexReader koji je prethodno napravljen. Pored toga, treba kreirati i objekat klase Analyzer, koji se koristi za pretragu teksta u indeksu.

Sada kada smo pristupili indeksu, potrebno je da kreiramo upit. Postoje sledeće opcije za pisanje upita:

• test – pretražuje reč test u dokumentu
• test tekst – moguća je pretraga više reči
• te?t – ? zamenjuje tačno jedan karakter (ne sme da se pojavi kao prvi karakter)
• te*t – * zamenjuje 0 ili više karaktera (ne sme da se pojavi kao prvi karakter)
• test~2 – fuzzy pretraga pretražuje reči slične reči test (2 je stepen sličnosti)
• test tekst~10 – broj reči između reči test i tekst ne sme biti veći od 10
• [1-10] – broj koji se traži mora biti u zadatom opsegu kome pripadaju i granične vrednosti 1 i 10 (na isti način se pretračuje i tekst)
• {1-10} – broj koji se traži mora biti u zadatom opsegu kome ne pripadaju granične vrednosti 1 i 10 (na isti način se pretračuje i tekst)
• test^10 tekst – ocena pretrage reči test se množi brojem 10 što utiče na prikaz i redosled rezultata pretrage
• test OR tekst – logički operatori; dokument treba da sadrži bar jednu od ove dve reči. Osim OR postoje i AND, NOT kao i kombinovanje operatora pomoću zagrada.

Lucene podržava i specijalne karaktere: + – && || ! ( ) { } [ ] ^ “ ~ * ? : \ ispred kojih se mora napisati karakter \ .

String koji smo napisali parsiramo u upit (objekat klase Query) pomoću objekta klase QueryParser kome se prosleđuje polje nad kojim se vrši upit i analizator. Deo koda koji kreira ove objekte dat je u nastavku.

String index = "index"; String field = "contents"; String queries = null; int repeat = 0; String queryString = "computer^10 crime"; int hitsPerPage = 10; IndexReader reader = DirectoryReader.open(FSDirectory.open(Paths.get(index))); IndexSearcher searcher = new IndexSearcher(reader); Analyzer analyzer = new StandardAnalyzer(); BufferedReader in = null; QueryParser parser = new QueryParser(field, analyzer); Query query = parser.parse(queryString); System.out.println("Searching for: " + query.toString(field)); doPagingSearch(in, searcher, query, hitsPerPage); reader.close(); 

Funkcija void doPagingSearch(BufferedReader in, IndexSearcher searcher, Query query, int hitsPerPage) izvršava upit i ispisuje koji fajlovi su rezultat upita. Upit se izvršava pozivanjem funckije search(Query query, int hits) objekta klase IndexSearcher kojoj se prosleđuje upit i maksimalan broj dokumenata koje želimo kao rezultat. Funkcija vraća objekat klase TopDocs koji sadrži listu izlaznih dokumenata. Informacije o jednom rezultujućem dokumentu se dobijaju na sledeći način:

Document doc = searcher.doc(hits[i].doc); String path = doc.get("path"); 

Kod cele funkcije je dat u nastavku.

public static void doPagingSearch(BufferedReader in, IndexSearcher searcher, Query query, int hitsPerPage) throws IOException { TopDocs results = searcher.search(query, hitsPerPage); ScoreDoc[] hits = results.scoreDocs; int numTotalHits = results.totalHits; System.out.println(numTotalHits + " total matching documents"); int start = 0; int end = Math.min(numTotalHits, hitsPerPage); if (end > hits.length) { System.out.println("Only results 1 - " + hits.length +" of " + numTotalHits + " total matching documents collected."); } for (int i = start; i < end; i++) { Document doc = searcher.doc(hits[i].doc); String path = doc.get("path"); if (path != null) { System.out.println((i+1) + ". " + path); String title = doc.get("title"); if (title != null) { System.out.println("   Title: " + doc.get("title")); } } else { System.out.println((i+1) + ". " + "No path for this document"); } } 

Kompletan primer sa fajlovima koje smo pretraživali možete preuzeti ovde: LuceneDemo.

U ovom članku smo videli šta je Lucene, kako radi i kako se može upotrebiti. U praksi je već ugrađen u veliki broj alata. Spisak tih alata možete videti na sledećem linku: https://wiki.apache.org/lucene-java/PoweredBy. U narednom članku (link) ćemo istražiti alat za pretragu Elasticsearch koji je baziran na Lucene tehnologiji.

Literatura

• Lucene and its magical indexes, https://www.linkedin.com/pulse/lucene-its-magical-indexes-sanjay-singh
• Lucene Apache, https://lucene.apache.org/
• Lucene Demo, https://lucene.apache.org/core/6_6_0/demo/overview-summary.html#overview_description
• Lucene Query Parser, https://lucene.apache.org/core/2_9_4/queryparsersyntax.html