管道風(fēng)格kwic--lxy

1、KWICImplementedwithPipeFilterArchitecturalStyle采用管道過(guò)濾器體系結(jié)構(gòu)風(fēng)格實(shí)現(xiàn)KWIC關(guān)鍵詞索引系統(tǒng)KWICImplementedwithPipeFilterArchitecturalStyle2采用管道過(guò)濾器體系結(jié)構(gòu)風(fēng)格實(shí)現(xiàn)KWIC關(guān)鍵詞索引系統(tǒng)21 PipeFilterSystemsinGeneral22 一般而言的管道過(guò)濾器系統(tǒng)23 Architecture32 體系結(jié)構(gòu)32.1 PipesinKWICsystem32.2 KWIC系統(tǒng)中的管道32.3 FiltersinKWICSystem42.4 KWIC系統(tǒng)中的過(guò)濾器42.5 Pipel

2、ineinKWICsystem52.6 KWIC系統(tǒng)中的傳輸途徑53Students'Assignment63 學(xué)生作業(yè)63.1 ImplementShiftFilterMechanism63.2 循環(huán)移位機(jī)制實(shí)現(xiàn)63.3 ImplementLineandShiftTransformMechanism63.4 行與循環(huán)移位變換機(jī)制的實(shí)現(xiàn)63.5 Answerunderstandingquestions73.6 回答理解問(wèn)題7KWICImplementedwithPipeFilterArchitecturalStyle采用管道過(guò)濾器體系結(jié)構(gòu)風(fēng)格實(shí)現(xiàn)KWIC關(guān)鍵詞索引系統(tǒng)1PipeFilt

3、erSystemsinGeneral2.2 一般而言的管道過(guò)濾器系統(tǒng)Inapipeandfilterstyleeachcomponenthasasetofinputstreamsandasetofoutputstreams.Acomponentreadsstreamsofdataonitsinputstreams,processesthedataandwritestheresultingdataonitsoutputstreams.Hencecomponentsaretermedfilters.Theconnectorsofthisstylemergethestreamstogether,i.

4、e.,theytransmitoutputsofonefiltertoinputsofanotherfilter.Hencetheconnectorsaretermedpipes.在管道和過(guò)濾器風(fēng)格，每個(gè)組件有一個(gè)輸入流和輸出流。一個(gè)組件從輸入流讀取數(shù)據(jù)流，然后處理數(shù)據(jù)，并向輸出流寫入結(jié)果數(shù)據(jù)。因此組件被稱為過(guò)濾器。這種風(fēng)格的連接器把流合并一起，即，他們發(fā)送一個(gè)過(guò)濾器的輸出到另一過(guò)濾器的輸入。因連接器此被稱為管道。LegendFilters*PipesFigure1：Pipe-filterstup口沁winmpipt-flItersystem2 Pipe-filterstopologyinag

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

6、heendsoftheirpipes.圖1:管道-過(guò)濾器系統(tǒng)的一般管道-過(guò)濾器拓?fù)浣Y(jié)構(gòu)在這種風(fēng)格中最重要的不變量就是過(guò)濾器必須是獨(dú)立的實(shí)體：特別是，他們不應(yīng)該與其他過(guò)濾器共享狀態(tài)。另一個(gè)重要的不變量是過(guò)濾器不知道上游和下游的過(guò)濾器的識(shí)別方式。因此，過(guò)濾器可能無(wú)法識(shí)別的管道兩端的組件。Commonspecializationsofthisstyleincludepipelines(seefigurebelow),whichrestrictthetopologiestolinearsequencesoffilters;boundedpipes,whichrestricttheamountofdat

7、athatcanresideonapipe;andtypedpipes,whichrequirethatthedatapassedbetweentwofiltershaveawell-definedtype.這種風(fēng)格常見的特點(diǎn)包括管道(見下圖)，這限制了過(guò)濾器線性序列的拓?fù)洌挥薪绻艿?，這限制了可以駐留在一個(gè)管的數(shù)據(jù)的數(shù)量；和輸入管，這要求通過(guò)兩過(guò)濾器之間的數(shù)據(jù)有一個(gè)明確的類型。eqend'FlltenPipe*FigureZ:Pipelinetopologyinaspecificpipe-filtersystem3 Pipelinetopologyinaspecificpipe-fil

