资源描述：
《a dynamic programming algorithm for constructing optimal “1”-ended binary prefix-free cod》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.46,NO.4,JULY20001637[7]S.VerdúandT.S.Han,“Ageneralformulaforchannelcapacity,”IEEETrans.Inform.Theory,vol.40,pp.1147–1158,July1994.[8]F.M.J.Willems,“Thecontext-treeweightingmethod:Extensions,”inIEEEInt.Symp.InformationTheory,Trondheim,Norway,1994.[9],“Codingfo
2、rabinaryindependentpiecewise-identically-dis-tributed-source,”IEEETrans.Inform.Theory,vol.42,pp.2210–2217,Fig.1.CodeCisanoptimalprefix-freecodeforthedistributionNov.1996.(1=6);(1=6);(1=6);(1=6);(1=6);(1=6).CisanoptimalOne-ended[10]E.YangandJ.C.Kieffer,“Simpleuniversallossydatacompressionprefix-free
3、codeforthesamedistribution.Cisanoptimalone-endedcodeforschemesderivedfromtheLempel–Zivalgorithm,”IEEETrans.Inform.thedistribution0:9;0:09;0:009;0:0009;0:00009;0:00001.Theory,vol.42,pp.239–245,Jan.1996.[11]J.ZivandA.Lempel,“Compressionofindividualsequenceviavariableratecoding,”IEEETrans.Inform.Theor
4、y,vol.IT-24,pp.530–536,Sept.O(nlogn)timeusingthegreedyHuffman-Encodingalgorithm,see,1978.e.g.,[5]orevenO(n)timeifthepiarealreadysorted[6].In1990,BergerandYeung[1]introducedanewvariantofthisproblem.Theydefinedafeasibleor1-endedcodetobeaprefix-freecodeinwhicheverywordisrestrictedtoendwitha“1.”Suchcod
5、esareused,forexample,inthedesignofself-synchronizingcodes[3]andtesting.GivenP,theproblemistofindtheminimum-cost1-endedADynamicProgrammingAlgorithmforConstructingcode.Fig.1givessomeexamples.Optimal“”-EndedBinaryPrefix-FreeCodesIntheirpaper,BergerandYeungderivedpropertiesofsuchcodes,suchastherelation
6、shipofamin-costfeasiblecodetotheentropyofSze-LokChanandMordecaiJ.Golin,Member,IEEEP,andthendescribedanalgorithmtoconstructthem.Theiralgorithmworksbyexaminingallcodesofaparticulartype,returningthemin-Abstract—ThegenericHuffman-EncodingProblemoffindingamin-imumone.Theynotedthatexperimentalevidencesee
7、medtoindicateimumcostprefix-freecodeisalmostcompletelyunderstood.Therestillthattheiralgorithmrunsintimeexponentialinn.Afewyearslater,existmanyvariantsofthisproblemwhicharenotaswellunderstood,Capocelli,DeSan
