Dávid Kováč - Distance Search

    1.    Opis problému

    Distance search, ale tiež aj vyhľadávanie na základe vzdialenosti slúži na vyhľadávanie konkrétneho objektu podľa vzdialenosti k referenčnému bodu. V mojom zadaní je týmto objektom množina hotelov v Bratislave. Referenčný bod predstavuje konkrétnu ulicu Bratislavy. Cieľom vyhľadávania na základe vzdialenosti v tomto zadaní je zobraziť relevantné výsledky k hľadanému výrazu zoradené podľa vzdialenosti od referenčného bodu. Samotnému používateľovi teda vieme poskytnúť služby, ktoré na danom mieste hľadá, v mojom prípade ubytovacie služby v hoteloch mesta Bratislavy.


    Za vzdialenosť  medzi referenčnými bodmi sa môže považovať fyzická a komunikačná vzdialenosť. Fyzickú vzdialenosť predstavuje vzdušná čiara medzi jednotlivými referenčnými bodmi. Naopak komunikačná predstavuje napríklad cestnú komunikáciu, ktorá je iná ako vzdušná vzdialenosť. V tomto zadaní sa zohľadňuje vzdušná vzdialenosť. Vo všeobecnosti pri vzdušnej vzdialenosti je potrebné počítať aj zakrivenie zeme. V tomto prípade, keďže toto zadanie je zamerané na jednu lokalitu, nemá veľký význam uvažovať so zakrivením. Pre výpočet vzdialenosti sa používa zemepisná šírka (latitude) a zemepisná dĺžka (longitude) obidvoch referenčných bodov.


    Samotný distance search môžeme rozdeliť na dve dolezite zalezitosti. Prvou zalezitostou je ziskavanie dat (parsovanie adries z dokumentov, získavanie GPS súradníc, identifikovanie jedinečných údajov, apod.). Druhú záležitosť tvorí samotné vyhľadávanie v týchto dátach. Je potrebné vyhľadať relevantné zdroje a zobraziť ich aj na základe vzdialenosti od referenčného bodu. V tejto práci som sa venoval obidvom častiam.

    2.    Prehľad súčasných riešení

    Medzi asi najznámejšie riešenie patrí GoogleMaps so svojou službou „Search nearby“. Výsledky sa však nezobrazujú v prvom rade podľa vzdialeností, ale podľa relevancie a až potom podľa vzdialenosti. GoogleMaps poskytuje oveľa viacej možností ako je len vyhľadávanie na základe vzdialenosti. Medzi ne patria napr. nepriame meranie vzdialenosti medzi dvomi bodmi, tzn. Nie vzdušnou čiarou. Vo veľkom  sa však táto služba používa na znázornenie trasy, určenie najrýchlejšej, najekonomickej cesty apod. Pri týchto prístupoch sa uplatňujú teórie grafou a algoritmy najkratšej cesty, prehľadávanie grafou a pod.


    Portál superpages.com poskytuje službu „Search by distance“. Táto služba vyhľadá stránky, ktoré obsahujú hľadané kľúčové slovo a zoradí ich podľa vzdialenosti od referenčného bodu. Vzdialenosť a počet výsledkov sa dá nastaviť. 
    Obidve tieto stránky/spoločnosti poskytujú jednak služby na získanie adresy z GPS súradníc a aj získanie ulice/mesta podľa GPS súradníc.

    3.    Opis dát

    Ako dáta som použil crawlované stránky hotelov, ktoré našiel vyhľadávač portálu zoznam.sk pre Bratislavu. Celkových výsledkov bolo okolo 169. Z tohto počtu bolo  5 výsledkov sponzorovaných odkazov. Relevantných výsledkov bolo 55, kde ostatné výsledky odkazovali na stránky poskytujúce ubytovanie alebo služby nejakým spôsobom spojené s ubytovaním. S pomocou crawlera sa mi z týchto 55 stránok podarilo stiahnuť 42 doménových stránok (+21 zo subdomén), ktoré som potom zindexoval.


    Nie všetky dáta tvorili vhodné vstupy pre indexovanie.  Z tohto dôvodu sa znížil aj počet domén, ktoré boli reálne zindexované. Dôvodom, prečo stránky neboli zindexované je aj to, že samotný obsah bol vytvorený vo flashi, resp. stránku tvorili obrázky. Takýchto stránok bolo až osem. Ďalším problémom, ktorý v podstate znemožnil scrawlovať stránku boli chybné linky.  Našťastie takto vytvorená bola iba jedna doména.
    Celkovo bolo k scrawlovaných 15200 html stránok. Ako crawaler som použil nástroj HTTrack.
    Pri získavaní adresy sa vyskytli rôzne formáty, niektoré neboli štandardné a preto ich nebolo možné zachytiť. Použil som nasledujúce triedy pre získanie jednotlivých častí adresy.

     

    #P.O. (BOX), predložka pred ulicou alebo ulica, namestie ul.
    STREET_FORNAME = "(((P\\s*\\.\\s*O\\s*\\.\\s*|(" + UPPER + LOWER + "{1,2}|" + LOWER + "+\\.?)\\s+)(?<![\\r\\n])))?"
    #slovo začánajúce veľkým písmenom
    CAPITAL_WORD = UPPER + LOWER + "+";
    
    #názov ulice, Hlavna 29, apod
    STREET_NAME = CAPITAL_WORD;
    
    #Frana Mojtu 9
    SECOND_NAME = "(" + UPPER + "?" + LOWER + "+)";
    
    #prve číslo domu Hlavná 29
    FIRST_HOME_NUM = "\\d{1,4}";
    
    #druhé číslo domu Štúrova 29/A, 29/40
    SECOND_HOME_NUM = "(\\s*([/|\\\\]\\s*([\\p{Alpha}]|[\\p{Digit}]+)|[\\p{Alpha}]))?";
    
    #obidve čísla spolu
    HOME_NUM = "(" + FIRST_HOME_NUM + SECOND_HOME_NUM + ")?";
    
    #PSČ 098 01, 09801, SK-0908 01
    PSC = "(\\p{Alpha}{2}\\s*-\\s*)?(\\d{3}\\s\\d{2}|\\d{5})";
    
    #mesto SK-Bratislava, Bratislava
    CITY = "(\\p{Alpha}{2}\\s*-\\s*)?" + CAPITAL_WORD;
    
    #tvar mesto psc
    PSC_CITY = "(" + PSC + "\\s*(\\s|,|\\*)\\s*" + CITY + ")";
    
    #tvar psc mesto
    CITY_PSC = "(" + CITY + "\\s*" + PSC + "(?!\\p{Digit}))";
    
    #jedna z predchádzajúcich možností
    PSC_AND_CITY = "(" + PSC_CITY + "|" + CITY_PSC + ")";
    
    #vyskladaný regulárny výraz
    ADDRESS_PATTERN = "(?:" + STREET_FORNAME + STREET_NAME + "\\s+(?<![\\r\\n])(" + HOME_NUM + "|" + SECOND_NAME + "\\s*\\.?\\s*" + HOME_NUM + ")(\\s|[,\\*])+" + PSC_AND_CITY + "(\\s|,|\\.)?)";
    

    4.    Opis riešenia

    Ako už bolo vyššie spomenuté, toto zadanie môžeme rozdeliť do dvoch častí, a to na indexovanie a vyhľadávanie.

    4.1.    Indexovanie

    Prvým a asi najväčším problémom bolo kódovanie jednotlivých html stránok. Samotný crawler zisťoval, či je správne nastavené kódovanie, ak nie, tak zapísal vlastný meta tag, ktorý toto kódovanie upravoval. Týmto vznikol problém pre parser, ktorý si prepínal kódovanie na základe meta tagu. Takto nastávala situácia, kedy si parser prehadzoval kódovania a nakoniec ho i tak zle nastavil. Prvotne riešenie bolo nastavenie defaultného kódovania, to však už bolo potrebné robiť zásahy do knižníc. Toto tiež nestačilo a bolo potrebné vytvoriť okrem dodatočných tried pre hml parser aj parser, ktorý extrahuje kódovanie zo súboru (ešte predtým ako sa spustí html parser). Toto kódovanie sa zisťovalo pomocou regulárnych výrazov. Najprv sa zistí, či nie je kódovanie nastavené crawlerom, ak nie vyhľadá sa zodpovedajúci meta tag. Ak ani ten neexistuje, nastaví sa defaultne UTF-8.


    Ďalšou etapou bolo vytvorenie regulárneho výrazu pre získavanie adries. Aj napriek tomu, že som bol zameraný na Bratislavu, snažil som sa vyhnúť použitiu slova „Bratislava“ ako obmedzeniu. Obmedzením na mesto bolo, že to je jednoslovné mesto.


    V prvom rade som si určil skupiny znakov, tj. veľké a malé písmena (s diakritikou).
    K získaným adresám sa zisťovali GPS súradnice cez googlemaps . Priame volania googlemaps API nebolo možné, pretože sme potrebovali súradnice ešte na strane aplikačného servera. Preto bolo potrebné odchytiť si adresu a parametre. Ďalším problémom spojeným s googlemaps bol chybový kód 620, ktorý hovoril o príliš veľkom počte požiadaviek za daný čas. Tento problém sa vyriešil počkaním určitú dobu a opakovaním požiadavky, maximálne však päťkrát.


    Podobným problémom ako nesprávny formát adresy bola aj nesprávna adresa, kedy sa napríklad naviac k názvu ulici pridávalo slovo „ulica“, resp. „ul.“. V takomto prípade googlemaps ulicu nepoznalo a vrátilo chybový kód 602. Túto situáciu som vyriešil opakovaním požiadavky s tým, že dané slová som z adresy odstránil.
    Nakoniec bolo potrebné okrem zindexovania a uloženia indexov, o ktoré sa postarala knižnica lucene, nájdené unikátne adresy uložiť a k nim prislúchajúce hotely. Pre ľahšiu inštaláciu som zvolil zápis do súboru.
    Index sa vyvára do adresára index v adresári, kde sa nachádza kontext aplikácie (konkr. príklad na mojom počítači je to cesta c:\Program Files (x86)\Apache Software Foundation\Tomcat 6.0\webapps\distanceSearch\index\).
    Spúšťacou triedou je trieda Indexer, ktorá číta súbory z daného adresára a posiela ich triede HTMLDocument. Táto trieda si vyvára HTMLParser, ktorý poskytuje priamo (titulok, obsah, atď.) alebo nepriamo (adresa z AddressParser) dáta pre indexovanie. HTMLParser používa triedu EncodingParser, ktorá vracia kódovanie danej stránky.

    4.2.    Vyhľadávanie

    V prvom rade bolo potrebné vyhľadať obsah zodpovedajúci danej požiadavke. Tento krok je vzriešený podobne ako indexovanie tak aj vyhľadávanie pomocou lucene. Po vyhľadaní relevantných dát je potrebné ich zoradiť na základe vzdialenosti od referenčného bodu, a tiež odstrániť duplicitné stránky. Najprv sa zistila vzdialenosť od referenčného bodu a táto vzdialenosť potom tvorila index/poradie. Ak nejaká iná stránka mala rovnakú vzdialenosť, zaradila sa za predchádzajúcu, ktorá mala vyššie skóre vďaka obsahu. Avšak najprv sa zistilo, či to nie je tá istá stránka, len s iným názvom adresy (s diakritikou / bez diakritiky). Túto časť by bolo vhodnejšie presunúť ešte do indexovania. Takto dostaneme zoznam, ktorý je primárne usporiadaný podľa vzdialenosti a sekundárne podľa relevancie k hľadanému výrazu. Samotné vyhľadávanie je implementované iba v triede Searcher.


    Samotné zadanie som sa implementoval v jazyku JAVA. Pri svojej práci som použil WinHTTracker ako crawler. Na zindexovanie a vyhľadávanie v scrawlovaných súboroch som použil nástroj Apache Lucene. Na parsovanie html stránok som použil voľne dostupný htmlparser, ktorý som si podľa potreby upravil.  Pre získanie GPS súradníc využívam nepriame volanie GoogleMaps Api.  Ako formát zápisu jedinečných adries a údajov o stránke do súboru som si zvolil formát JSON,pre ktorý som použil knižnicu org.json. Samotná aplikácia je vytvorená ako webová aplikácia pre Apache Tomcat (testované na verzii 6.0).


    Dôležitou poznámkou je, že scrawlované stránky musia  byť v štruktúre webu, tzn.  Koreňový adresár musí mať v názve názov domény (napr. c:\tmp\crawled\www.hotelxyz.sk\). V samotnej aplikácii  je pripravená trieda URLCrawler, ktorej cieľom má byť prechádzanie stránok a crawlovanie nie ich obsahu, ale iba liniek v rámci domény. Takto scrawlované linky by tvorili základ, pre html parser, ktorý by z týchto liniek stiahol obsah a sparsoval. Týmto spôsobom by sme sa vyhli zbytočnému sťahovaniu dát lokálne na disk. Príkladom môže byť aj moja sada dát, ktorá predstavovala 1,5GB (čo však nie je veľa, ale nemusí to byť).

    5.    Vyhodnotenie  

    Indexovanie bolo vykonané na dvoch sadách stránok na menšej (1000 stránok) a na väčšej (15 200 stránok). V prvom teste sa našlo 241 adries, z toho bolo 31 unikátnych. Tieto adresy sa našli na ľá rôznych serveroch. Dve rôzne adresy sa väčšinou našli z dôvodu rôzneho formátu adresy.

    V druhej sade bolo nájdených 4500 adries, z toho 1500 bolo zle urcených, alebo sa nenašli pomocou GoogleMaps. Počet unikátnych adries bolo 68. Dôvodom chybných adries boli adresy, kde mesto sa skladalo z dvoch a viacerých názvov.

    Cieľom tohto zadania bolo zamerať sa na hotely v Bratislave. Pri adresách, ktoré patrili do tejto oblasti, regulárny výraz ich nemal problém nájsť. Toto sa dá zo subjektívneho hľadiska považovať za obstojné. Avšak, ak by sme chceli rozšíriť vyhľadávanie aj do iných miest, bolo by potrebné regulárny výraz upraviť.

    Vyhľadávanie je prispôsobené nájdenniu najbližšieho miesta k zadanému referenčnému bodu. Váhovaním vzdialenosti a relevantnosti obsahu by sme dosiahli iné výsledky, ktoré by boli možno objektívnejšie.

    6.    Inštalácia a opis aplikácie

    Inštalácia  aplikácie sa vykonáva štandardným spôsobom , nakopírovaním  tzv. „warka“ (distanceSearch.war) z adresára distanceSearch/out do adresára webapps aplikačného serveru Tomcat. Spustenie sa vykoná zadaním adresy, na ktorej beží aplikačný server a zadaním mena aplikácie (napr. localhost:8081/distanceSearch).
    Na obrázku (Obrázok 1) je znázornená obrazovka po spustení aplikácie. Na výber sú dve možnosti indexovanie a vyhľadávanie. Po zvolení „ReIndex“ sa objaví obrazovka podobná ako na obrázku (Obrázok 2).


     obr1.jpg
    Obrázok 1 Hlavná stránka


    Tu je potrebné zadať koreňový adresár všetkých scrawlovaných stránok a stlačiť tlačidlo „ReIndex“. Následne sa začnú indexovať stránky čo znázorňuje aj obrázok (Obrázok 3). Ak sa nájde nová adresa, zobrazí sa informácia podobná ako na obrázku (Obrázok 4). Ak sa naopak nájde už existujúca (už raz nájdená) adresa, zobrazí sa informácia podobná ako na obrázku (Obrázok 5).
    Po ukončení indexovania sa unikátne adresy zapíšu do súboru, čo znázorňuje obrázok (Obrázok 6).


     obr2.jpg
    Obrázok 2 Zadanie zdrojového adresára

    obr3.jpg 
    Obrázok 3 Informácie o indexovaní

    obr4.jpg 
    Obrázok 4 Informácie o nájdenej adrese


    obr5.jpg 
    Obrázok 5 Informácie o už nájdenej adrese


    obr6.jpg 
    Obrázok 6 Zapisovanie unikátnych adries do súboru

    obr7.jpg 
    Obrázok 7 Informácie o výsledkoch reindexovania

     

    Tag page (Edit tags)
    • No tags

    Files 7

    FileSizeDateAttached by 
     obr1.jpg
    Obrázok 1 Hlavná stránka
    208.2 kB12:51, 15 Jan 2009David.KovacActions
     obr2.jpg
    Obrázok 2 Zadanie zdrojového adresára
    201.39 kB12:51, 15 Jan 2009David.KovacActions
     obr3.jpg
    Obrázok 3 Informácie o indexovaní
    50.24 kB12:51, 15 Jan 2009David.KovacActions
     obr4.jpg
    Obrázok 4 Informácie o nájdenej adrese
    9.36 kB12:51, 15 Jan 2009David.KovacActions
     obr5.jpg
    Obrázok 5 Informácie o už nájdenej adrese
    10.83 kB12:51, 15 Jan 2009David.KovacActions
     obr6.jpg
    Obrázok 6 Zapisovanie unikátnych adries do súboru
    29.48 kB12:51, 15 Jan 2009David.KovacActions
     obr7.jpg
    Obrázok 7 Informácie o výsledkoch reindexovania
    23.12 kB12:51, 15 Jan 2009David.KovacActions
    You must login to post a comment.
    Powered by MindTouch Core