Pisin yhteinen jatke -ongelman ratkaiseminen koodaavan tietorakenteen avulla

Show full item record



Permalink

http://urn.fi/URN:NBN:fi-fe201902286664
Title: Pisin yhteinen jatke -ongelman ratkaiseminen koodaavan tietorakenteen avulla
Author: Määttä, Mikko
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2019
Language: fin
URI: http://urn.fi/URN:NBN:fi-fe201902286664
http://hdl.handle.net/10138/299745
Thesis level: master's thesis
Discipline: Tietojenkäsittelytiede
Abstract: 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.


Files in this item

Total number of downloads: Loading...

Files Size Format View
Maatta_Mikko_Pro_gradu_2018.pdf 592.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record