Programmeerimisülesanded: Tekstialgoritmid I, Kevad 2003

Programmeerimisülesanded ja töötulemuste raport tuleb koostada grupitööna (maksimum kuni 3-liikmelised grupid) või individuaalselt. Grupis tuleb pidada märkmikku aja kasutuse kohta - kes, millal, kui kaua kasutas aega mille tegemiseks. Lõpuks tuleks ka ühiselt jõuda raportini, kaua võttis töö aega eri osade lõikes.

Töö tuleb vormistada koos ülesandepüstituse, lahenduse kirjelduse ning algoritmide (sooritus)kiiruse hindamise/võrdlusega. See raport peaks olema kompaktne, ca 10 lehekülje pikkune viisakas vormistus. Vormistuse juurde käib ka tarkvara esitamine andmekandjal või meili teel. Tehtud tööd tahaks koguda kokku ja "riputada" veebi.

Programmeerimiskeeltest: Sama teema võib võtta ka eri inimeste poolt tingimusel et nad programmeerivad eri keeltes. Näiteks - C/C++, Java, Delphi, perl.

Programmeerimisel võiks soovitada nn. Extreme Programming meetodit kus korraga istub kaks inimest sama programmi kirjutamas ning suuremas rühmas tehakse ühiseid "code review"-sid.

Eesmärk ei ole mitte niivõrd absoluutselt lollikindla programmi tegemine vaid võimalikult täpselt seatud piirangutega programmi tegemine, mis peab saama ette täpsed sisendandmed. Ärge raisake aega mitte kasutajaliidesele vaid algoritmilistele küsimustele. Mida lühemad on allolevaid ülesandeid lahendavad programmid, seda parem. Kuid - see ei ole mitte 'Obfuscated C contest'. Algoritmi tuum peab olema arusaadavalt esitatud. Nii dokumendis kui ka koodis endas.

Allolevad teemad annavad ette valdkonna, kusjuures mõni on täpsemini ja mõni ebatäpsemalt sõnastatud. Iseseisva uurimistöö puhul tuleb alati esitada kriitiliselt oma isiklik ülesandepüstitus. St, formuleerida eeldused, võimalikud probleemid ja huvitavad küsimused, ning neile huvitavatele küsimustele siis lahendusi otsida.

Näidisküsimused, mida hinnata projekti käigus

Programmeerimisprojektil on tähtis osa praeguses kursuses. Selle eesmärk pole ainult programmi kirjutamine, vaid pigem lahenduse võrdlemine.

Näiteks - miks kasutada sufiksitabelit, kui on olemas ka teisi algoritme? Ehk - milline on reaalne ajaline võit mille saame kasutades sufiksitabeleid.

Hinnata:

a) tabeli konstrueerimisele minevat aega

b) mälumahtu

c) otsimise aega ning võrduste/kettapöördumiste arvu

d) keerukamate päringute (Näiteks! 2 sõna korraga) otsimise aega jne.

Seda suhtes:

A) faili suuruse kasv (100 KB -> 1MB -> 10MB -> 100MB)

B) tähestiku suurus (näiteks 4 vs 20 vs 40+ tähte)

C) faili keerukus (juhuslik vs. loomulik tekst vs väga suurte kordustega tekst)

St, peamine rõhk on algoritmi empiirilisel hindamisel. Võrrelda tuleks alati vähemalt mõne lihtsama, nt. jõumeetodiga, et näidata tegelikku kiiruse efekti. Lugege kindlasti veidi selle pilguga ka David Johnsoni artiklit!

Viiteid

Tähtaeg

Programmeerimistööde esitamise lõpptähtaeg on nädal enne eksamit.

Teemad

  1. Otsides tekstifailist on tavaliselt vaja teada reanumbrit. Kui kasutada kiiret otsingut nagu näiteks BMHHS siis hüpatakse aga märkidest (s.h. reavahetus) üle. Ehita tekstifailile indeks mis lubaks arvutada mustri esinemise positsiooni järgi tekstifaili sees selle esinemise rea järjekorranumber (positsioonid 1345-1398 = rida 56). Indeksist võib otsida näiteks kahendotsimisega. Võrdle kas nii on võimalik kiirendada. (Vrdl grep ja grep -n, proovi kiirendada viimast).

  2. Moodusta etteantud tekstifailidele pöördindeks kus igale sõnale igas dokumendis koostatakse loetelu mis positsioonides sõna esineb. 
    auto: d1:32 d1:38 d45:78