8、tersystemThebest-knownexamplesofpipeandfilterarchitecturesareprogramswrittenintheUNIXshell.UNIXsupportsthisstylebyprovidinganotationforconnectingcomponents(representedasUNIXprocesses)andbyprovidingrun-timemechanismsforimplementingpipes.圖2:一個(gè)具體管道-過(guò)濾器系統(tǒng)的管道拓?fù)渥钣忻艿篮瓦^(guò)濾器的結(jié)構(gòu)的例子是用UNIX操作系統(tǒng)編寫的程序。UNIX支持這種風(fēng)格提供了

9、一個(gè)連接組件的符號(hào)（代表操作過(guò)程）并為實(shí)現(xiàn)管道提供運(yùn)行時(shí)機(jī)制。2ArchitecturePipeandFilterKWICsystemiscomposedofthefollowingcomponents:?Inputfilter,whichreadsthecontentofaKWICinputfile,parsesit,andwritestheparsedlinestoitsoutputstream.2架構(gòu)管道和過(guò)濾器的關(guān)鍵詞檢索系統(tǒng)由以下部件組成：?輸入過(guò)濾器，它讀取關(guān)鍵詞索引輸入文件的內(nèi)容，分析它，并將分析到的內(nèi)容寫到其輸出流。?CircularShifterfilterconnected

10、withapipetotheoutputstreamofInputfilter.Thus,thelinesproducedbyInputfilterserveasinputforCircularShifterfilter.CircularShifterprocessestheinputlinesproducingcircularshiftsofthoselines.TheproducedshiftsarewrittentotheCircularShifter'soutputstream.?circularshifter過(guò)濾器通過(guò)管道連接輸出流到輸入流過(guò)濾器。因此，這些行通過(guò)為circu

11、larshifter過(guò)濾器輸入服務(wù)的輸入流產(chǎn)生。Circularshifter對(duì)這些行的處理就產(chǎn)生了這些行的循環(huán)移位行。所產(chǎn)生的循環(huán)移位行是寫入到輸出circularshifter?AlphabetizerfilterconnectedwithapipetotheoutputstreamofCircularShifterfilter.Thus,circularshiftsproducedbyCircularShifterserveasinputforAlphabetizer.Alphabetizersortstheseshiftsalphabeticallyandwritesthemtoits

12、outputstream.Alphabetizerfilter（按字母順序排列過(guò)濾器）通過(guò)管道連接到circularshifter過(guò)濾器的輸出流。因此由circularshifter產(chǎn)生的循環(huán)移位行作為Alphabetizerfilter的輸入。Alphabetizerfilter把這些循環(huán)移位行按字母順序排序并寫入到輸出流?OutputfilterconnectedwithapipetotheoutputstreamofAlphabetizer.Thus,Outputreadssortedshiftsfromitsinputstreamandwritesthemtothestandardou

13、tput.輸出過(guò)濾器通過(guò)管道連接到Alphabetizer流的輸出。因此，Output從輸入流讀取排好序的行并寫入到標(biāo)準(zhǔn)輸出。?MasterControl,whichmanagesfilterandpipemechanism,bycreatingapipelineoftheabovedescribedfilters.好控制，通過(guò)建立以上所述的過(guò)濾器的管道序列，管理過(guò)濾器和管道機(jī)制。口I/OMedium1HSystemI/OFlgurt3;PipeliieinKWJCfyst«m4 PipelineinKWICsystem3 PipesinKWICsystemPipesintheKWI

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

15、am.圖3:關(guān)鍵詞檢索系統(tǒng)中的管道個(gè)管道關(guān)鍵詞檢索系統(tǒng)管道在關(guān)鍵詞檢索系統(tǒng)的表示為管道類的實(shí)例。管道的實(shí)例類是一個(gè)兩個(gè)流的組合：一個(gè)輸入和輸出流。管類連接這些流的方式如下。寫入到輸入流的數(shù)據(jù)被傳輸?shù)捷敵隽鳌＿@樣，這些數(shù)據(jù)可用于被從輸出流讀取。ThePipeclassencapsulatestheinputandoutputstreamsasitsprivateinstancevariablesandprovidejustasimplepublicinterfaceforwritingandreadingdatatoapipeobject.Thus,clientssimplywritesomed

