Browsing by Author "Määttä, Mikko"

Pisin yhteinen jatke -ongelmassa tarkoituksena on selvittää tietorakenteen avulla merkkijonon kahden loppuosan pisimmän yhteisen alkuosan pituus. Ongelman nopea ratkaiseminen on tärkeää esimerkiksi monissa merkkijonoalgoritmeissa. Lisäksi tiedon määrän jatkuva kasvu lisää tarvetta minimoida tietorakenteen viemä tila. Tutkielmassa käsitellään pisin yhteinen jatke -ongelman ratkaisemista koodaavalla tietorakenteella. Tällöin alkuperäiseen merkkijonoon päästään käsiksi vain ennalta määriteltyjen kyselyjen avulla, eikä merkkijonoa tarvita kyselyissä. Tyypillisesti koodaava tietorakenne vie vähemmän tilaa ja sisältää vähemmän informaatiota kuin alkuperäinen tieto. Taustan antamiseksi käsitellään ensin pisin yhteinen jatke -ongelman perinteisiä ratkaisuja. Sen jälkeen tarkastellaan tiedon tilavaativuutta informaatioteoreettisen entropian avulla, mikä luo perustan arvioida tietorakenteiden tilavaativuuden optimaalisuutta ja aika - tila-vaihtokauppaa. Lisäksi annetaan esimerkkejä koodaavan tietorakenteen käytöstä ja ongelman tilaa säästävistä ratkaisuista. Yksityiskohtaisesti käsitellään pisin yhteinen jatke -ongelman ratkaisua, jossa käytetään koodaavaa tietorakennetta. Ratkaisussa on kaksi pääasiallista osaa, joiden avulla vastaus selvitetään. Toteutuksessa käytetään hyväksi useita tietorakenteita, esimerkiksi loppuosapuuta, de Bruijn -verkon muunnosta ja virittävää puuta. Algoritmin ja tietorakenteen toteutuksen lisäksi tarkastellaan tietorakenteen tilavaativuuden ylärajan parantamista ja puiden esittämistä toteutuksessa tilaa säästäen. Keskeiset johtopäätökset ovat seuraavat. Useita kyselyjä tehtäessä pisin yhteinen jatke -ongelma voi kannattaa ratkaista tietorakenteen avulla. Tiedon määrän kasvun ja tietorakenteiden kehityksen seurauksena ongelmaan on viime vuosina esitetty tilaa säästäviä ratkaisuja. Niissä optimoidaan aika- ja tilavaativuutta monin eri tavoin. Ongelmaan on olemassa muun muassa vakioaikainen, koodaavaa tietorakennetta hyödyntävä ratkaisu, jolla voidaan päästä alilineaariseen tilavaativuuteen ilman alkuperäisen merkkijonon korkeaa tiivistyvyyttä. Viimeaikaisten ratkaisujen suorituskyvystä sovelluksissa ei ole vertailutietoa.