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í:

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