欢迎来到天天文库
浏览记录
ID:39814213
大小:2.39 MB
页数:396页
时间:2019-07-11
《text_algorithms 》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、Chapter1321/7/971.Introduction1.1.TextsandtheirprocessingOneofthesimplestandnaturaltypesofinformationrepresentationisbymeansofwrittentexts.Datatobeprocessedoftendoesnotdecomposeintoindependentrecords.Thistypeofdataischaracterizedbythefactthatitcanbewrittendownasalongsequenceo
2、fcharacters.Suchlinearsequenceiscalledatext.Thetextsarecentralin"wordprocessing"systems,whichprovidefacilitiesforthemanipulationoftexts.Suchsystemsusuallyprocessobjectswhicharequitelarge.Forexample,thisbookcontainsprobablymorethanamillioncharacters.Textalgorithmsoccurinmanyar
3、easofscienceandinformationprocessing.Manytexteditorsandprogramminglanguageshavefacilitiesforprocessingtexts.Inbiology,textalgorithmsariseinthestudyofmolecularsequences.Thecomplexityoftextalgorithmsisalsooneofthecentralandmoststudiedproblemsintheoreticalcomputerscience.Itcould
4、besaidthatitisthedomainwherethepracticeandtheoryareveryclosetogether.Thebasictextualproblemistheproblemcalledpatternmatching.Itisusedtoaccessinformationandprobablymanycomputersaresolvinginthismomentthisproblemasafrequentlyusedoperationinsomeapplicationsystem.Pattern-matchingi
5、scomparableinthissensetosorting,ortobasicarithmeticoperations.ConsidertheproblemofareaderoftheFrenchdictionary"GrandLarousse",whowantsallentriesrelatedtotheword"Marie-Curie-Sklodowska".Thisisanexampleofapatternmatchingproblem,orstring-matching.Inthiscase,theword"Marie-Curie-S
6、klodowska"isthepattern.Generallywemaywanttofindastringcalledapatternoflengthminsideatextoflengthnwherenisgreaterthanm.Thepatterncanbedescribedinamorecomplexwaytodenoteasetofstringsandnotonlyasingleword.Inmanycasesmisverylarge.Ingeneticsthepatterncancorrespondtoagenomethatcanb
7、everylong,inimageprocessingthedigitizedimagessentseriallytakemillionsofcharacterseach.Thestring-matchingproblemisthebasicquestionconsideredinthebook,togetherwithitsvariations.String-matchingisalsothebasicsubprobleminveryotheralgorithmicproblemsontexts.Belowthereisa(notexclusi
8、ve)listofbasicgroupsofproblemsdiscussedinthebook:variationsonthestri
此文档下载收益归作者所有
点击更多查看相关文章~~