Finite-State Transducers in Language and Speech Pr

Finite-StateTransducersinLanguageandSpeechProcessingMehryarMohriAT&TLabs-ResearchFinite-statemachineshavebeenusedinvariousdomainsofnaturallanguageprocessing.Weconsiderheretheuseofatypeoftransducersthatsupportsveryefficientprograms:sequentialtransducers.Werecallclassicaltheoremsandgivenewonescharacterizingsequentialstring-to-stringtransducers.Transducersthatoutputweightsalsoplayanimportantroleinlanguageandspeechprocessing.Wegiveaspecificstudyofstring-to-weighttransducers,includingalgorithmsfordeterminizingandminimizingthesetransducersveryefficiently,andcharacterizationsofthetransducersadmittingdeterminizationandthecorrespondingalgorithms.Someapplicationsofthesealgorithmsinspeechrecognitionaredescribedandillustrated.1.IntroductionFinite-statemachineshavebeenusedinmanyareasofcomputationallinguistics.Theirusecanbejustifiedbybothlinguisticandcomputationalarguments.Linguistically,finiteautomataareconvenientsincetheyallowonetodescribeeasilymostoftherelevantlocalphenomenaencounteredintheempiricalstudyoflanguage.Theyoftenleadtoacompactrepresentationoflexicalrules,oridiomsandclich´es,thatappearsasnaturaltolinguists(Gross,1989).Graphictoolsalsoallowonetovisualizeandmodifyautomata.Thishelpsincorrectingandcompletingagrammar.Othermoregeneralphenomenasuchasparsingcontext-freegrammarscanalsobedealtwithusingfinite-statemachinessuchasRTN’s(Woods,1970).Moreover,theunderlyingmechanismsinmostofthemethodsusedinparsingarerelatedtoautomata.Fromthecomputationalpointofview,theuseoffinite-statemachinesismainlymo-tivatedbyconsiderationsoftimeandspaceefficiency.Timeefficiencyisusuallyachievedbyusingdeterministicautomata.Theoutputofdeterministicmachinesdepends,ingen-erallinearly,onlyontheinputsizeandcanthereforebeconsideredasoptimalfromthispointofview.Spaceefficiencyisachievedwithclassicalminimizationalgorithms(Aho,Hopcroft,andUllman,1974)fordeterministicautomata.Applicationssuchascompilerconstructionhaveshowndeterministicfiniteautomatatobeveryefficientinpractice(Aho,Sethi,andUllman,1986).Finiteautomatanowalsoconstitutearichchapteroftheoreticalcomputerscience(Perrin,1990).Theirrecentapplicationsinnaturallanguageprocessingwhichrangefromthecon-structionoflexicalanalyzers(Silberztein,1993)andthecompilationofmorphologicalandphonologicalrules(KaplanandKay,1994;Karttunen,Kaplan,andZaenen,1992)tospeechprocessing(Mohri,Pereira,andRiley,1996)showtheusefulnessoffinite-statemachinesinmanyareas.Weprovideheretheoreticalandalgorithmicbasesfortheuseandapplicationofthedevicesthatsupportveryefficientprograms:sequentialtransducers.600MountainAvenue,MurrayHill,NJ07974,USA.c1997AssociationforComputationalLinguisticsComputationalLinguisticsVolume23,NumberWeextendtheideaofdeterministicautomatatotransducerswithdeterministicin-put,thatismachinesthatproduceoutputstringsorweightsinadditiontoaccepting(deterministically)input.Thus,wedescribemethodsconsistentwiththeinitialrea-sonsforusingfinite-statemachines,inparticularthetimeefficiencyofdeterministicmachines,andthespaceefficiencyachievablewithnewminimizationalgorithmsforsequentialtransducers.Bothtimeandspaceconcernsareimportantwhendealingwithlanguage.Indeed,oneofthetrendswhichclearlycomeoutofthenewstudiesoflanguageisalargeincreaseinthesizeofdata.Lexicalapproacheshaveshowntobethemostappropriateinmanyareasofcomputationallinguisticsrangingfromlarge-scaledictionariesinmorphologytolargelexicalgrammarsinsyntax.Theeffectofthesizeincreaseontimeandspaceefficiencyisprobablythemaincomputationalproblemoneneedstofaceinlanguageprocessing.Theuseoffinite-statemachinesinnaturallanguageprocessingiscertainlynotnew.Limitationsofthecorrespondingtechniques,however,areveryoftenpointedoutmorethantheiradvantages.Thereasonforthatisprobablythatrecentworkinthisfieldarenotyetdescribedincomputersciencetextbooks.Sequentialfinite-statetransducersarenowusedinallareasofcomputationallinguistics.Inthefollowingwegiveanextendeddescriptionofthesedevices.Wefirstconsiderthecaseofstring-to-stringtransducers.Thesetransducershavebeensuccessfullyusedintherepresentationoflarge-scaledictionaries,computationalmorphology,andlocalgrammarsandsyntax.Wedescribethetheoreticalbasesfortheuseofthesetransduc-ers.Inparticular,werecallclassicaltheoremsandgivenewonescharacterizingthesetransducers.Wethenconsiderthecaseofsequentialstring-to-weighttransducers.Thesetrans-ducersappearasveryinterestinginspeechprocessing.Languagemodels,phonelatticesandwordlatticesareamongtheobjectsthatcanberepresentedbythesetransducers.Wegivenewtheoremsextendingthecharacterizationsknownforusualtransducerstothesetransducers.Wedefineanalgorithmfordeterminizingstring-to-weighttransduc-ers.Webothcharacterizetheunambiguoustransducersadmittingdeterminizationanddescribeanalgorithmtotestdeterminizability.Wealsogiveanalgorithmtominimizesequentialtransducerswhichhasacomplexityequivalenttothatofclassicalautomataminimizationandwhichisveryefficientinpractice.Undercertainrestrictions,themin-imizationofsequentialstring-to-weighttransducerscanalsobeperformedusingthedeterminizationalgorithm.Wedescribethecorrespondingalgorithmandgivet