管道风格kwic--lxy

1、KWICImplementedwithPipeFilterArchitecturalStyle采用管道过滤器体系结构风格实现KWIC关键词索引系统KWICImplementedwithPipeFilterArchitecturalStyle2采用管道过滤器体系结构风格实现KWIC关键词索引系统21 PipeFilterSystemsinGeneral22 一般而言的管道过滤器系统23 Architecture32 体系结构32.1 PipesinKWICsystem32.2 KWIC系统中的管道32.3 FiltersinKWICSystem42.4 KWIC系统中的过滤器42.5 Pipel

2、ineinKWICsystem52.6 KWIC系统中的传输途径53Students'Assignment63 学生作业63.1 ImplementShiftFilterMechanism63.2 循环移位机制实现63.3 ImplementLineandShiftTransformMechanism63.4 行与循环移位变换机制的实现63.5 Answerunderstandingquestions73.6 回答理解问题7KWICImplementedwithPipeFilterArchitecturalStyle采用管道过滤器体系结构风格实现KWIC关键词索引系统1PipeFilt

3、erSystemsinGeneral2.2 一般而言的管道过滤器系统Inapipeandfilterstyleeachcomponenthasasetofinputstreamsandasetofoutputstreams.Acomponentreadsstreamsofdataonitsinputstreams,processesthedataandwritestheresultingdataonitsoutputstreams.Hencecomponentsaretermedfilters.Theconnectorsofthisstylemergethestreamstogether,i.

4、e.,theytransmitoutputsofonefiltertoinputsofanotherfilter.Hencetheconnectorsaretermedpipes.在管道和过滤器风格，每个组件有一个输入流和输出流。一个组件从输入流读取数据流，然后处理数据，并向输出流写入结果数据。因此组件被称为过滤器。这种风格的连接器把流合并一起，即，他们发送一个过滤器的输出到另一过滤器的输入。因连接器此被称为管道。LegendFilters*PipesFigure1：Pipe-filterstup口沁winmpipt-flItersystem2 Pipe-filterstopologyinag

5、eneralpipe-filtersystemAmongtheimportantinvariantsofthestyleistheconditionthatfiltersmustbeindependententities:inparticular,theyshouldnotsharestatewithotherfilters.Anotherimportantinvariantisthatfiltersdonotknowtheidentityoftheirupstreamanddownstreamfilters.Thus,filtersmaynotidentifythecomponentsont

6、heendsoftheirpipes.图1:管道-过滤器系统的一般管道-过滤器拓扑结构在这种风格中最重要的不变量就是过滤器必须是独立的实体：特别是，他们不应该与其他过滤器共享状态。另一个重要的不变量是过滤器不知道上游和下游的过滤器的识别方式。因此，过滤器可能无法识别的管道两端的组件。Commonspecializationsofthisstyleincludepipelines(seefigurebelow),whichrestrictthetopologiestolinearsequencesoffilters;boundedpipes,whichrestricttheamountofdat

7、athatcanresideonapipe;andtypedpipes,whichrequirethatthedatapassedbetweentwofiltershaveawell-definedtype.这种风格常见的特点包括管道(见下图)，这限制了过滤器线性序列的拓扑；有界管道，这限制了可以驻留在一个管的数据的数量；和输入管，这要求通过两过滤器之间的数据有一个明确的类型。eqend'FlltenPipe*FigureZ:Pipelinetopologyinaspecificpipe-filtersystem3 Pipelinetopologyinaspecificpipe-fil

8、tersystemThebest-knownexamplesofpipeandfilterarchitecturesareprogramswrittenintheUNIXshell.UNIXsupportsthisstylebyprovidinganotationforconnectingcomponents(representedasUNIXprocesses)andbyprovidingrun-timemechanismsforimplementingpipes.图2:一个具体管道-过滤器系统的管道拓扑最有名管道和过滤器的结构的例子是用UNIX操作系统编写的程序。UNIX支持这种风格提供了