16、atatoapipeobjectbycallingitswritemethod.Thisdatabecomesthenavailableforotherclients,whichcancallthereadmethodofthepipeobjecttoretrievethedata.管道類封裝輸入、輸出流是通過(guò)作為它的私有的實(shí)例變量并且僅僅提供一個(gè)向管道讀取數(shù)據(jù)的一個(gè)公共接口，因此，用戶在向一個(gè)管道對(duì)象寫數(shù)據(jù)的時(shí)候只需要通過(guò)調(diào)用它的寫方法，然后這些數(shù)據(jù)變得可以被其他客戶可用，這些客戶可以通過(guò)調(diào)用管道對(duì)象的讀方法來(lái)檢索數(shù)據(jù)。PipereaderPipedReader*read(ouicint)+

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

18、圖管道對(duì)象有幾個(gè)重要的性能：布對(duì)象限制可以承受的數(shù)據(jù)量。然而，當(dāng)客戶端從一個(gè)管讀取數(shù)據(jù)，這一數(shù)據(jù)被認(rèn)為是消費(fèi)的知被檢索到的數(shù)據(jù)所占去的空間就被釋放了。?Pipeobjectsaresynchronized.Thishastwomajorconsequences.Firstly,therecanbeonlyonethreadworkingwithapipeobjectataspecificmoment,i.e,therecanbeonlyonethreadcurrentlywritingorreadingthedatafromapipeobject.Secondly,threadsreading

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

20、thread,wheretheproducerthreadwritessomedatatothepipe,andtheconsumerthread"consumes"thatdatafromthepipe.嘴對(duì)象是同步的。這兩家主要的后果。首先，只能有一個(gè)線程在一個(gè)特定的時(shí)刻通過(guò)一個(gè)管道對(duì)象工作，即，只能有一個(gè)線程正在從一個(gè)管道對(duì)象讀或?qū)憯?shù)據(jù)。其次，從一個(gè)空的管道讀或向一個(gè)滿的管道寫就會(huì)受阻，只要管道沒(méi)有數(shù)據(jù)可讀或沒(méi)有空間可寫，就會(huì)阻塞。因此，一管對(duì)象可被視為一個(gè)典型的共享數(shù)據(jù)結(jié)構(gòu)的生產(chǎn)者/消費(fèi)者多線程情況。因此，一管對(duì)象始終是被生產(chǎn)者和消費(fèi)者線程共享，在這里在生產(chǎn)者線程寫

21、入一些數(shù)據(jù)到管道，消費(fèi)者線程從數(shù)據(jù)管消費(fèi)”數(shù)據(jù)。FiltersinKWICSystemFiltersintheKWICsystemarerepresentedbyanabstractclassnamedFilter.AninstanceofFilterclassiscomposedof:關(guān)鍵詞檢索系統(tǒng)的過(guò)濾器關(guān)鍵詞檢索系統(tǒng)的過(guò)濾器是由一個(gè)抽象類命名的過(guò)濾器。過(guò)濾器類的實(shí)例組成是:?Inputpipeobject,fromwhichthefilterobjectreadsthedata?Outputpipeobject,towhichthefilterobjectwritestheprocess

22、eddata?Threadofcontrol.Eachfilterobjectrunsinitsownthreadandisindependentofanyotherfiltersinthesystem,i.e.,itdoesnotsharestatewithotherfiltersinthesystem.?輸入管對(duì)象，從該過(guò)濾器對(duì)象讀取數(shù)據(jù)?俞出管對(duì)象，該過(guò)濾器對(duì)象寫入處理過(guò)的數(shù)據(jù)彼程控制。每個(gè)過(guò)濾器對(duì)象運(yùn)行在它自己的線程，獨(dú)立于系統(tǒng)中任何其他過(guò)濾器，即，在系統(tǒng)中它與其他過(guò)濾器不共享狀態(tài)。FiJtorabstract)#lnput_Pipe"iS'Startfrd_bool

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

24、vokesthefilter'stransformmethod.圖5:過(guò)濾類圖當(dāng)前實(shí)現(xiàn)的過(guò)濾器類已經(jīng)提供了基本過(guò)濾器功能。因此，客戶通過(guò)調(diào)用其start方法開始執(zhí)行的過(guò)濾器對(duì)象。反過(guò)來(lái)，這種方法啟動(dòng)了控制線程，（控制線程）連續(xù)調(diào)用過(guò)濾器的轉(zhuǎn)換方法。Inthecurrentimplementationthetransformmethodisanabstractmethod,whichmeansthatsubclassesofFilterclassshouldprovideaparticularimplementationforthatspecificfilterobject.Forexa

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

