Geokodiranje (angl. geocoding, address lookup) je storitev, ki poišče geografske kraje, ki ustrezajo podanemu iskalnemu nizu. Geografski kraji so predstavljeni s prostorsko lokacijo v geografskih koordinatah (zemljepisna dolžina in širina v stopinjah). Geokodiranje pride prav uporabnikom, ki želijo izvedeti, kje se nahaja nek geografski kraj (npr. naslov, cesta, zgradba ipd.), pri tem pa vedo samo (celo ali delno) ime kraja. V ustrezno opremljenem odjemalcu vnesejo iskalni niz, orodje jim poišče ustrezne zadetke, grafični odjemalec pa jih prikaže na zemljevidu.

Ustrezna koda se nahaja v javinem paketu net.tinelstudio.gis.geocoding.

7.1 Iskalci

Storitev geokodiranja je zasnovana tako, da odjemalec strežniku poda zahtevo v obliki iskalca (angl. locator). Iskalcev je več vrst in opravljajo različne vloge. Tako lahko uporabnik natančno definira, po kateri vrsti podatkov se naj išče.

Iskalec v bistvu obstaja v dveh oblikah. Tisti na strežniški strani (LocatorService) dejansko išče zadetke, tistega na odjemalčevi strani (Locator) pa uporabnik uporablja za nastavljanje iskanja. Ko uporabnik izbere iskalca, mu mora podati še:

• searchString - iskalni niz (geoime) in
• maxResults - največje število zadetkov.

Iskalni niz je lahko cel (predstavlja celotno geoime, npr. "Cankarjeva ulica") ali le delen (npr. "cank ul.").

Storitev pozna štiri vrste iskalcev:

1. Osnovni iskalec, ki išče samo po glavnem imenu neke vrste podatka (npr. samo po imenu naslova, ceste ali zgradbe).
   • AddressLocator - Išče hkrati po naslovih (geoimena vrste ADDRESS) in po hišnih številkah. Če v iskalnem nizu ni nobene hišne številke, se iskanje sploh ne prične. To pride prav v kombinaciji z multi iskalci.
   • StreetLocator - Išče po imenih cest (geoimena vrste STREET).
   • BuildingLocator - Išče po imenih zgradb (geoimena vrste BUILDING).
2. Osnovni iskalec, ki išče po drugih imenih neke vrste podatka (npr. samo po imenu mesta ali države nekega naslova, ceste ali zgradbe).
   Zanimivo pri tej vrsti iskalca je, da vrne samo en zadetek na iskalno ime. Če je iskalni niz "Ljubljana", bo, npr., DistinctAddressByTownLocator vrnil samo prvi naslov v Ljubljani in ne vseh nekaj tisoč. To je uporabno takrat, kadar nas zanima samo, kje je določeno mesto (bolj na grobo), in ne podrobnosti mesta.
   • DistinctAddressByNameLocator - Išče samo po naslovih brez hišnih številk (geoimena vrste ADDRESS) in vrne samo en naslov na ime naslova.
   • DistinctAddressByTownLocator - Išče samo po imenih mest (geoimena vrste TOWN) in vrne samo en naslov na mesto.
   • DistinctAddressByRegionLocator - Išče samo po imenih regij (geoimena vrste REGION) in vrne samo en naslov na regijo.
   • DistinctAddressByCountryLocator - Išče samo po imenih držav (geoimena vrste COUNTRY) in vrne samo en naslov na državo.
   • DistinctAddressByContinentLocator - Išče samo po imenih kontinentov (geoimena vrste CONTINENT) in vrne samo en naslov na kontinent.
   • DistinctStreetByTownLocator - Išče samo po imenih mest (geoimena vrste TOWN) in vrne samo eno cesto na mesto.
   • DistinctStreetByRegionLocator - Išče samo po imenih regij (geoimena vrste REGION) in vrne samo eno cesto na regijo.
   • DistinctStreetByCountryLocator - Išče samo po imenih držav (geoimena vrste COUNTRY) in vrne samo eno cesto na državo.
   • DistinctStreetByContinentLocator - Išče samo po imenih kontinentov (geoimena vrste CONTINENT) in vrne samo eno cesto na kontinent.
   • DistinctBuildingByTownLocator - Išče samo po imenih mest (geoimena vrste TOWN) in vrne samo eno zgradbo na mesto.
   • DistinctBuildingByRegionLocator - Išče samo po imenih regij (geoimena vrste REGION) in vrne samo eno zgradbo na regijo.
   • DistinctBuildingByCountryLocator - Išče samo po imenih držav (geoimena vrste COUNTRY) in vrne samo eno zgradbo na državo.
   • DistinctBuildingByContinentLocator - Išče samo po imenih kontinentov (geoimena vrste CONTINENT) in vrne samo eno zgradbo na kontinent.