9、一个连接组件的符号（代表操作过程）并为实现管道提供运行时机制。2ArchitecturePipeandFilterKWICsystemiscomposedofthefollowingcomponents:?Inputfilter,whichreadsthecontentofaKWICinputfile,parsesit,andwritestheparsedlinestoitsoutputstream.2架构管道和过滤器的关键词检索系统由以下部件组成：?输入过滤器，它读取关键词索引输入文件的内容，分析它，并将分析到的内容写到其输出流。?CircularShifterfilterconnected

10、withapipetotheoutputstreamofInputfilter.Thus,thelinesproducedbyInputfilterserveasinputforCircularShifterfilter.CircularShifterprocessestheinputlinesproducingcircularshiftsofthoselines.TheproducedshiftsarewrittentotheCircularShifter'soutputstream.?circularshifter过滤器通过管道连接输出流到输入流过滤器。因此，这些行通过为circu

11、larshifter过滤器输入服务的输入流产生。Circularshifter对这些行的处理就产生了这些行的循环移位行。所产生的循环移位行是写入到输出circularshifter?AlphabetizerfilterconnectedwithapipetotheoutputstreamofCircularShifterfilter.Thus,circularshiftsproducedbyCircularShifterserveasinputforAlphabetizer.Alphabetizersortstheseshiftsalphabeticallyandwritesthemtoits

12、outputstream.Alphabetizerfilter（按字母顺序排列过滤器）通过管道连接到circularshifter过滤器的输出流。因此由circularshifter产生的循环移位行作为Alphabetizerfilter的输入。Alphabetizerfilter把这些循环移位行按字母顺序排序并写入到输出流?OutputfilterconnectedwithapipetotheoutputstreamofAlphabetizer.Thus,Outputreadssortedshiftsfromitsinputstreamandwritesthemtothestandardou

13、tput.输出过滤器通过管道连接到Alphabetizer流的输出。因此，Output从输入流读取排好序的行并写入到标准输出。?MasterControl,whichmanagesfilterandpipemechanism,bycreatingapipelineoftheabovedescribedfilters.好控制，通过建立以上所述的过滤器的管道序列，管理过滤器和管道机制。口I/OMedium1HSystemI/OFlgurt3;PipeliieinKWJCfyst«m4 PipelineinKWICsystem3 PipesinKWICsystemPipesintheKWI

14、CsystemarerepresentedasinstancesofthePipeclass.AninstanceofthePipeclassisacompositionoftwostreams:aninputandanoutputstream.Pipeclassconnectsthesetwostreamsinthefollowingway.Thedatathatiswrittentotheinputstreamistransmittedtotheoutputstream.Inthiswaythesedatabecomeavailableforreadingfromtheoutputstre

15、am.图3:关键词检索系统中的管道个管道关键词检索系统管道在关键词检索系统的表示为管道类的实例。管道的实例类是一个两个流的组合：一个输入和输出流。管类连接这些流的方式如下。写入到输入流的数据被传输到输出流。这样，这些数据可用于被从输出流读取。ThePipeclassencapsulatestheinputandoutputstreamsasitsprivateinstancevariablesandprovidejustasimplepublicinterfaceforwritingandreadingdatatoapipeobject.Thus,clientssimplywritesomed

16、atatoapipeobjectbycallingitswritemethod.Thisdatabecomesthenavailableforotherclients,whichcancallthereadmethodofthepipeobjecttoretrievethedata.管道类封装输入、输出流是通过作为它的私有的实例变量并且仅仅提供一个向管道读取数据的一个公共接口，因此，用户在向一个管道对象写数据的时候只需要通过调用它的写方法，然后这些数据变得可以被其他客户可用，这些客户可以通过调用管道对象的读方法来检索数据。PipereaderPipedReader*read(ouicint)+