26、dataisretrievedfromtheinputpipe,transformed（processed）andwrittenouttotheoutputpipe.在當(dāng)前的實(shí)現(xiàn)中transformmethod（轉(zhuǎn)換方法）是一個(gè)抽象方法，即過(guò)濾器類的子類應(yīng)該為具體的過(guò)濾器對(duì)象提供一個(gè)具體的實(shí)現(xiàn)。例如，circularshifter過(guò)濾器以下列方式實(shí)現(xiàn)變換方法。從輸入管道檢索來(lái)的數(shù)據(jù)經(jīng)過(guò)處理后產(chǎn)生了循環(huán)移位行。此后，產(chǎn)生的循環(huán)移位行是寫入到輸出管道。更廣泛地說(shuō)，過(guò)濾器子類以下列方式執(zhí)行其變換方法：數(shù)據(jù)是從輸入管得到，轉(zhuǎn)換（加工）然后寫入到輸出管。Filterobjectsmaybecombine

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

28、sintoasequence（pipeline）toachievethedesiredfunctionalityofthesystem.過(guò)濾器對(duì)象通過(guò)簡(jiǎn)化為共享一個(gè)管道對(duì)象時(shí)可以歸入典型的生產(chǎn)/消費(fèi)者模型。例如，我們指定第一個(gè)過(guò)濾器的輸出管道到第二個(gè)過(guò)濾器的輸入管道。因此，當(dāng)?shù)谝粋€(gè)過(guò)濾器產(chǎn)生的數(shù)據(jù)并將其寫入到輸出管，這個(gè)數(shù)要被第二個(gè)過(guò)濾器消費(fèi)。因此，我們可以使用許多過(guò)濾器形成一個(gè)序列（管道）為實(shí)現(xiàn)系統(tǒng)的預(yù)期功能。PipelineinKWICsystemThecurrentKWICsystemutilizesapipelineconsistingofthefollowingfourfilters

29、:?Inputfilter?CircularShifterfilter?Alphabetizerfilter?OutputfilterAllKWICfiltersareofcoursesubclassesofabstractFilterclass.Theserelationshipsaredepictedonthefollowingclassdiagram:在關(guān)鍵詞檢索系統(tǒng)中的管道序列目前的關(guān)鍵詞檢索系統(tǒng)采用管道序列包括以下四個(gè)過(guò)濾器：?輸入過(guò)濾器化ircularshifter循環(huán)移位過(guò)濾器彼字母排序過(guò)濾器?輸出過(guò)濾器所有的題內(nèi)關(guān)鍵詞過(guò)濾當(dāng)然是子類的抽象類過(guò)濾器。這些關(guān)系的描繪在下面的類圖: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:過(guò)濾器類的子類四個(gè)關(guān)鍵詞檢索過(guò)濾器通過(guò)以下管道連接：?in_cs管，由Input輸入和circularshifter過(guò)濾器共享，即，這是輸入過(guò)濾器的的輸出管道，是circularshifter過(guò)濾器的輸入管道。?cs_al管,由circularshifter和Alphabetizer（按字母順序排列）過(guò)濾器共享，即，這是circularshifter過(guò)濾器的輸出管道和Alphabetizer（輸入管按字母排序）過(guò)濾器的輸入管道。?cs_ou管，它由按字母排序和輸出過(guò)濾器之間共享，即Alphabetizer（輸入管按字母飾序）過(guò)濾器的輸出管道和輸出過(guò)濾器的輸入管道。下圖顯示了當(dāng)

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

34、aredenotedasnoisewords.Noisewordsshouldbedefinedinaspecialfile,whichmustbepassedtotheKWICsystemasthesecondcommandlineargument(thefirstcommandlineargumentisthenameoftheinputKWICfile).Thus,toinvokethesystemfromthecommandlinewetype:javakwic.pf.KWICkwic.txtnoise.txt3學(xué)生作業(yè)完成移位過(guò)濾器機(jī)制在關(guān)鍵詞檢索系統(tǒng)中從數(shù)據(jù)流的某個(gè)單詞開始移動(dòng)序列