3. Multi iskalec, ki kombinira več iskalcev.
   Iskalec najprej delegira iskanje prvemu podanemu iskalcu, nato drugemu, nato tretjemu in tako dalje. Zadetke vseh iskalcev vrne v enem seznamu po vrsti tako, kot so bili najdeni.
   • CompositeLocator - Delegira iskanje po vseh navedenih iskalcih.
   • FullCompositeLocator - Predpripravljen iskalec, ki delegira iskanje po vseh osnovnih iskalcih.
4. Multi iskalec, ki preide na naslednjega iskalca, če prejšnji ne vrne zadetkov.
   Iskalec najprej delegira iskanje prvemu podanemu iskalcu. Če ta ne vrne nobenega zadetka, se iskanje delegira drugemu, drugače se takoj vrnejo zadetki samo prvega iskalca. Ostali sploh ne pridejo na vrsto.
   • FallbackLocator - Delegira iskanje po navedenih iskalcih, dokler eden ne vrne zadetkov.
   • DefaultFallbackLocator - Predpripravljen iskalec, ki smiselno delegira iskanje po osnovnih iskalcih, dokler eden ne vrne zadetkov.

Slika 7.1: Diagram aktivnosti iskanje z multi iskalcema CompositeLocator in FallbackLocator.

Z multi iskalci je možna zelo zapletena in fino nastavljiva kombinacija vseh iskalcev, tudi več multi iskalcev, npr.:

Locator locator=new FallbackLocator(new CompositeLocator(
  new StreetLocator(), new BuildingLocator()),
  new FallbackLocator(new DistinctAddressByTownLocator(),
    new DistinctAddressByCountryLocator()));

Koda 7.1: Primer bolj zapletene kombinacije iskalcev in multi iskalcev.

Vsakemu iskalcu lahko nastavimo največje število zadetkov (maxResults), ki jih vrne. V primeru sestavljenega iskalca (CompositeLocator) se iskanje prekine, ko je skupaj najdeno dovolj zadetkov. Drugače pa velja največje število zadetkov posameznega iskalca, če ga nastavimo. V kolikor največjega števila zadetkov za posameznega iskalca ne nastavimo, velja zanj število, ki smo ga nastavili za multi iskalca.

Locator locator=new AddressLocator();
locator.setSearchString("cank ul. 3");
locator.setMaxResults(10);
List<? extends Place> places=this.geocodingService.find(locator);

Koda 7.2: Primer uporabe iskalca AddressLocator.

Na strežniški strani vsak iskalec naredi svoje delo. Vsak osnovni iskalec poišče zadetke neposredno v podatkovni zbirki. Multi iskalec samo uporabi osnovne iskalce, kar pomeni, da se poizvedba v zbirki požene večkrat, za vsakega osnovnega iskalca posebej.

7.2 Algoritem

Vsak osnovni iskalec najprej primerno razčleni (angl. parse) iskalni niz. Odstrani vse nečrkovne (angl. non-alphabetic) in neštevilčne (angl. non-digit) znake in jih razkosa v več podnizov.

final String regex="[\\s\\p{Punct}]+";

Koda 7.3: Regularni izraz (angl. regular expression, regex), ki predstavlja vse nečrkovne in neštevilčne znake. Z njim se iskalni niz razkosa na čiste besede.

Vsak podniz se nato poišče kot del geoimena v podatkovni zbirki:

geoname.name like '%podniz%'

Koda 7.4: Izrezek v SQL-ju, kako se iščejo podnizi v delu geoimena v podatkovni zbirki.