17、wntccIrt)-*cferaeWtrter()Fipurr4:Pipedingrwrn5 PipeclassdiagramTherearefewimportantpropertiesofpipeobjects:?Pipeobjectslimittheamountofdatatheycanhold.However,wheneverclientsreadthedatafromapipe,thisdataisconsidered"consumed"andthespacethatwasoccupiedbytheretrieveddataismadefreeagain.图4:管类

18、图管道对象有几个重要的性能：布对象限制可以承受的数据量。然而，当客户端从一个管读取数据，这一数据被认为是消费的知被检索到的数据所占去的空间就被释放了。?Pipeobjectsaresynchronized.Thishastwomajorconsequences.Firstly,therecanbeonlyonethreadworkingwithapipeobjectataspecificmoment,i.e,therecanbeonlyonethreadcurrentlywritingorreadingthedatafromapipeobject.Secondly,threadsreading

19、fromanemptypipeorwritingtoafullpipeareblockedaslongastherearenotsomedatatoreadfromthepipe,orthereisnofreespaceinthepipetowritethedata.Thus,apipeobjectmaybeseenasatypicalsharedsynchronizeddatastructureforproducer/consumermulti-threadscenarios.Thus,apipeobjectisalwayssharedbetweenaproducerandaconsumer

20、thread,wheretheproducerthreadwritessomedatatothepipe,andtheconsumerthread"consumes"thatdatafromthepipe.嘴对象是同步的。这两家主要的后果。首先，只能有一个线程在一个特定的时刻通过一个管道对象工作，即，只能有一个线程正在从一个管道对象读或写数据。其次，从一个空的管道读或向一个满的管道写就会受阻，只要管道没有数据可读或没有空间可写，就会阻塞。因此，一管对象可被视为一个典型的共享数据结构的生产者/消费者多线程情况。因此，一管对象始终是被生产者和消费者线程共享，在这里在生产者线程写

21、入一些数据到管道，消费者线程从数据管消费”数据。FiltersinKWICSystemFiltersintheKWICsystemarerepresentedbyanabstractclassnamedFilter.AninstanceofFilterclassiscomposedof:关键词检索系统的过滤器关键词检索系统的过滤器是由一个抽象类命名的过滤器。过滤器类的实例组成是:?Inputpipeobject,fromwhichthefilterobjectreadsthedata?Outputpipeobject,towhichthefilterobjectwritestheprocess

22、eddata?Threadofcontrol.Eachfilterobjectrunsinitsownthreadandisindependentofanyotherfiltersinthesystem,i.e.,itdoesnotsharestatewithotherfiltersinthesystem.?输入管对象，从该过滤器对象读取数据?俞出管对象，该过滤器对象写入处理过的数据彼程控制。每个过滤器对象运行在它自己的线程，独立于系统中任何其他过滤器，即，在系统中它与其他过滤器不共享状态。FiJtorabstract)#lnput_Pipe"iS'Startfrd_bool

23、ean+Filter(inpmPipeoutpurPipe)+*芯*ruin()配ar73fbmbFilterrlhssdigram6 FilterclassdiagramThecurrentimplementationoftheFilterclassprovidesalreadythebasicfilterfunctionality.Thus,clientsstarttheexecutionofthefilterobjectbyinvokingitsstartmethod.Inturn,thismethodstartsthecontrolthread,whichconsecutivelyin

24、vokesthefilter'stransformmethod.图5:过滤类图当前实现的过滤器类已经提供了基本过滤器功能。因此，客户通过调用其start方法开始执行的过滤器对象。反过来，这种方法启动了控制线程，（控制线程）连续调用过滤器的转换方法。Inthecurrentimplementationthetransformmethodisanabstractmethod,whichmeansthatsubclassesofFilterclassshouldprovideaparticularimplementationforthatspecificfilterobject.Forexa

25、mple,CircularShifterfilterimplementstransformmethodinthefollowingway.Thelinesretrievedfromtheinputpipeareprocessedandcircularshiftsofthoselinesaremade.Thereaftertheproducedshiftsarewrittentotheoutputpipe.Speakingmoregenerally,subclassesofFilterclassimplementtheirtransformmethodsinthefollowingway:the