35、，開始的單詞決定了哪一個(gè)序列要被從數(shù)據(jù)流中移除，它被指名為噪音單詞，噪音單詞應(yīng)被定義在一個(gè)特定的文件中，它必須被作為第二個(gè)參數(shù)傳給關(guān)鍵詞檢索系統(tǒng)(第一個(gè)命令行參數(shù)是關(guān)鍵詞檢索系統(tǒng)輸入文件的名稱)。因此，調(diào)用系統(tǒng)命令要從我們輸入命令行開始：Javakwic.pf.kwickwic.txtnoise.txtTheformatofthenoisewordsfileisverysimple:Asinglenoisewordisstoredonasinglelineinthefile.Thus,thesystemshouldparsethenoisewordsfile,keepallnoisewords

36、inthememory,comparethefirstwordofeachsingleshiftwithallofnoisewords,andfinallyremoveallshiftsthatstartwithanoiseword.噪音詞文件格式很簡(jiǎn)單：一個(gè)噪聲字是存儲(chǔ)在文件中的單獨(dú)一行。因此，該系統(tǒng)應(yīng)分析噪音詞文件，把所有的噪音詞存在內(nèi)存中，用噪音詞比較每一個(gè)序列的第一個(gè)單詞，并最終移動(dòng)所有以噪音詞開始的序列。Hint:YoushouldimplementanewFiltersubclass,sayShiftFilter.ShiftFiltermaykeepallnoisewordsasi

37、tsinstancevariables.InthetransformmethodofShiftFilterclass,youmaywanttoremoveallshiftsstartingwithanoisewordfromthedataflow.Finally,youneedtoinsertaninstanceofShiftFilterattheproperplaceinthecurrentpipeline.ImplementLineandShiftTransformMechanism提示：你要實(shí)現(xiàn)一個(gè)新的過(guò)濾器子類，叫shiftfilter0shiftfilter可能把所有的噪音詞作為它的

38、實(shí)例變量。在shiftfilter類的轉(zhuǎn)換方法中，你可能想要移動(dòng)所有從數(shù)據(jù)流來(lái)的以噪音次開始的序列。最后，你需要在在目前的管道適當(dāng)?shù)牡攸c(diǎn)插入一個(gè)shiftfilter的實(shí)例。實(shí)現(xiàn)行和序列變換機(jī)制Generally,LineTransformMechanismaltersthecontentofasinglelineinthefollowingway.Thefirstwordofthelineiscapitalized.i.e.,allcharactersofthefirstwordareconvertedtouppercase.Hereisanexample:StarWarsAftertran

39、sformingit:STARWars一般來(lái)說(shuō)，行轉(zhuǎn)換機(jī)制，改變一單行的內(nèi)容的方式如下。行的第一個(gè)字母大寫的線。即，第一個(gè)單詞的所有字符轉(zhuǎn)換為大寫。這里是一個(gè)例子：StarWarsAftertransformingit:STARWarsYouneedtoapplythismechanismforbothalloriginallinesandallcircularshifts.Thus,firstalloriginallinesaretransformedresultingineachoriginallinestartingwithacapitalizedword.Secondly,wemake

40、circularshiftswithtransformedlines.Finally,allcircularshiftsaretransformedresultingineachcircularshiftstartingwithacapitalizedword.Forexample,letuslookonthefollowingoriginalline:你需要對(duì)所有原始行和移位行使用這個(gè)機(jī)制。因此，首先所有原始行被轉(zhuǎn)換導(dǎo)致每個(gè)原始行從一個(gè)大寫的單詞開始。其次，我們用轉(zhuǎn)換的行進(jìn)行循環(huán)移位。最后，所有的循環(huán)移位行轉(zhuǎn)化成從一個(gè)大寫的單詞開始的行。例如，讓我們看看以下原始行：TheEmpireStri

41、kesBackTheresultantshiftsafteralltransformationslookasfollows:循環(huán)移位行轉(zhuǎn)換后如下：THEEmpireStrikesBackBACKTHEEmpireStrikesSTRIKESBackTHEEmpireEMPIREStrikesBackTHEHint:WriteanewsubclassofFilterclass.LetuscallthisnewclassLineTransformerclass.Inthetransformmethodofthenewclassimplementtheuppercaseconversionofthefirstword.Toimplementtheabovede