Toto je dokument opisujúci projekt, prácu na ňom a dosiahnuté výsledky.

    Abstrakt

    Projekt OSMLucener je spojením OSM dát s Lucene frameworkom. Ide o špecializovaný vyhľadávač založený na lucene frameworku, ktorý vyhľadáva v OSM mapových dátach. Výsledný softvér je schopný indexovať OSM dáta v postgre databáze a umožňuje v týchto dátach za pomoci aplikácie do príkazového riadku vyhľadávať. Vyhľadávanie je jednak podľa slov a jednak podľa polohy.

    Úvod

    Na internete existuje mnoho projektov, ktoré sú udržované dobrovoľníkmi. Jedným z takýchto projektov je i OpenStreetMap.org (ďalej len ako OSM). Tento projekt má ako primárnu úlohu vytvoriť mapu sveta, ktorá je voľne dostupná i na komerčné použitie.

    Projekt má mnoho nadšencov a vcelku stabilné vedenie a jasné smerovanie. Prispieť komunite je možné viacerými spôsobmi. Najčastejšie je to "mapovaním", teda vytváraním digitálnych, vektorových máp. Inými možnosťami prispievania je tvorba aplikácií, ktoré využívajú, alebo zviditeľňujú dáta zozbierané a udržiavané komunitou OSM.

    Ja som sa rozhodol prispieť aplikáciou, ktorá bude schopná prehľadávať dáta vytvárané touto komunitou. Keďže v oblasti vyhľadávania v OSM dátach už existuje jedna aplikácia, budem sa snažiť spraviť aplikáciu vyhľadávania maximálne prispôsobivú a kvalitnú.

    OSM

    Projekt, ako už bolo načrtnuté v úvode, zbiera a vytvára vektorové, digitálne mapové podklady celého sveta. Na rozdiel od komerčných máp, však dáva svojim tvorcom plnú voľnosť a umožňuje im vytvárať i objekty, ktoré by sme na komerčných mapách hľadali len ťažko. Vytvorené body, cesty a oblasti majú ako svoje atribúty tagy. Tagy sú dnes moderné a dovoľujú reflektovať rýchlo sa meniacu taxonómiu (folxonómiu) tagovaných objektov. Týmto spôsobom je možné do mapy zaznačiť "čokoľvek".

    Tagy sa však normalizujú a mnohé objekty majú už ustálené tagy, ktoré ich popisujú. Toto umožňuje mnohým programom pracovať s mapovými objektmi. Pri vyhľadávaní sa však nie je dobré spoliehať na fixnú množinu tagov.

    Projekt vytvára nielen dáta, ale ich i poskytuje a pre manažovanie dát vytvára i mnoho programového vybavenia. Jadro SW vývojárov sa sústreďuje na zabezpečenie maximálnej pohodlnosti pri ukladaní dát do celosvetovej databázy a na jeho následné kvalitné zobrazovanie. Komunita OSM vývojárov vytvorila a stále vytvára množstvo podporných programov pre tieto účely.

    Dáta, ich úložisko i distribúcia sú teda zabezpečené. Čo však použitie týchto dát? Toto je zatiaľ jedna zo slabších častí projektu. Vzniklo niekoľko projektov na navigáciu (hľadanie najkratšej cesty z miesta A do miesta B), pár projektov pre zobrazovanie dát na mobilných zariadeniach a i jeden projekt na vyhľadávanie v týchto dátach. Práve vyhľadávanie sa budem snažiť v tomto projekte vyriešiť kvalitnejšie a systematickejšie, ako je tomu teraz.

    Where Is It

    Where It Is je názov projektu, ktorý je aktuálne používaný na vyhľadávanie v mapových OSM dátach. Tento program, skript, vyhľadáva v dátach za pomoci SQL jazyka. Teda spraví priamo select do databázy s OSM dátami a hľadá zvolený výraz na dopredu určených miestach. Obmedzením je teda, že hľadá iba v menách miest, obcí a riek. Takisto hľadá iba presné výrazy a nereflektuje voľnosť tagovania. Teda neumožňuje hladať nové tagy v OSM dátach, ktoré vznikajú spolu s počtom do mapy zaznačených objektov. Viac o skripte where it is je na stránke. Jednoduchý interfejs pre vyhľadávanie za pomoci tohoto nástroja je tu.

    Projekt je jediným, ktorý som našiel. Všetky ostatné drobné aplikácie, ktoré som našiel, používali SQL select a vyhľadávanie bolo vždy teda prevedené nad databázou priamo. Zvyšné mnou nájdené aplikácie boli priamo súčasťou lokálnych skupín pracujúcich na OSM dátach. Slovenská skupina dobrovoľníkov pracuje na stránke freemap.sk. Jej vyhľadávanie je tiež vstavané priamo do web stránky a na vyhľadávanie používa SQL select-y.

    OSMLucener

    Projekt vyhľadáva v OSM mapových dátach nepriamo. Ako prvé si indexuje dáta v databáze a následne vyhľadáva v indexoch, prípadne si pri niektorých typoch vyhľadávaní pomáha i pôvodnou databázou. Výhodou databázy je ľahká práca so "spatial" informáciami.

    Projekt OSMLucener si vyžadoval znalosti jednak z oblasti Lucene framework-u a jednak znalosti OSM databázy. Ako prvé som si importoval do postgre databázy s postgis rozšírením dáta OSM pre Slovensko. Dáta pre Slovensko i celý svet je možné nájsť na stránkach OSM komunity.

    Indexovanie

    Indexovanie OSM mapových dát prebieha za pomoci vytvorenej konzolovej aplikácie. Aplikácia sa pripojí na databázu s OSM dátami, spraví si obraz o počte objektov v nej kvôli možnosti zobrazovania percentuálneho postupu pri indexovaní a pustí sa do indexovania.

    Indexovanie prebieha nad dvoma hlavnými typmi objektov. Objekty typu node a way. Objekt typu node je reprezentovaný jedným bodom na mape, teda súradnicami lon a lat. Objekt way je zložitejší. Skladá sa z usporiadaných dvojíc lon a lat súradníc. Podľa toho, či je prvý a posledný bod tejto "cesty" zhodný, sa tento typ objektu označuje ako way, alebo ako area. Oba hlavné typy objektov majú však spoločné metadáta.

    Informácie o objektoch (metadáta) sa nachádzajú v dvojiciach (pároch) key a value. Ide o voľný tagový štýl kategorizácie objektov. Príkladom môžu byť napríklad cesty. Cesta v meste sa napríklad označuje dvojicou highway=residential. Avšak chodník v meste je označený dvojicou highway=footway. Takýto spôsob označovania objektov v mape umožňuje zakresľovať dobrovoľníkom stále nové a nové typy objektov, ako napríklad nástupištia na autobusovej stanici, rôzne typy obchodov, či podnikov a podobne. Časom vznikla však ustálená základňa pre bežne mapované objekty a tak je pri indexovaní možné túto skutočnosť využiť.

    Pri indexovaní sa využíva "synonymický konfig", ktorý určuje, ako budú mapované dvojice z OSM databázy na slová, ktoré sa indexujú. Aby sa však neprišlo o možnosť vyhľadávania v novovytvorených tagoch, tak sa indexujú aj tagy. Takto sa nikdy nestane, že nebude možné nájsť nejaký objekt v OSM databáze. Toto je kľúčová výhoda oproti aktuálnym implementáciám vyhľadávania.

    Synonymický konfig

    Na začiatok uvediem kúsok reálneho konfigu pre Slovenskú verziu. Následne vysvetlím, čo znamenajú jednotlivé riadky a ako sa vykonáva indexovanie s pomocou tohoto konfigu.

    Záznamy v synonymickom slovníku:
    atm=*                                  ->    bankomat atm
    amenity=atm                            ->    bankomat atm
    amenity=post_box                       ->    poštová schránka
    bank=csob                              ->    ČSOB
    highway=footway                        ->    chodník pešia
    bank=*                                 ->    banka pobočka banky
    highway=*                              ->    cesta
    amenity=post_office                    ->   
    pošta

    Pri konfigu, ako je uvedený na predchádzajúcich riadkoch, sa prevody tagov z OSM databázy správajú nasledovne:

    Synonyma pre bank=csob:            ČSOB banka pobočka banky
    Synonyma pre bank=slsp:            banka pobočka banky
    Synonyma pre atm=yes:              bankomat atm
    Synonyma pre highway=yes:          cesta
    Synonyma pre amenity=post_box:     poštová schránka
    Synonyma pre amenity=post_officepošta
    Synonyma pre highway=footway:     
    chodník pešia cesta
    Synonyma pre asdf=asdf:            null

    Konkrétna dvojica tag=value tagu z OSM databázy je prevedená na synonymá, ktoré sa nachádzajú v konfigu pre túto dvojicu a za ne je pridaný riadok synoným z konfigu, ktorý je v tvare key=*. Ak sa niektorý z hľadaných riadkov v konfigu nenachádza, jednoducho sa nenachádza na výstupe synonym žiadne synonymum. Ukážkou môže byť napríklad prevod dvojice highway=footway na synonymá "chodník pešia cesta".

    Pri indefovaní sa indexujú jednak pôvodné tagy a hodnoty z OSM databázy a aj k nim prislúchajúce synonymá podľa aktuálneho konfigu. Originálne hodnoty tag=value z OSM databázy sú indexované do Lucene poľa s názvom otherTags a prislúchajúce synonymá sú ukladané do poľa s názvom parsedTags.

    Vyhľadávanie

    Pri vyhľadávaní je možné použiť priamo framework Lucene a jeho QueryParser. Keďže tento prístup by bol predsa len príliš jednoduchý, rozhodol som sa použiť i programovo vytvárané query. Vlastné filtre a zoraďovania podľa vzdialenosti. Tento prístup umožní konkrétnym aplikáciám používajúcim OSMLucener program, či knižnicu, veľkú variabilitu vyhľadávaní s vysokým dôrazom na polohové informácie.

    Filtre polohy

    Filter na polohu som implementoval iba jeden. Tento filter sa volá FilterToCircleArea a filtruje dokuemnty na základe polohy. Objekt je filtrom prijatý iba, ak je v zadanej vzdialenosti od referenčného bodu. Obmedzenie maximálnej vzdialenosti je v okolí +/- 0.01 stupňa zemepisnej šírky a výšky. Na takýto štvorec sa za pomoci spatial indexu orezáva hľadanie objektov nachádzajúcich sa v zadanom polomere.

    Filter polohy využíva štandardnú Lucene abstrantnúp triedu pre filter. Pri požiadavke na filtrovanie zostrojí bitovú masku filtra za pomoci selektu z databázy na ID objektov v danej vzdialenosti a následne ich v cykle pretransformuje na Lucene BitSet objekt.

    Zoraďovanie podľa vzdialenosti

    Zoraďovanie výsledkov podľa vzdialenosti a nie podľa dosiahnutého skóre vo vyhľadávaní je vykonávané za pomoci implementovania Lucene rozhrania SortComparatorSource. Implementácia sa nachádza v triede s názvom DistanceComparatorFromPostgreDB a využíva možnosti interfejsu podstatne lepšie, ako tomu bolo v ukážke v knihe Lucene in action.

    Sortovanie dokumentov prebieha po filtrovaní a vyhľadaní, takže sa k sortovaniu dostane malý počet dokumentov. Rádovo to bývajú maximálne desiatky dokumentov. Pre takéto množstvo je možné použiť pri zoraďovaní dokumentov dopyty na databázu a tak výpočet vzdialenosti za pomoci sferoidu WGS_1984 prevádza databáza. Výsledky sú v metroch. Zoraďovanie potom prebieha za pomoci získaných vzdialeností.

    Podobne, ako i filter polohy, potrebuje sorter poznať refernčnú polohu a potrebuje mať k dispozícii pripojenie na databázu.

    Použitie OSMLucener-a

    Táto kapitola opisuje možné použitie konzolovej aplikácie OSMLucener. Rovnaké možnosti sú i pri použití projektu ako knižnice. Konzolová verzia CLI aplikácie sa nachádza na tejto wiki stránke. Po stiahnutí je možné vykonávať bez potreby ďaľších komponentov nasledovne opísané úkony.

    Pre podrobnejšie vysvetlenie parametrov odporúčam spustiť program s parametrom --help. Kompletný výpis parametrov s ich popisom, popis fieldov v Lucene indexe, ale i možné kombinácie parametrov sú popísané v danom helpe k programu. Tuná uvádzam len "Quick how to".

    Indexovanie

    Ako prvý uvediem výpis konzolového programu OSMLucener.

    Help:
     -c CONNSTR  : Connection string. Je potrebný pri indexovaní a updejte. Ukážkový
                    connection string:
                   jdbc:postgresql://localhost/osmdb?user=os...ser&password=3
                   a#de5Pad9.
     -d INDEXDIR : Určenie adresára s indexom.
     -h          : Vypíše toto info, teda help.
     -i          : Parameter pre príkaz indexovania databázy.
     -q QUERY    : Query pre operáciu vyhľadávania.
     -u          : Parameter pre príkaz updejtovania databázy.

    Vyhľadávanie

    Vyhľadávanie je možné cez tú istú konzolovú aplikáciu, ako i indexovanie. Okrem tejto možnosti je dostupné vyhľadávanie i cez OSMLucener ako knižnicu. Vyhľadávanie má rôzne možnosti. Okrem vyhľadávania iba podľa kľúčových slov je možné vyhľadávať iba v zadanom geografickom území, prípadne výsledky vyhľadávania zoradiť podľa vzdialenosti od zadaného bodu.

    Klasický dotaz

    java -jar OSMLucener_fat.jar -d /tmp/luceneIndexLuvar2/ -q bankomat

    Ukážkové volanie vraví samé za seba. Pre vyhľadávanie viacerých slov, alebo s použitím zložitejších výrazov, je potrebné použiť úvodzovky, aby bola celá query odovzdaná ako jeden parameter. Uvediem ukážky niektorých advanced query.

    java -jar OSMLucener_fat.jar -d /tmp/luceneIndexLuvar2/ -q "+Tresko~ +supermarket +is_in:Košice"

    Dotaz s polohou

    java -jar OSMLucener_fat.jar -d /tmp/luceneIndexLuvar2/ -c "jdbc:postgresql://example.com/osm?user=os...assword=osmpwd" -q bankomat -y 48.15593638300127 -x 17.11220530293204 -r 1146

    Pre vykonanie dotazu s polohou potrebuje program aj pripojenie na databázu. Viac o funkčnosti mechanizmu je v predošlých kapitolách. Na ukážkovom príkaze vidno odovzdanie polohy a vzdialenosti v metroch, v ktroej sa má hľadať. O filtráciu objektov sa postará vlastný filter v Lucene a následne sa použije tiež vlastný sorter na zoradenie výsledkov podľa vzdialenosti od nich. Vzdialenosť je pre jednoduchosť zatial počítaná ako priamka medzi polohou a objektom.

    Precision a Recall

    V tejto kapitole sa pokúsim vyhodnotiť presnosť a pokrytie môjho vyhľadávacieho softvéru. Vo vyhodnotení zahrniem i porovnanie s vyhľadávaním použitým na stránke freemap.sk a vyhľadávanie za pomoci vyhľadávača google.

    Recall obyčajnej query
    Query Google Freemap OSMLucener Geonames
    +Tresko~ +supermarket +is_in:Košice  0 záznamov  0 záznamov  1 záznam  1 záznam
    +Tesco +supermarket +Košice  750 približne  0 záznamov  1 záznam  1 záznam
    +Parkovanie +Nitra  84 300 približne  0 záznamov  0 záznamov  1 záznam
     +bankomat +dulovo +námestie  218 približne  0 záznamov  1 záznam  0 záznamov

     Pre výsledky musím dodať, že v prvom prípade boli nájdené výsledky relevantné iba v OSMLucener programe. V druhom našiel google na prvých miestach ubytovanie namiesto supermarketu a zvyšné výsledky OSMLucener-u a Geonames boli v poriadku.

    Rôznorodosť kvality výsledkov je daná zdrojom informácií, ktoré majú k dispozícii jednotlivé portály / programy. Čo sa týka recall hodnotenia programu OSMLucener pri obyčajnej query, myslím, že môže dostať spokojne 100% v troch prípadoch, keďže v Košiciach sa nachádza jeden supermarket a na Dulovom námestí sa priamo nachádza iba jeden bankomat. Čo sa týka hľadania parkoviska v Nitre, OSMLuener zlyhal na plnej čiare. Síce v OSM databáze sa nenachádza mnoho parkovacích miest, ale nejaké tam predsalen sú. Chybou je, že ani jeden z nich nemá nastavený správne tag is_in a tak sa nič nenašlo. Geonames v tomto prípade tiež nenašiel miesto na parkovanie, ale iba mesto. Finálny recall na takto malej vzorke vyhľadávaní je teda 75%.

    Pre precision nebudem uvádzať tabuľku, keďže všetky nájdené výsledky programom OSMLucener boli plne relevantné. Pri indexovaní tagov si myslím, že nemôže pri vyhľadávaní prísť k chybe. Jediná možnosť je výskyt synoným, ako napríklad kúsok morbidný príklad, "odpočinok" by bolo možné nájsť i na odpočívadle pri dialnici, ale i na cintoríne.

    Pre spatial query nie je možné vykonať porovnanie s predchádzajúcimi portálmi, keďže implementácie spatial vyhľadávania sa zásadne líšia, alebo nie sú dostupné. Pre ukážku vyskúšam však spatial query na Dulovom námestí a pokúsim sa nájsť všetky bankomaty v okolí 300 metrov.

    java -jar OSMLucener_fat.jar -d /tmp/luceneIndexLuvar2/ -c "jdbc:postgresql://example.com/osmdb?user=...assword=pwd123" -q bankomat -y 48.14957 -x 17.13378 -r 300

     Výsledkom sú nasledovné objekty:

    ---------------------
    Dokument cislo: 0
    Score: 1.7786659
    Distance: 53.0
    author = LuVar
    id = 308811583
    name = VÚB, a.s.
    otherTags =  atm yes amenity bank addr:street Dulovo námestie addr:city Bratislava addr:housenumber 1
    parsedTags = bankomat atm
    type = NODE
    ---------------------
    URL: http://www.freemap.sk/?zoom=16&lat=48.1496758&lon=17.133076&marker=1
    ---------------------
    Dokument cislo: 1
    Score: 1.7786659
    Distance: 55.0
    author = LuVar
    id = 308811584
    name = Volksbank
    otherTags =  amenity atm
    parsedTags = bankomat atm
    type = NODE
    ---------------------
    URL: http://www.freemap.sk/?zoom=16&lat=48.1496392&lon=17.1330347&marker=1
    ---------------------
    Dokument cislo: 2
    Score: 1.7786659
    Distance: 163.0
    author = LuVar
    id = 304861794
    name = Tatrabanka
    otherTags =  amenity atm
    parsedTags = bankomat atm
    type = NODE
    ---------------------
    URL: http://www.freemap.sk/?zoom=16&lat=48.1487709&lon=17.1319326&marker=1
    ---------------------
    Dokument cislo: 3
    Score: 1.7786659
    Distance: 171.0
    author = LuVar
    id = 304861795
    name = Slovenská Sporiteľňa
    otherTags =  amenity atm
    parsedTags = bankomat atm
    type = NODE
    ---------------------
    URL: http://www.freemap.sk/?zoom=16&lat=48.1487685&lon=17.131817&marker=1
    ---------------------

     

    Literatúra

    Lucene (hlavná stránka projektu)

    Freemap.sk (stránka OSM komunity na Slovensku. Pomoc v otázkach tagov, ich početnosti a iné informácie. Komunikácia cez irc kanál)

    Zoznam tagov v Slovenskej OSM databáze (pomôcka pri písaní konfigu)

    PostGiS manual (informácie o optimalizovaní PostGiS indexov a optimalizovaní sql query)

    PlainText interné know how (práca s PostGiS, OSM štruktúra databázy)

    Compass (knižnica nad Lucene pre ORM a podobne. Využil som ich poznatky na fóre pri vlastnej implementácii)

    Doplnok

    Web rozhranie pre OSMLucener je dostupné a zväčša funkčné na adrese:

    https://dawn.ynet.sk:8444/OSMLucenerWeb/WhereItIs.jsp

    Ukážkové "spatial" vyhľadávanie je na nasledovnej adrese (môže trvať i 10 sekúnd):

    https://dawn.ynet.sk:8444/OSMLucener...at&format=html

    Tag page (Edit tags)
    • No tags

    Files 3

    FileSizeDateAttached by 
     OSMLucener.zip
    Zbalený celý eclipse projekt s knižnicami, konfigmi i zdrojovými kódmi.
    3.65 MB17:53, 22 Jan 2009Lubomir.VargaActions
     OSMLucener_fat.jar
    Spustiteľná výsledná CLI aplikácia
    2.24 MB15:58, 22 Jan 2009Lubomir.VargaActions
     synonyms.cfg
    súbor konfigu so synonymami
    1597 bytes01:39, 23 Jan 2009Lubomir.VargaActions
    Viewing 1 of 1 comments: view all
    Pokusný web interfejs ku vyhľadávaniu je dostupný na https://dawn.ynet.sk:8444/OSMLucenerWeb/WhereItIs.jsp
    Zatial funguje iba časť klasického hľadania. Je možné teda vyplniť query, nastaviť formát výstupu (htmp/xml) a kliknúť na "search". Viac funkcionality, teda spatial informácie pri hľadaní, do tohoto web interfejsu pribudnú neskôr. edited 01:47, 23 Jan 2009
    Posted 01:46, 23 Jan 2009
    Viewing 1 of 1 comments: view all
    You must login to post a comment.
    Powered by MindTouch Core