26、dataisretrievedfromtheinputpipe,transformed（processed）andwrittenouttotheoutputpipe.在当前的实现中transformmethod（转换方法）是一个抽象方法，即过滤器类的子类应该为具体的过滤器对象提供一个具体的实现。例如，circularshifter过滤器以下列方式实现变换方法。从输入管道检索来的数据经过处理后产生了循环移位行。此后，产生的循环移位行是写入到输出管道。更广泛地说，过滤器子类以下列方式执行其变换方法：数据是从输入管得到，转换（加工）然后写入到输出管。Filterobjectsmaybecombine

27、dintoatypicalproducer/consumerscenariobysimplysharingapipeobject.Forexample,weassigntheoutputpipeofthefirstfiltertotheinputpipeofthesecondfilter.Inthatwaywheneverthefirstfilterproducessomedataandwritesittoitsoutputpipe,thisdataisavailableforthesecondfiltertoconsumeit.Thus,wemaycombineanumberoffilter

28、sintoasequence（pipeline）toachievethedesiredfunctionalityofthesystem.过滤器对象通过简化为共享一个管道对象时可以归入典型的生产/消费者模型。例如，我们指定第一个过滤器的输出管道到第二个过滤器的输入管道。因此，当第一个过滤器产生的数据并将其写入到输出管，这个数要被第二个过滤器消费。因此，我们可以使用许多过滤器形成一个序列（管道）为实现系统的预期功能。PipelineinKWICsystemThecurrentKWICsystemutilizesapipelineconsistingofthefollowingfourfilters

29、:?Inputfilter?CircularShifterfilter?Alphabetizerfilter?OutputfilterAllKWICfiltersareofcoursesubclassesofabstractFilterclass.Theserelationshipsaredepictedonthefollowingclassdiagram:在关键词检索系统中的管道序列目前的关键词检索系统采用管道序列包括以下四个过滤器：?输入过滤器化ircularshifter循环移位过滤器彼字母排序过滤器?输出过滤器所有的题内关键词过滤当然是子类的抽象类过滤器。这些关系的描绘在下面的类图:U

30、gure6:of1-HierehsiiFigure6:SubclassesofFilterclassThefourKWICfiltersareconnectedbymeansofthefollowingpipes:?in_cspipe,whichissharedbetweenInputandCircularShifterfilter,i.e,thispipeistheoutputpipeforInputfilterandtheinputpipeforCircularShifterfilter.?cs_alpipe,whichissharedbetweenCircularShifterandAl

31、phabetizerfilter,i.e,thispipeistheoutputpipeforCircularShifterfilterandtheinputpipeforAlphabetizerfilter.?cs_oupipe,whichissharedbetweenAlphabetizerandOutputfilter,i.e,thispipeistheoutputpipeforAlphabetizerfilterandtheinputpipeforOutputfilter.Thefollowingfigureshowsthecurrentpipelineincludingthepipe

32、names:图6:过滤器类的子类四个关键词检索过滤器通过以下管道连接：?in_cs管，由Input输入和circularshifter过滤器共享，即，这是输入过滤器的的输出管道，是circularshifter过滤器的输入管道。?cs_al管,由circularshifter和Alphabetizer（按字母顺序排列）过滤器共享，即，这是circularshifter过滤器的输出管道和Alphabetizer（输入管按字母排序）过滤器的输入管道。?cs_ou管，它由按字母排序和输出过滤器之间共享，即Alphabetizer（输入管按字母饰序）过滤器的输出管道和输出过滤器的输入管道。下图显示了当

