search query: @supervisor Alku, Paavo / total: 39
results-list
reference: 16 / 39
« previous | next »
Author:Axelson, Erik
Title:Analysing the Efficiency of Algorithms for Compiling Finite-State Morphologies
Äärellistilaisten morfologioiden käännösalgoritmien tehokkuusanalyysi
Publication type:Master's thesis
Publication year:2010
Pages:ix + 81      Language:   eng
Department/School:Elektroniikan, tietoliikenteen ja automaation tiedekunta
Main subject:Akustiikka ja äänenkäsittelytekniikka   (S-89)
Supervisor:Alku, Paavo
Instructor:Lindén, Krister
Electronic version URL: http://urn.fi/URN:NBN:fi:aalto-201203131505
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions
close

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto  639   | Archive
Keywords:finite-state morphologies
automaton minimisation
Brzozowski's minimisation algorithm
Hopcroft's minimisation algorithm
äärellistilaiset morfologiat
automaatin minimointi
Brzozowskin minimointialgoritmi
Hopcroftin minimointialgoritmi
Abstract (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.
Abstract (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.
ED:2010-08-20
INSSI record number: 40193
+ add basket
« previous | next »
INSSI