2-INF-147 Vyhľadávanie v texte, LS 2012/2013

Táto stránka sa týka ukončeného semestra. Navyše tento predmet už nebude vyučovaný. Pre potreby štátnicového bloku B a D ho nahrádza pnvý predmet Vybrané partie z dátových štruktúr.

Prezentácia článku

Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti vyhľadávania v texte. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok. K tomuto článku môžete dostať otázku aj na skúške.

Termíny

• Výber článku na prezentáciu do pondelka 15.4. v systéme Moodle. Každý článok môže prezentovať iba jeden študent, takže odovzdajte svôj výber radšej skôr. Kto si článok do uvedeného termínu nevyberie, bude mu nejaký priradený vyučujúcou.
• Prezentácie na prednáškach v posledných týždňoch semestra.

Rady k prezentácii

• Na prezentáciu budete mať 15-20 minút, pričom tento limit bude striktne dodržiavaný. Nechystajte si teda priveľa materiálu, rátajte aspoň 1,5 minúty na slajd.
• K dispozícii bude dátový projektor. Prezentáciu si doneste na USB kľúči v pdf formáte alebo na vlastnom počítači (aj tak je dobré doniesť si aj pdf, keby niečo nefungovalo). Môžete použiť tabuľu, ale s mierou, lebo vysvetľovanie pri tabuli ide pomalšie.
• Hlavným cieľom je porozprávať niečo zaujímavé z vášho článku vo forme prístupnej vašim spolužiakom (ktorí chodili na tento predmet, nepamätajú si však každý detail z každej prednášky). Nemusíte pokryť celý obsah článku a nemusíte použiť rovnaké poradie, označenie alebo príklady, ako autori článku.
• Nedávajte na slidy veľa textu, použite dostatočne veľký font a dobre viditeľné farby (podobné farby, napr. žltá na bielej, nemusia byť na projektore vôbec viditeľné).
• Použite čo najmenej definícií a označenia. Pojmy, algoritmy a dôkazy radšej ilustrujte na obrázku alebo príklade, než zložitým textom.

Typická osnova prezentácie (podľa potreby ju však možete meniť):

• Úvod: aký problém autori študujú, prečo je dôležitý alebo zaujímavý, má nejaký vzťah k niečomu z prednášok?
• Prehľad výsledkov: V čom je presne prínos autorov oproti predchádzajúcim prácam? Nemusíte robiť prehľad predchádzajúcich prác, len uveďte, čo je v článku nové. Malo by to byť jasné najmä z úvodu a záveru článku.
• Jadro: Vysvetlite nejaký kúsok zo samotného obsahu článku (časť algoritmu alebo dôkazu, niektoré výsledky z testovania na dátach a pod.)
• Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo)

Typy vhodných článkov

• Články empiricky porovnávajúce algoritmy na prácu s textom na reálnych dátach alebo popisujúce použitie týchto algoritmov v reálnych aplikáciach.
• Články o ďalších algoritmoch alebo ich variantoch, ktoré neboli/nebudú pokryté na prednáške
• Články o paralelných algoritmoch na prácu s textom.
• Články o podrobnejšej analýze algoritmov: dolné a horné odhady počtu porovnaní, analýza v priemernom prípade pre rôzne typy rozdelení a pod.

Príklady článkov

Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.

Algoritmy, teória:

• J. Fischer, V. Heun (2006) Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. CPM 2006. Novší algoritmus na hľadanie najnižšieho spoločného predka, experimentálne porovnanie. [pdf] Tento článok je už obsadený.
• C. Allauzen, M. Crochemore and M. Raffinot (2006) Efficient Experimental String Matching by Weak Factor Recognition. CPM 2006. [ pdf od vydavateľa - cez UK proxy] Faktorové orákulá vedú k veľmi rýchlym algoritmom na vyhľadávanie v texte.
• Cole, Hariharan, Paterson, Zwick (1995) Tighter Lower Bounds on the Exact Complexity of String Matching, SIAM Journal on Computing, 24(1):30-45 [ps] Dolný odhad na počet porovnaní.
• Fredriksson, Grabowski (2005): Practical and optimal string matching. SPIRE 2005. [pdf]. Efektívna verzia Shift-Or algoritmu.
• A. Andoni, T. S. Jayram, and M. Pătraşcu (2010) Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA 2010 [pdf] Komunikačná zložitosť výpočtu editačnej vzdialenosti.
• B. Porat, E. Porat: Exact and Approximate Pattern Matching in the Streaming Model. FOCS 2009:315-323 [pdf od vydavateľa - cez UK proxy] On-line pravdepodobnostný algoritmus s malou pamäťou.
• Hagai Cohen and Ely Porat (2010) Fast Set Intersection and Two-Patterns Matching. LATIN 2010. [Pdf od vydavateľa]
• Frederiksson and Mozgovoy (2006) Efficient parameterized string matching. Information processing letters. [pdf]