Manjša izjema je AddressLocator, ki išče tudi po hišnih številkah, zato pred iskanjem preveri še, kateri podnizi so podobni hišnim številkam (se začnejo s cifro):

final String houseNumberRegex="[0-9].*";

Koda 7.5. Regularni izraz, ki predstavlja besede, ki se začnejo s cifro - hišne številke.

AddressLocator poleg imena ulic išče še po hišnih številkah:

geoname.name like '%ime%' and geoname.type='ADDRESS'
and address.houseNumber like 'hisnaStevilka%'

Koda 7.6: Izrezek v SQL-ju, kako se iščejo naslovi v podatkovni zbirki.

Vsak iskalec išče po vseh podnizih tako, da mora geoime vsebovati vse podnize (lahko v različnem vrstnem redu), sicer ni zadetek. Izjema je AddressLocator, ki obravnava hišno številko ločeno.
Poizvedbe so definirane na enem mestu, v vmesniku DAO (FindingDao). Implementacija ima generator poizvedbe, ki podnize z operatorjem IN združi.

select s
from Street as s
join s.geoNames as geoname
where (lower(geoname.name) like '%cank%'
  and lower(geoname.name) like '%ul%')
  and geoname.type='STREET'

Koda 7.7: Primer poizvedbe HQL, ki bi se tvorila z iskalcem StreetLocator in iskalnim nizom "Cank ul.".

Pri uporabi iskalca DistinctStreetByTownLocator z istim iskalnim nizom, bi bila poizvedba rahlo bolj zapletena in bi vsebovala podpoizvedbo (angl. subselect query), saj ta iskalec vrne le en (prvi) zadetek na mesto:

from Street as s
where s in (
  select min(s)
  from Street as s
  join s.geoNames as geoname
  where (lower(geoname.name) like '%cank%' and lower(geoname.name) like
    '%ul%')
  and geoname.type='TOWN'
  group by geoname.name
)

Koda 7.8: Primer poizvedbe HQL, ki bi se tvorila z iskalcem DistinctStreetByTownLocator in iskalnim nizom "Cank ul.".

Slika 7.2: Rezultat geokodiranja v središču Ljubljane. Rdeči kvadratki so naslovi, ki jih je našel AddressLocator z iskalnim nizom "cank 10" (Cankarjeva cesta 10, 10a in 10b). Modri črti predstavljata cesti, ki ju je našel StreetLocator z iskalnim nizom "cank" (Cankarjeva cesta in Cankarjevo nabrežje).

Storitev nima vgrajene logike neposrednega prepoznavanja vrste iskanega podatka (ali uporabnik išče naslov, cesto ali zgradbo), to je prepuščeno odjemalcu. Ta lahko z dodatno logiko ugotovi, kaj uporabnik želi, in uporabi ustrezne iskalce. Ali pa uporabniku kar ponudi, da si sam izbere iskalca. Lahko pa uporabi kakšnega od prednastavljenih multi iskalcev, ali sestavi svojega, in s tem že kar dobro izboljša natančnost iskanja.

Da bi bilo iskanje popolno, si prizadeva ekipa, ki izdeluje PAGC (Postal Address Geo-Coder). Pomembno pri tem izdelku je, da zna najprej standardizirati iskalni niz, to je ugotoviti, katero vrsto podatka uporabnik išče. Pri tem uporabljajo posebne zbirke podatkov: leksikone in pravila. Nato preiščejo indeksirano podatkovno zbirko po točnih zadetkih in po fonetičnih zadetkih (algoritem soundex), hkrati pa vsak zadetek ovrednotijo.
V tem sistemu je standardizacija iskalnega niza na nek način izvedena s številnimi osnovnimi in multi iskalci. Dodatno vrednost bi iskalci imeli, če bi znali zadetke ovrednotiti in jih sortirati po ustreznosti. Oboje bi pridobili, če bi uporabili eno od orodij za celobesedilno iskanje.

7.3 Celobesedilno iskanje

