text_algorithms

《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