Algoritmy na iné typy problémov:

• A. Lubiw, L. Tanur (2004) Pattern Matching in Polyphonic Music as a Weighted Geometric Translation Problem. ISMIR 2004 [url] Algoritmus na hľadanie v hudbe. Tento článok je už obsadený.
• H. Hirjee and D. G. Brown (2009) Automatic detection of internal and imperfect rhymes in rap lyrics. Proceedings of the 10th International Society for Music Information Retrieval Conference. [pdf] Použitie algoritmov na lokálne zarovnanie na hľadanie rýmov.
• B Ma, X Sun (2008) More Efficient Algorithms for Closest String and Substring Problems. Research in Computational Molecular Biology RECOMB 2008. [pdf] NP-ťažké problémy dôležité vo výpočtovej biológii. Tento článok je už obsadený.
• Y. Xu, Y. Papakonstantinou (2007) Efficient LCA based keyword search in XML data. CIKM 2007: 1007-1010 [pdf] Vyhľadávanie v XML pomocou LCA. Tento článok je už obsadený.
• E.D. Demaine, S. Mozes, B. Rossman, O. Weimann: An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms 6(1): (2009) [pdf] Editačná vzdialenosť medzi stromami. Tento článok je už obsadený.

Aplikácie:

• Curtsinger, C., Livshits, B., Zorn, B., & Seifert, C. (2011). ZOZZLE: fast and precise in-browser JavaScript malware detection. In USENIX Security Symposium (pp. 33-48). [pdf] Použitie algoritmov na hľadanie vzorky pri hľadaní nebezpečných stránok s JavaScript kódom. Tento článok je už obsadený.
• S Burrows, SMM Tahaghoghi, J Zobel (2007) Efficient plagiarism detection for large code repositories. Software - Practice and Experience [pdf] Použitie algoritmov na lokálne zarovnanie pri detekcii pagiarismu.
• I. Sourdis and D. Pnevmatikatos (2003) Fast, Large-Scale String Match for a 10Gbps FPGA-Based Network Intrusion Detection System. Field-Programmable Logic and Applications (FPL). Hardvérová implementácia hľadania v texte s aplikáciou na informačnú bezpečnosť. [pdf]
• Yu, Chen, Diao, Lakshman, Katz (2006) Fast and memory-efficient regular expression matching for deep packet inspection. ANCS 2006. Efektívna implementácia regulárnych výrazov. [pdf] Tento článok je už obsadený.
• L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [pdf] Aplikácia v bioinformatike.
• Boldi and Vigna (2005) Mutable strings in Java: design, implementation and lightweight text-search algorithms, Science of Computer Programming 54(1).

Prehľadové články, ktoré nie sú vhodné na prezentovanie, môžu však byť zdrojom citácií na iné zaujímavé články.

• G. Navarro (2001) A guided tour to approximate string matching. ACM Computing Surveys [ps]
• G. Navarro, V. Mäkinen (2007) Compressed full-text indexes. ACM Computing Surveys [pdf]

Články navrhnuté študentami (a obsadené)

• Durian et al (2010) Bit-Parallel Search Algorithms for Long Patterns. SEA 2010 [pdf]

Rady k hľadaniu článkov

• Podľa kľúčových slov sa články dobre hľadajú na Google Scholar. Tam okrem iného nájdete aj linky na iné články, ktoré daný článok citujú, čo môže byť dobrý zdroj ďalších informácií.
• The DBLP Computer Science Bibliography je dobrý zdroj bibtexových záznamov, ak píšete projekt alebo inú prácu v Latexu a tiež sa dá použiť na nájdenie zoznamu článkov od jedného autora alebo z jednej konferencie a podobne.
• ISI Web of Knowledge je oficiálna databáza hlavne časopiseckých článkov a citácií, prístupná z fakultnej siete. Trochu menej pohodlná na použitie ako Google Scholar, ale menej chýb v záznamoch.
• Pattern Matching Pointers je zbierka liniek na rôzne konferencie a iné zdroje informácií v oblasti vyhľadávania v texte.
• Konferencie CPM a SPIRE sú dobrým zdrojom novších článkov (linky na zborníky buď cez Pattern Matching Pointers alebo DBLP)

Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň volne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma. Pre niektoré zdroje (napr. ACM, IEEE, LNCS zborníky konferencií a ďalšie) je plný text článku prístupný z fakultnej siete, pričom v niektorých prípadoch si potrebujete v prehliadači nastaviť automatický konfiguračný skript na univerzitný proxy http://www.uniba.sk/proxy.pac. Celý text článku (pdf) sa v mnohých prípadoch dá nájsť na webe (napr. na webstránke autora). V najhoršom prípade, ak neviete zohnať článok, ktorý k projektu alebo prezentácii veľmi potrebujete, kontaktujte ma e-mailom a môžem sa pokúsiť ho zohnať.