haku: @supervisor Alku, Paavo / yhteensä: 39
hakutulos-lista
viite: 16 / 39
« edellinen | seuraava »
Tekijä:Axelson, Erik
Työn nimi:Analysing the Efficiency of Algorithms for Compiling Finite-State Morphologies
Äärellistilaisten morfologioiden käännösalgoritmien tehokkuusanalyysi
Julkaisutyyppi:Diplomityö
Julkaisuvuosi:2010
Sivut:ix + 81      Kieli:   eng
Koulu/Laitos/Osasto:Elektroniikan, tietoliikenteen ja automaation tiedekunta
Oppiaine:Akustiikka ja äänenkäsittelytekniikka   (S-89)
Valvoja:Alku, Paavo
Ohjaaja:Lindén, Krister
Elektroninen julkaisu: http://urn.fi/URN:NBN:fi:aalto-201203131505
OEVS:
Sähköinen arkistokappale on luettavissa Aalto Thesis Databasen kautta.
Ohje
sulje

Digitaalisten opinnäytteiden lukeminen Aalto-yliopiston Harald Herlin -oppimiskeskuksen suljetussa verkossa

Oppimiskeskuksen suljetussa verkossa voi lukea sellaisia digitaalisia ja digitoituja opinnäytteitä, joille ei ole saatu julkaisulupaa avoimessa verkossa.

Oppimiskeskuksen yhteystiedot ja aukioloajat: https://learningcentre.aalto.fi/fi/harald-herlin-oppimiskeskus/

Opinnäytteitä voi lukea Oppimiskeskuksen asiakaskoneilla, joita löytyy kaikista kerroksista.

Kirjautuminen asiakaskoneille

  • Aalto-yliopistolaiset kirjautuvat asiakaskoneille Aalto-tunnuksella ja salasanalla.
  • Muut asiakkaat kirjautuvat asiakaskoneille yhteistunnuksilla.

Opinnäytteen avaaminen

  • Asiakaskoneiden työpöydältä löytyy kuvake:

    Aalto Thesis Database

  • Kuvaketta klikkaamalla pääset hakemaan ja avaamaan etsimäsi opinnäytteen Aaltodoc-tietokannasta. Opinnäytetiedosto löytyy klikkaamalla viitetietojen OEV- tai OEVS-kentän linkkiä.

Opinnäytteen lukeminen

  • Opinnäytettä voi lukea asiakaskoneen ruudulta tai sen voi tulostaa paperille.
  • Opinnäytetiedostoa ei voi tallentaa muistitikulle tai lähettää sähköpostilla.
  • Opinnäytetiedoston sisältöä ei voi kopioida.
  • Opinnäytetiedostoa ei voi muokata.

Opinnäytteen tulostus

  • Opinnäytteen voi tulostaa itselleen henkilökohtaiseen opiskelu- ja tutkimuskäyttöön.
  • Aalto-yliopiston opiskelijat ja henkilökunta voivat tulostaa mustavalkotulosteita Oppimiskeskuksen SecurePrint-laitteille, kun tietokoneelle kirjaudutaan omilla Aalto-tunnuksilla. Väritulostus on mahdollista asiakaspalvelupisteen tulostimelle u90203-psc3. Väritulostaminen on maksullista Aalto-yliopiston opiskelijoille ja henkilökunnalle.
  • Ulkopuoliset asiakkaat voivat tulostaa mustavalko- ja väritulosteita Oppimiskeskuksen asiakaspalvelupisteen tulostimelle u90203-psc3. Tulostaminen on maksullista.
Sijainti:P1 Ark Aalto  639   | Arkisto
Avainsanat:finite-state morphologies
automaton minimisation
Brzozowski's minimisation algorithm
Hopcroft's minimisation algorithm
äärellistilaiset morfologiat
automaatin minimointi
Brzozowskin minimointialgoritmi
Hopcroftin minimointialgoritmi
Tiivistelmä (fin): Äärellistilaiset morfologiat ovat tietokoneohjelmia, jotka mallintavat kielen sanojen rakennetta (morfologiaa) merkkijonopareja sisältävillä tietorakenteilla (äärellistilaisilla transduktoreilla).
Äärellistilaisia morfologioita voidaan käyttää esimerkiksi hakuohjelmissa, jotka löytävät tekstistä kaikki annetun perusmuotoisen sanan esiintymät eri taivutusmuodoissaan.
Äärellistilaiset morfologiat ovat myös hyödyllisiä, kun tekstistä tehdään tilastoja siitä kuinka usein kukin sana esiintyy ja missä taivutusmuodoissa.