Pri geokodiranju se srečamo z iskanjem in primerjanjem nizov oz. podnizov. Uporabnik posreduje nek niz (naslov ali le nek del naslova, imena ceste, zgradbe ipd.), storitev pa preišče vsa geoimena v podatkovni zbirki in vrne zadetke. Pri naprednejšem iskanju bi to delo prepustili orodjem, ki omogočajo celobesedilno iskanje (angl. full text search).

Takšna orodja so v bistvu pravi iskalni stroji (angl. search engine), kot jih poznamo iz drugih uspešnih aplikacij, iz, npr., spletnih iskalnikov. Ti iskalni stroji poznajo celo vrsto tako imenovanih analizatorjev in filtrov, ki znajo, npr., iskati po korenu besede, predvidijo celo napačen vnos uporabnika (vsebujejo črkovalnik), iščejo nize, ki se izgovarjajo podobno (fonetični algoritmi), in ovrednotijo ustreznost zadetka po primernosti (angl. relevance).

Preizkusil sem celobesedilno iskanje z ogrodjem Compass, ki uporablja zelo priljubljen iskalni stroj Apache Lucene. V sistemu ga na koncu nisem uporabil.

Nastavitev je razmeroma enostavna (primer je v projekti.zip v paketu tinel-gis-geocoding-compass), saj se Compass lepo zlije s Springom in Hibernateom.
Podobno kot pri tehnologiji ORM, Compass potrebuje preslikavo (angl. mapping), ki opisuje, kako in kateri podatki bodo na voljo za iskanje. To lahko storimo preprosto z dodatnimi Compassovimi oznakami (angl. annotations) neposredno na domenskih objektih ali pa ločeno v preslikovalni datoteki XML. Oboje je na las podobno preslikovanju ORM za Hibernate.
Nazadnje definiramo še nova Springova zrna, ki tvorijo Compassov iskalnik.
Celobesedilno iskanje je tako pripravljeno. Vse, kar moramo še storiti, je, da poženemo prvo indeksiranje in napišemo nekaj iskalnih poizvedb.

Iskalni stroj temelji na dobro premišljenih indeksih, ki jih privzeto hrani v posebnih datotekah na trdem disku. Zaradi tega je zelo podoben sami podatkovni zbirki.
Ob indeksiranju Compass samodejno iz podatkovne zbirke pridobi ustrezne podatke in jih indeksira.

Poizvedbe so minimalistične. Pri iskanju navedemo ime atributa in iskalni niz. Iskalni stroj pozna tudi preprosto in obširno sintakso, s katero lahko kar v poizvedbi vplivamo na iskanje in ovrednotenje zadetkov.

String query="GeoName.name:ljub* AND GeoName.type=TOWN";

Koda 7.9: Primer poizvedbe pri celobesedilnem iskanju, ki poišče vsa geoimena mest, ki se pričnejo z nizom "ljub".

Ob začetnem navdušenju, da iskanje pravzaprav deluje, sem kasneje prišel do ugotovitve, da za naše potrebe celobesedilno iskanje ne prinaša dovolj nove vrednosti:

1. Celobesedilno iskanje se da v celoti nadomestiti samo z bolj zapletenimi poizvedbami po podatkovni zbirki.
2. Celobesedilno iskanje je včasih tudi do dvakrat hitrejše kot poizvedovanje po podatkovni zbirki, vendar vrne le delne rezultate. Npr., ob iskanju naslovov ne vrne lokacije, ker ni indeksirana. Po iskanju je tako treba rezultate dopolniti še iz zbirke, kar predstavlja dodatno poizvedbo. Hitrost je v tem primeru nižja.
3. Indeks je treba posebej vzdrževati (ob vsaki spremembi v podatkovni zbirki je treba indeks na novo zgraditi).
4. Iskanje po naslovih je povzročalo težave, vsaj pri uporabi ogrodja Compass. Naslovi so sestavljeni iz več geoimen, vsak naslov vsebuje tudi eno ime mesta (geoime vrste TOWN). Če iščemo naslove samo po določenem imenu mesta, potem logičen iskalni niz "name:ljubljana AND type:TOWN" ne daje pričakovanih rezultatov. Namesto da bi vrnil vse naslove, ki so v mestu Ljubljana, vrne kar vse naslove, ki vsebujejo geoime vrste TOWN - to so vsi.

