Tento problém jsem řešil v rámci semestrální práce na algoritmizaci. V článku se dozvíte, jaké jsou možnosti, k čemu je to dobré a také zde naleznete funkční multiplatformní program.
- Nastínění problému
- Užití
- Řešení
- Program
Legenda okolo semestrální práce
Nejdříve trochu osobní omáčky. Pokud vás zajímá hlavně ten program, najdete ho níže.
Zadání jsme dostali poměrně brzy, pár týdnu po zahájení semestru. Většina lidí byla nadšena, protože nám bylo oznámeno, že nebudeme na rozdíl od jiných skupin psát písemnou práci. Kromě docházky tak mělo veškeré hodnocení ze cvičení vycházet právě ze semestrální práce. Měla být uspořádána soutěž o nejrychlejší algoritmus, problém nevypadal na první pohled zvlášť složitě, žádná písemka - co víc si přát?
O nějaký ten týden později jsem se trochu podíval, o co vlastně jde a začínalo mi být jasné, že to taková legrace nebude. Zjistil jsem, že složitost algoritmu hrubá síla by byla (n^3)/2. Takže při předpokladu, že za jednu vteřinu procesor vykoná 1*10^9 operací, celé by to pro naše milionové n trvalo více jak 15 let. Většina lidí ale byla stále v klidu, protože žila ve stínu prvního pohledu na věc.
Během zimních prázdnin se už situace začala hrotit. Na ICQ či Facebooku jsem dostal od spolužáků ne-jednu nervózní zprávu ohledně této práce. Sám jsem nad tím strávil dva dny, kdy mělo mé úsilí nulový výsledek a asi je vám jasné, jaké to mělo účinky na psychiku.
Zadání aneb co bylo cílem
Zkrácená verze je uvedena už v nadpisu článku: nalézt nejčastější výskyt nejdelšího řetězce. Trochu to rozvedu.
Prohledávaný soubor měl velikost 1 MB (tedy milion znaků) a opakované řetězce se mohly překrývat (viz. příklady níže).
Hodnocení (Testovací procesor byl jednojádrový 1,2Ghz.):
- * A. END TIME <=3 sec SUPERLIGA
- * B. END TIME <=15 sec EXTRALIGA
- * C. END TIME <=60 sec LIGA
- * D. END TIME <=300 sec DIVIZE
- * E. END TIME <=600 sec ZABARI
- * F. END TIME > 600 sec PUKAVCI (bez šance na zápočet)
Ty písmena jsou trochu zavádějící, protože známka (tedy písmeno) se dává až u zkoušky. Za toho se dostávaly body, které se pak sčítaly se zkouškovou písemkou a hlavním cílem bylo samozřejmě dostat vůbec zápočet (povolení jít ke zkoušce).
Příklady pro různé vstupní řetězce:
Výsledek pro BBBB:
BBB 1 2
Proč? Protože v řetězci je nejdelší opakující se sekvence znaků BBB a to na pozicích 1 a 2 (číslování od 1).
BBBB
BBBB
Výsledek pro ANANAS:
ANA 1 3
Proč?
ANANAS
ANANAS
Výsledek pro OKYOKZOK.HEHEH:
HEH 10 12
Je zde sice také řetězec OK, který se opakuje 3x, ale my hledáme ty opakující se, které jsou nejdelší. Tzn. neexistuje už žádný delší opakující se.
MAMAYMAMAZMAMAITATALTATAETATA:
MAMA: 1 6 11
TATA: 16 21 26
Pokud se v řetězci nachází hledaných nejdelších podřetězců více, nalezneme je všechny.
K čemu je nejdelší společný podřetězec dobrý?
- Nejvíce se s tímto problémem potýkají pravděpodobně genetici. Neznám podrobnosti, ale znát tento podřetězec a vědět, jestli ho už nemají v databázi, se jim hodí.
- Kvalitní hesla: heslo je tím lepší, čím větší jeho část se v něm opakuje (ideálně se tedy neopakuje žádný znak).
- Komprimace. Opakované části řetězců lze přenášet pouze jednou a zbytek nahradit odkazy.
- Pravděpodobně by se našly další uplatnění.
Jak problém řešit?
Řešení No. 1 : Suffixový strom
To byla první věc, ke které jsem se dogooglil a po prvním nálezu jsem měl radost, že tím semestrální práci vyřeším snadno a rychle. Brzy jsem ale zjistil, že sufixový strom je přecijen trochu vyšší dívčí a asi bych ho nedal dohromady nebo bych u toho přišel o poslední zbytky nervů.
Suffixový strom je datová struktura, ve které už onen opakující se řetězec naleznete poměrně snadno. Je několik způsobů, jak jej postavit, přičemž nejpomalejší algoritmus vede ke kubické složitosti, takže by si náročný hledač musel na svůj výsledek opět počkat několik let.
Není tomu však moc dlouho (1995), kdy jistý pan Ukkonen přišel s lineárním algoritmem, což je naprosto úžasný. Každému je asi jasné, že do lineárního algoritmu už můžete hodit sakra velké n a pořád se dočkat výsledku v poměrně přijatelném čase.
O Sufixových stromech se toho dá na internetu najít hodně, ale kromě několika prezentací z vysokých škol, spíše anglické materiály. I to ztěžuje pochopení této struktury. Učit se nový algoritmus, aplikovat ho v cizím programovacím jazyce a číst si podklady v cizím jazyce není nic příjemného. Velmi dobrý web, kde naleznete i JS generátor stromu, naleznete tady. Další kvalitní článek o suffixových stromech tady.
Mimochodem, někteří moji spolužáci semestrální práci přes sufixové stromy řešili. Někomu to ale vyšlo o dost pomaleji, než moje řešení. Takže suffix bych viděl jako nejlepší řešení, ale musíte ho napsat opravdu době. Jeden člověk ho postavil tím způsobem, že přepsal JS kód z výše zmíněného webu do Javy. Sám se přiznal, že svému kódu moc nerozuměl.
Mé řešení postavené na hashovaní řetězců
Přiznávám se, že původně jsem chtěl dojít k cíli poněkud jinak, ale jádro zůstává stejné. Řekl jsem si, že celý jeden rozměr ve složitosti hrubého algoritmu představuje porovnávání jednotlivých znaků mezi sebou a řetězce vedle sebe se navíc liší vždy jen o jeden znak. Tedy hodně zbytečné práce navíc.
Našel jsem tedy hashovací funkci, která měla tu vlastnost, že když mám hash řetězce na pozici n, pak hash na pozici n+1 jsem schopen dopočítat odečtením prvního a přičtením dalšího znaku (samozřejmě to není až tak triviální, ale co se týče výpočetního výkonu, vyjde to skoro na stejno). Díky tomuto jsem schopen udělat hashe řetězců pro jednu délku podřetězce v lineárním čase.
Původně jsem chtěl udělat modulo těchto hashů a použít je jako klíče v poli, jejichž hodnotou by byl počet výskytů. Potom už bych jenom prošel toto pole a našel prvek s největším číslem.
Ukázalo se však, že u velkého počtu hashovaných řetězců se najdou takové, které mají stejný hash, ale ve skutečnosti stejné nejsou. Abych se tohoto nešvaru zbavil, musel bych používat velká prvočísla a to už by mi zase přetékaly proměnné. Co bylo ale hlavní, ty opravdu stejné řetězce měly hash také stejný, takže jsem se rozhodl u tohoto řešení zůstat, jenom ho trošku zpomalit o odfiltrování těch špatných výsledků.
Ale jak na to? Mám pole hashů, některé mohou být stejné, ale jenom vybrání pouze těch stejných by mi zabralo kvadratický čas. Rozhodl jsem se použít, mým bývalým spolužákem opěvovaný, HeapSort. Ten má složitost n*log(n) a jak známo, logaritmus je docela pěkně (pomalu) rostoucí funkce (n*log(n) už je znatelně horší, ale pořád je to přijatelné). Setříděné pole se už dalo prostým jediným projitím, testováním sousedních prvku a hrubým zkoušením shodných hashů analyzovat do finální podoby.
Lžu! Resp. není tak úplně pravda, že eliminace jedinečných výskytů hashů by mi zabrala kvadratický čas. Článek jsem psal už před nějakým tím pátkem a teď jsem si uvědomil, že by to šlo i lineárně. Buď by se použily hashe jako klíče v poli (Tady bych narazil na problém příliš velkých hashů a nutnosti vytvoření příliš velkého pole. Možná by to pomohlo vyřešit vymodulením (%) hashů, ale nevím, jestli by to nevytvořilo další duplicity.
Nebo by se to dalo lineárně vyřešit pomocí dvourozměrného pole.
Možná si říkáte, že mé řešení je slepené z tolika částí a nakonec stejně používám hrubou sílu, takže to nemůže být nijak rychlé. Navíc je třeba si uvědomit, že vše výše zmíněné muselo proběhnout pro každou délku možného výsledného řetězce!
Inu, rychlé je. Všechny použité části mají velmi příjemnou složitost, jakýkoliv kvadratický či dokonce kubický algoritmus zlehka zastíní n či n^2 lineárních algoritmů. Co se týče té hrubé síly na konci, je aplikována na mnohem méně řetězců (a také mnohem kratších).
Dále jsme v semestrální práci mohli využít poznatků genetiků. Konkrétně toho, že nejdelší, nejčastěji se opakující řetězec nebude delší než 30 znaků. Celý výše zmíněný algoritmus jsem tedy nemusel použít n* ale pouze párkrát. Zavedl jsem však binární půlení intervalu, díky němuž dostanu výsledek do několika vteřin i bez zmíněného zvýhodnění:
START hledani, input size=1000000
Retezec delky 999999 NENALEZEN. Pokracuji delkou 500000
Retezec delky 500000 NENALEZEN. Pokracuji delkou 250001
Retezec delky 250001 NENALEZEN. Pokracuji delkou 125002
Retezec delky 125002 NENALEZEN. Pokracuji delkou 62503
Retezec delky 62503 NENALEZEN. Pokracuji delkou 31254
Retezec delky 31254 NENALEZEN. Pokracuji delkou 15630
Retezec delky 15630 NENALEZEN. Pokracuji delkou 7818
Retezec delky 7818 NENALEZEN. Pokracuji delkou 3912
Retezec delky 3912 NENALEZEN. Pokracuji delkou 1959
Retezec delky 1959 NENALEZEN. Pokracuji delkou 983
Retezec delky 983 NENALEZEN. Pokracuji delkou 495
Retezec delky 495 NENALEZEN. Pokracuji delkou 251
Retezec delky 251 NENALEZEN. Pokracuji delkou 129
Retezec delky 129 NENALEZEN. Pokracuji delkou 68
Retezec delky 68 NENALEZEN. Pokracuji delkou 38
Retezec delky 38 NENALEZEN. Pokracuji delkou 23
Retezec delky 23 NENALEZEN. Pokracuji delkou 16
Retezec delky 16 NALEZEN. Zkousim delku 19
Retezec delky 19 NALEZEN. Zkousim delku 20
Retezec delky 20 NENALEZEN. Pokracuji delkou 19
Retezec delky 19 NALEZEN.
Ve zdrojovem textu o 1000000 znaku, byly nalezeny nejdelsi retezce o delce 19 (bylo hledano od delky 999999), ktere se vyskytovaly 2*.
POZICE RETEZCU JSOU CISLOVANY OD 1.
ggacgtacttgcgagtgca: 776970 795656
acttaggaggcagtgagcg: 700769 877222
gtactgggtatgaatgcca: 45605 737506
END TIME=13087
Jiné řešení
Teď už bych tento problém řešil patrně ještě trochu jinak. Nicméně základ (hash řetězců), by byl stejný. Dá se čekat, že tento článek budou nalézat studenti ČVUT, kteří budou také řešit semestrální práci. Z toho důvodu sem neumisťuji zdrojové kódy. Je to pro vaše dobro. Má implementace určitě není ideální a bude lepší, když si najdete vlastní řešení nebo alespoň vlastní implementaci mého algoritmu, který popisuji výše.
Další možnost by mohla spočívat v nalezení největší četnosti jednoho znaku. Potom by se hledala největší četnost znaku, který následuje ten nejčastější z předchozího hledání a takto by se nabalovalo dál a dál, dokud jsou alespoň dva výsledky.
Je to pouze nápad (a není můj). Nevím, jak je to těžké na realizaci (už jsem se poučil, že co se zdá na první pohled jednoduché, může být nakonec docela složité) ani si nejsem jist časovou složitostí, ale jeví se to pěkně. (Na druhou stranu se také zdá, že se dá pro takový postup nalézt rekurzivní algoritmus a ty nemívají moc dobrou efektivitu.)
Ještě jiné řešení
Pravděpodobně se najdou ještě další zajímavá řešení. Jedním je možná Knuth–Morris–Pratt algorithm, ale nevím to jistě - nezkoumal jsem, nezkoušel jsem.
Multiplatformní program v Jave
Asymptotická složitost algoritmu použitého v mém programu je n*log(n).
Stažení:
- Genom.zip (toto vám bude ve většině případů stačit)
- Genom-Xmx300m.zip (viz. poslední odstavec)
Ovládání a další informace
Program spustíte přes příkazovou řádku. Nejjednodušší je vstoupit do složky, kde máte rozbalený výše odkazovaný archiv (příkaz cd) a zavoláte program takto:
java Genom (eventuelně java -Xmx300m Genom-Xmx300m)
Pokud vám bude program vyhazovat vájimky, ujistěte se, že jste si přečetli, co po vás chtěl a nezadali jste mu něco, na základě svých předpokladů. Berte v úvahu, že uživatelské rozhraní je velmi strohé, protože pro účely semestrální práce do předmětu algoritmizace nebylo vůbec třeba. Stejně tak nejsou odchycené výjimky. Šlo pouze o rychlost algoritmu.
Soubor s třídou nesmíte přejmenovat.
Pokud budete hledat podřetězce, kde se dá očekávat velmi velký počet výskytů, je třeba použít větší pole výsledků a také program spouštět s přidělením více paměti (nemusí třeba ani tak jít o konečný výsledek, ale program v nějaké mezifázi to místo potřebuje). Pokud tedy dochází k: ArrayIndexOutOfBoundsException (Nastane např. když budete prohledávat soubor DNA.txt a necháte si vyhledat opakující se řetězce délky 10), použijte druhou verzi programu a spouštějte jej takto: java -Xmx300m Genom-Xmx300m
Wow! Zajímavé ... teď abych litoval, že jsem na ČVUT nakonec nešel
Na druhou stranu u nás na FIT VUT jsme měli hned čtyři projekty na semestr, ikdyž ne tak složité a především ne tak zajímavé.
A je škoda, že jsme neměli například podobné zadání, protože takhle se nad problémem nezamyslím tak hluboce jako z donucení (například z donucení zápichem) . Tyhle rozbory problémů mě ale vždycky zajímají, hlavně když je to nějaký "lidský" problém (tím myslím pro mě relativně zvládnutelný) ... nevím jak je to u vás na škole, ale u nás se nikdo s řešením projektů nechlubí (postupy, kód,...) a podle mě je to škoda ... no co, zkouším zavést novou éru a podobně jako ty házím své dílka na web, třeba to někoho probudí
A závěrem jestli jsem správně pochopil a END TIME je v milisekundách, tak gratuluju k nádhernému výsledku
(neprozradili vám, s jakým algoritmem by byla šance na superligu?)
danek<zavináč>antonindanekcz
Koukám, že pro zápočty máte stejný metafory. Dokonce jsme přišli se „zásun“ pro zápočet, tak jsem si říkal, že zkouška by měla být „orgasmus“.
Co se týče zveřejňování školních prací, lidi to opravdu moc nedělají. Já jsem to tak dělal už na střední a taky mě publikování na internetu motivovalo k větší snaze a dalo to té práci větší smysl. Každopádně je to daleko lepší přístup než někoho, kdo to bere jako nutné zlo k ničemu - rychle nějak udělat a pak zahodit. Pak se asi dá chápat, že to ten člověk bere jako ztrátu času, protože to opravdu ztráta času je.
Ano, ten čas je v milisekundách a jsem celkem spokojen. S využitím zmíněného limitu řetězce najdu na mém dual core procesoru dokonce za 3,5 vteřiny, ale na testovacím procesoru to vyšlo na cca 15 vteřin (dostal jsem ze semestrálky B).
Jak to udělat nejefektivněji, jsme si neříkali, protože na posledním cvičení bylo ještě hodně lidí, co semestrálku vůbec neodevzdalo. Ale mohl bych mu napsat mail, ostatně nám sám cvičící nabízel, že nám k tomu dá info. Jinak bych ještě dodal, že do toho Ačka se jeden člověk vešel (a možná že k dnešnímu datu je těch lidí i víc, to už nezjistim).
Každopádně ten Ukkonenův suffix by to měl do 3 vteřin zvládnout v pohodě. Jenom je problém, že vyžaduje, aby funkce uměla vrátit dva parametry a to Java (která nemá ukazatele ve významu adres na paměť) neumí. Tedy umí, ale musí se využít objektového programování, které má určitou režii a to to zase dost zpomalí. Jak píšu v článku, někteří spolužáci přepisovali JS kód Ukkonena a vyšlo jim to pomaleji než mně.
michaelf.ms<zavináč>gmailcom
A já mám zase o kapku větší motivaci, když to vidím... jdu se učit matiku k přijímačkám :). Hádám, že jsi byl na svoje dílo podstatně hrdej, když se dostalo do release fáze :).
danek<zavináč>antonindanekcz
Popravdě v tomhle případě jsem byl spíš rád, když jsem to měl za sebou a už nepřišel žádný e-mail s bugama.
Ale jo hrdej jsem byl taky, zvlášť když jsme se o tom bavili se spolužákama a porovnávali rychlosti.
Ten napad s binarnim pulenim je zajimavy.
Vyuzit KMP jsem puvodne chtel taky, ale je tam problem s tim, ze neznas retezec, ktery mas hledat, proto jsem sel nakonec jinou cestou.
danek<zavináč>antonindanekcz
Jasně.
Jinak s tou hashovací funkcí mi pomohl tenhle Matfyzáckej web: http://ksp.mff.cuni.cz/ Píšu to, protože vim, že si chodil na Matfyz, tak jestli to třeba neznáš.
nothinkelse<zavináč>gmailcom
Nazdar, no tak pozrel som sa na tie stromy prípon. zohnal som si aj anglickú literatúru ale myslím si že je to príliš zložité. Literatúra je písaná pre mna nezrozumitlne. Takže hľadám iný spôsob, zišla by sa mi nejaká rada. Nejaké linky o tom hashovaní? Nejaké veci čo by sa mohli zísť? Dakujem
Osobně se domívám, že nejjednodušší řešení tohoto problému je přes suffix array.Mají sice náročnost n*log n, což je více než suffix tree, ale jsou několikanásobně pohodlnější na napsání a pokud zvolíte vhodnou reprezentaci dat pak se pod 3 sekundy každopádně dostanete.Největší problém, který asi budete řešit je výpis toho všeho :-D