33、前包括管的名字的管道序列:(ipure7：KXVIXpipelinewithpiprFigure7:KWIXpipelinewithpipenames图7：kwix管道序列与管道的名字3Students'AssignmentImplementShiftFilterMechanismShiftFilterMechanismremovesshiftsstartingwithcertainwordsfromthedataflowintheKWICsystem.Thestartingwordsthatdecidewhichshiftsshouldberemovedfromthedataflow

34、aredenotedasnoisewords.Noisewordsshouldbedefinedinaspecialfile,whichmustbepassedtotheKWICsystemasthesecondcommandlineargument(thefirstcommandlineargumentisthenameoftheinputKWICfile).Thus,toinvokethesystemfromthecommandlinewetype:javakwic.pf.KWICkwic.txtnoise.txt3学生作业完成移位过滤器机制在关键词检索系统中从数据流的某个单词开始移动序列

35、，开始的单词决定了哪一个序列要被从数据流中移除，它被指名为噪音单词，噪音单词应被定义在一个特定的文件中，它必须被作为第二个参数传给关键词检索系统(第一个命令行参数是关键词检索系统输入文件的名称)。因此，调用系统命令要从我们输入命令行开始：Javakwic.pf.kwickwic.txtnoise.txtTheformatofthenoisewordsfileisverysimple:Asinglenoisewordisstoredonasinglelineinthefile.Thus,thesystemshouldparsethenoisewordsfile,keepallnoisewords

36、inthememory,comparethefirstwordofeachsingleshiftwithallofnoisewords,andfinallyremoveallshiftsthatstartwithanoiseword.噪音词文件格式很简单：一个噪声字是存储在文件中的单独一行。因此，该系统应分析噪音词文件，把所有的噪音词存在内存中，用噪音词比较每一个序列的第一个单词，并最终移动所有以噪音词开始的序列。Hint:YoushouldimplementanewFiltersubclass,sayShiftFilter.ShiftFiltermaykeepallnoisewordsasi

37、tsinstancevariables.InthetransformmethodofShiftFilterclass,youmaywanttoremoveallshiftsstartingwithanoisewordfromthedataflow.Finally,youneedtoinsertaninstanceofShiftFilterattheproperplaceinthecurrentpipeline.ImplementLineandShiftTransformMechanism提示：你要实现一个新的过滤器子类，叫shiftfilter0shiftfilter可能把所有的噪音词作为它的

38、实例变量。在shiftfilter类的转换方法中，你可能想要移动所有从数据流来的以噪音次开始的序列。最后，你需要在在目前的管道适当的地点插入一个shiftfilter的实例。实现行和序列变换机制Generally,LineTransformMechanismaltersthecontentofasinglelineinthefollowingway.Thefirstwordofthelineiscapitalized.i.e.,allcharactersofthefirstwordareconvertedtouppercase.Hereisanexample:StarWarsAftertran

39、sformingit:STARWars一般来说，行转换机制，改变一单行的内容的方式如下。行的第一个字母大写的线。即，第一个单词的所有字符转换为大写。这里是一个例子：StarWarsAftertransformingit:STARWarsYouneedtoapplythismechanismforbothalloriginallinesandallcircularshifts.Thus,firstalloriginallinesaretransformedresultingineachoriginallinestartingwithacapitalizedword.Secondly,wemake

40、circularshiftswithtransformedlines.Finally,allcircularshiftsaretransformedresultingineachcircularshiftstartingwithacapitalizedword.Forexample,letuslookonthefollowingoriginalline:你需要对所有原始行和移位行使用这个机制。因此，首先所有原始行被转换导致每个原始行从一个大写的单词开始。其次，我们用转换的行进行循环移位。最后，所有的循环移位行转化成从一个大写的单词开始的行。例如，让我们看看以下原始行：TheEmpireStri

41、kesBackTheresultantshiftsafteralltransformationslookasfollows:循环移位行转换后如下：THEEmpireStrikesBackBACKTHEEmpireStrikesSTRIKESBackTHEEmpireEMPIREStrikesBackTHEHint:WriteanewsubclassofFilterclass.LetuscallthisnewclassLineTransformerclass.Inthetransformmethodofthenewclassimplementtheuppercaseconversionofthefirstword.Toimplementtheabovede