ava:  d1:31 d48:76
...
    Eesmärk: tee väike tööriist mis laseks otsida "sõna1 W/4 sõna2", ehk sõna1 ja sõna2 samas dokumendis kuid mitte kaugemal kui 4 sõna kaugusel üksteisest.

    Vihje: soovitavalt perl'is, indeksi võib ehitada kas MySQL peale või salvestada Storable.pm mooduli abil.

  3. Sufiksitabeli (suffix array) konstrueerimine etteantud failist. Kasutada võib mõnda lihtsustatud varianti, näiteks kasutades C sort() funktsiooni. Realiseeri alamstringi otsimine ühe- või kahekaupa korraga (parameeter - esinemised mitte kaugemal kui X baiti üksteisest...).
    Viiteid kust saab võrgust abi: Töö autorid:

  4. Sufiksipuu (või trie, on lihtsam) konstrueerimine WOTD meetodil (Write-Only-Top-Down) eesmärgiga lugeda kokku kõik etteantud pikkusega alamsõned ja kui mitu korda need esinevad teksti(faili)s.

  5. Arendada edasi algoritmide testkeskkonda ja süstematiseerida kursuse käigus tehtud täpse ja ligikaudse otsimise algoritme ühtsesse "Tartu Ülikooli String-algorithms-benchmark" süsteemi.

  6. Shift-OR tüüpi algoritmid

  7. Tutvuda Bielefeldi ülikoolis välja töötatud Haskelli baasil tehtud dünaamilise programmeerimise ülesannete algebralise meetodi paketiga ja realiseerida/dokumenteerida selles keeles paar näidisülesannet. (ma pole seda ise uurinud - sobib funktsionaalprogrammeerimist juba oskavale?) http://bibiserv.techfak.uni-bielefeld.de/adp/

  8. Kirjutada BMHHS algoritmil baseeruv abivahend mis reaalajas lubaks otsida tipitavale sõnale vasteid failist. Failiks võib võtta UNIX-ites oleva words faili (/usr/dict/words, /usr/share/dict/words) (Vrdl. auto-complement kuid nii sõnade algusest kui ka keskelt)

    Kuna tegu on graafilise kasutajaliidesega siis võiks see olla realiseeritud kas Delphis/Kylixis või Javas.

    • Priit Salumaa, Ireen Meho, Jaanus Jaeger
    • Markus Tarmak, Timo Õunmaa, Mikk Kard
    • Valmis tööd

  9. Ise valitud teema: Boyer-Moore vs. AC

  10. Ise valitud teema: Teisenduskaugus kasutades funktsionaalset programmeerimist

    Pakkimisalgoritmid

  11. Burrows-Wheeler teisendusel põhinev pakkimismeetod Lisamaterjale:
    • Priit Kervi, Aleksandr Grebennik, Oleg Petshonkin
    • Valmis tööd

    Andmekaevanduse tulemuste süstematiseerimine

    Andmekaevanduses (data mining) on tüüpiline olukord, et tuvastatakse palju mustreid mis on iseloomulikud antud andmestikele. Kuna osa mustreid on omavahel saranased siis tuleb neid kuidagi mõistlikult grupeerida, et inimestele neid paremini saaks esitada. Klasterdamine (rühmitamine) aitab vähendada väljundi suurust. Selleks et klasterdada on vaja osata hinnata mustrite vahelist (teisendus)kaugust.

  12. Kirjutada programm(id) kõikide etteantud stringide paaride vaheliste teisenduskauguste arvutamiseks. Võrrelda saab tavalise dünaamilise programmeerimise ja diagonaali meetodi kiirusi. Lisaks saab võrrelda erinevaid kauguste mõõte - lubatud ainult teisendused, või ka eemaldamine lisamine. Lubada lisada kaale igale tehtele (eemldamine/lisamine 2, teisendus 1).

  13. Kahe mustri vahelise sarnasuse arvutamine olukorras kus mustri positsioonid võivad sisaldada rühmasümboleid: (AT.GC.TA vs. ACGGTC[TG]A). Võrdlus nii, et kaks mustrit tuleb sobitada täis pikkuses. Teiseks teha kahe mustri sobitamine nii, et otsida pikimat kattuvust nende vahel.

    Et võrrelda täherühmi omavahel tuleks kasutada mingit tõenäosuse hindamise kriteeriumit. Lihtsuse mõttes teha DNA tähestikus, eeldada iga tähe tõenäosuseks 0.25. Iga rühma g = { c1, .. cn } tõenäosus on 1 miinus rühma kuuluvate tähtede tõenäosuste summa. Näiteks P([AT]) = 0.5 ja P([ACTG])=0. Kahe rühma võrdlemise tulemus saadakse nende tõenäosuste korrutamisega omavahel ning lisaks veel ühisosaga normeeritult. Kui ühisosa on tühi, siis on kordaja 0, kui 1, siis 0.25, kui 2, siis 0.5, jne. Võite pakkuda oma kriteeriume veel lisaks.

  14. Kahe PSSM/PWM vahelise redigeerimiskauguse arvutamine - võrdle eelmisega, kuid siin on iga märgi jaoks igas positsioonis etteantud reaalarvuline skoor. Mõtle välja mõni mõistlik kauguse mõõt, näiteks informatsiooni sisaldusel pohinev.
    • Meelis Kull, Kristo Käärmann, Leopold Parts, (Hedi Peterson)
    • Valmis tööd
Jaak Vilo, 2003