Celobesedilno iskanje zadetke rangira. V tem sistemu je to zelo omejeno, saj dobro deluje le pri iskanju geoimen, pa še tedaj je rangiranje treba vnaprej določiti s tako imenovano ojačevalno funkcijo (angl. boost). Sama geoimena pa kot zadetki ne prinašajo neke uporabne vrednosti, saj ne vsebujejo prostorskega podatka.

Glede na vse skupaj, sem se odločil opustiti celobesedilno iskanje. Klasično iskanje s pomočjo poizvedb v zbirki skupaj s poljubnimi iskalci trenutno povsem zadostuje.

Edini zelo koristen primer uporabe celobesedilnega iskanja, ki si ga lahko zamislim, je podoben tehnologiji Google Suggest ^[25] in sorodnim:
Uporabnik prične v odjemalcu z grafičnim uporabniškim vmesnikom v vnosno polje vpisovati iskalni niz. Ko vpiše, recimo, vsaj tri znake, se sproži celobesedilno iskanje nad geoimeni. Iskanje se dogaja v ozadju, uporabniku pa se zadetki nemudoma izpišejo v spustnem seznamu kot predlogi. Ko uporabnik izbere predlog, se sproži običajna poizvedba v podatkovni zbirki glede na vrsto izbranega geoimena, zadetki pa se narišejo na zemljevid.

7.4 Zmogljivost

Na hitrost poizvedbe v največji meri vpliva število podatkov v podatkovni zbirki. Razlike med enim in drugim iskalcem so predvsem razlike v tem, nad kakšno množico podatkov se iskanje izvaja, poizvedba je namreč pri vseh zelo podobna. Zato kakšne zanimive primerjave ne morem narediti.

Pri testiranju zmogljivosti storitve sem izvedel trinivojsko meritev, ki je pokazala hitrostne razlike med tremi različnimi nivoji v sami arhitekturi storitve:

1. DAO - Neposreden klic metode, ki pripravi poizvedbo in jo pošlje podatkovni zbirki za obdelavo.
2. Storitev - Klic storitve z iskalcem. Iskalec pripravi posredovane iskalne podatke in pokliče DAO. Pripravi rezultate.
3. Odjemalec - Klic metode storitve z iskalcem prek HTTP Invokerja na zagnan strežnik storitve.

Slika 7.3: Trije nivoji v arhitekturi storitve (DAO, storitev in odjemalec) pomembni pri trinivojski meritvi zmogljivosti.

Vse tri nivoje sem testiral na lokalnem računalniku (testi, strežnik in zbirka so tekli lokalno). Parameter, ki sem ga spreminjal, je največje število zadetkov (maxResults), saj ta najbolj vpliva na končno hitrost. Vsak klic sem ponovil stokrat z enim zagonom okolja, vsako meritev pa trikrat.
Iskal sem naslove. Pri meritvi na nivoju DAO je bil iskalni niz "Cank" ter hišna številka "1". Na nivojih storitve in odjemalca je bil iskalni niz "Cank 1" in iskalec AddressLocator.

Tabela 7.1: Rezultati trinivojske meritve zmogljivosti. Manj je bolje.

Graf 7.1: Rezultati trinivojske meritve zmogljivosti. Manj je bolje.

Rezultati kažejo na hitrost celotne infrastrukture. Počasnejše izvajanje pri večjem številu zadetkov (maxResults) gre pripisati prenašanju (angl. fetch) rezultatov med zbirko in programom. Storitev in odjemalec sta pričakovano nekoliko počasnejša od DAO, kar je posledica dodatnih funkcij, ki jih opravita (uporaba iskalca, pripravljanje rezultatov za odjemalca). Zanimiv pa je ravno odjemalec, saj je malenkost hitrejši od storitve. To je posledica tega, da je strežnik skozi vse meritve tekel in si je tako že napolnil predpomnilnik (angl. cache). Komunikacija med strežnikom in odjemalcem (protokol HTTP) pa očitno ne vpliva toliko, res pa je, da sta bila oba, strežnik in odjemalec, na istem računalniku, tekla sta lokalno.