Äärellistilaisten morfologioiden rakentaminen on monimutkainen prosessi, johon kuuluu useita tehtäviä, joista yksi on transduktorin minimointi.
Yleisiä minimointialgoritmeja ovat Brzozowskin (BRZ) ja Hopcroftin algoritmit (HOP).
Kirjallisuudessa esiintyy väitteitä, joiden mukaan BRZ:n ja HOP:n välinen ero on merkityksettömän pieni morfologioita käännettäessä.
Kuitenkaan BRZ:n suorituskykyä ei ole järjestelmällisesti testattu tai verrattu HOP:iin missään tutkimuksessa.

Tässä diplomityössä käännettiin HFST-ohjelmistolla kaksi avoimen lähdekoodin morfologiaa, suomelle kirjoitettu OMorFi ja saksalle kirjoitettu Morphisto.
HFST perustuu kahteen avoimen lähdekoodin transduktoriohjelmistopakettiin, SFST:hen ja OpenFst:hen, joista edellinen käyttää BRZ:ia ja jälkimmäinen HOP:ia minimointialgoritmina.

BRZ osoittautui paljon hitaammaksi kuin HOP sekä suomen että saksan morfologioilla.
BRZ:n hitaus oli ilmeistä transduktoreissa, jotka sisälsivät suuren mittakaavan syklisyyttä eli niissä oli siirtymiä, jotka johtivat lopputilojen läheisyydestä alkutilan läheisyyteen.
Tällaisia transduktoreita esiintyy usein morfologioissa, joissa on yhdyssanamekanismi.

Jos HOP:n ja BRZ:n välillä on valittava, edellinen on parempi vaihtoehto minimointi-algoritmiksi.
BRZ on joskus nopeampi kuin HOP, mutta siinä tapauksessa algoritmien ero on melko pieni.
Niissä tapauksissa joissa BRZ on hitaampi kuin HOP, ero on huomattavasti suurempi: BRZ on joskus jopa 50 kertaa hitaampi kuin HOP.
BRZ on kuitenkin paljon helpompi toteuttaa, koska se perustuu kahteen perusoperaatioon, determinisointiin ja reversioon.

Jos HOP:n toteuttaminen on liian vaativa tehtävä, avoimen lähdekoodin transduktorikirjaston kehittäjät voivat käyttää OpenFst:n minimointialgoritmia.
Transduktorit voidaan muuntaa OpenFst:n muotoon, minimoida OpenFst:llä ja muuntaa takaisin alkuperäiseen muotoon.
Tätä ratkaisua on tarkoitus käyttää myös HFST:n tulevissa versioissa.
Tiivistelmä (eng): Finite-state morphologies (FSMs) are computer programs that model the structure of words in a language (morphology) with networks containing a number of string pairs (finite-state transducers).
FSMs can be used e.g. to implement search programs that can find all forms of a word in a document if they are given only the base form.
FSMs are also useful in compiling statistics on a text, i.e. finding out how often a word occurs and in which forms.

Constructing FSMs is a complex process involving many tasks, one of which is transducer minimisation.
Common minimisation algorithms include Brzozowski's (BRZ) and Hopcroft's algorithm (HOP).
There have been claims in the literature that often the difference between BRZ and HOP is insignificant when compiling FSMs.
However, no studies have been carried out where the performance of BRZ would have been systematically tested or compared with HOP.

In this thesis, we compiled two open-source morphologies, OMorFi for Finnish and Morphisto for German, with the HFST software.
HFST is based on two open-source transducer software packages, SFST and OpenFst, the former using BRZ and the latter HOP as a minimisation algorithm.

BRZ turned out to be much slower than HOP both on Finnish and German morphologies.
The slowness of BRZ was evident in transducers that contained large-scale cyclicity, i.e. had transitions leading from the nearness of the final states to the nearness of initial states.
These kinds of transducers often occur in morphologies that have a compounding mechanism.

If a choice must be made between HOP and BRZ, the previous is a better choice for a minimisation algorithm.
BRZ is sometimes faster than HOP, but in that case their difference is quite small.
In the cases where BRZ is slower than HOP, their difference is much bigger, BRZ sometimes being 50 times slower than HOP.
Of course, BRZ is much easier to implement since it uses two basic operations, determinisation and reversion.

If the implementation of HOP is considered too demanding a task, the developers of free-source transducer libraries can use OpenFst's minimisation algorithm.
The transducers can be converted to OpenFst format, minimised with OpenFst and converted back to the original format.
This solution will also be used in future versions of HFST.
ED:2010-08-20
INSSI tietueen numero: 40193
+ lisää koriin
« edellinen | seuraava »
INSSI