{"entities":{"Q5953598":{"pageid":8130400,"ns":120,"title":"Item:Q5953598","lastrevid":41626396,"modified":"2025-05-06T13:05:27Z","type":"item","id":"Q5953598","labels":{"en":{"language":"en","value":"Bounding the inefficiency of length-restricted prefix codes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1695190"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$7EC79E25-4DB2-4A11-8CF4-86D528443CC1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d95c7211d8c99750bd4048b5acdb06fe2346325c","datavalue":{"value":{"text":"Bounding the inefficiency of length-restricted prefix codes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5953598$2D943CA8-9681-434E-BFD6-2499BA935C2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"049a9e969044b6d9ab15de91b369d6f77852428c","datavalue":{"value":"1012.94008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$A61EDE77-9CD4-4E51-BF47-14A6AC21AB90","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d540acb3c17412eca3767e289e45041977a7c40f","datavalue":{"value":{"entity-type":"item","numeric-id":1209530,"id":"Q1209530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$F5482B50-7FD0-464E-A1DA-EAED760FBBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96c336c47481eefdf3bf8537c9af3521411ea42d","datavalue":{"value":{"entity-type":"item","numeric-id":935153,"id":"Q935153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$7B0AB2E4-8ED7-4BF0-B046-77F30661A928","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$48C182AF-978A-44F2-83E7-251C70345935","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae38298a411e50615364cd6c80d7e0f949b3a896","datavalue":{"value":{"time":"+2003-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5953598$0D3DC4E4-471E-4352-AE3C-A25710437084","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75eb2aec5c474869e32b04fbba012344598ec234","datavalue":{"value":"Comparisons between the average length \\(A\\) of an optimal prefix code and the average length \\(A_L\\) of an optimal \\(L\\)-restricted prefix code are presented. It has been proved that: if \\(L=\\lceil \\log n\\rceil\\) then \\(A_L-A<\\lceil \\log n\\rceil-1\\); if \\(L>\\lceil\\log n\\rceil\\) then \\(A_L-A<1/\\psi^{L-\\lceil\\log(n+\\lceil\\log n\\rceil-L)\\rceil-1}\\), where \\(\\psi\\) is the golden ratio and \\(n\\) is the number of elements of the alphabet \\(\\Sigma\\). For \\(\\lceil\\log n\\rceil < L \\leq n/2\\) the bound is asymptotically tight. For \\(L\\geq \\lceil\\log n\\rceil+11\\) the bound guarantees that \\(A_L-A<0.01\\). Additionally, an \\(O(n)\\) time and space \\(1/\\psi^{L-\\lceil\\log(n+\\lceil\\log n\\rceil-L)\\rceil-1}\\)-approximative algorithm to construct \\(L\\)-restricted prefix codes is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$7F10B73D-533F-45AB-BE0E-68A5BF5FCDBD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a6597df2226fe6c5d3d23f6123dd1ba6d2a0bece","datavalue":{"value":{"entity-type":"item","numeric-id":587062,"id":"Q587062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$F751AB44-6013-484C-AD6D-137049D3E53E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf807832f23b1843158a0f1abb6a671308ea384a","datavalue":{"value":"94A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$78FB46E1-C6D2-43B2-A485-70A56DAA1320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$19D77ACC-A2A1-465D-8148-4A1F7CEFA82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$DA8D9E57-EC8D-4E9F-B3BB-49D7E2DE394C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7875222b19c2604b611ae8bc147651e78e213ff0","datavalue":{"value":"1695190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$49915123-AB7F-47C4-976D-949C1A58E174","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4645c6d326dc5e122b74e03f4c788140cafff7a","datavalue":{"value":"prefix codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$714B6B92-3D51-4F33-9D4D-882D7DD826D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16e266e2004b9230fc127aa688c524969195b555","datavalue":{"value":"Huffman trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$4C7825A9-1A36-400E-A3C9-452AB1F8188C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba3671326ab8a9b195aa9f697d844ba2c120b538","datavalue":{"value":"approximative algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$34732411-9F20-47D6-9DFD-74E05A36019E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f8dd5c493bcfe457a2c05cd0b9ce65be151090","datavalue":{"value":"compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$3949940C-936D-4BDB-A937-A52232AE8AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5935250e4e60897f7fdffe660d9ac37d224e316","datavalue":{"value":"redundancy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953598$AB0C0432-0256-4EB0-8D43-16CB2945B3E7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953598$BF688A8A-E677-4D3B-97C6-B75BC9C74FEB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ab8c5990c2ff5bff2449d9c9c3ecbe946bfbe7ce","datavalue":{"value":"https://doi.org/10.1007/s00453-001-0060-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5953598$7471E8BE-8236-43CD-85F6-3DE0556C4B88","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f43067f605342649a0d44c5dd5bcb19e29e3bb5","datavalue":{"value":"W106140241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$527EAB51-DE28-42DF-8DFE-A205D42F0A97","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da93afcd631b43952f110a1b801c3592349a2e16","datavalue":{"value":"10.1007/S00453-001-0060-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953598$C5383657-0C82-4DAD-BBE0-F0679614BED6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52acb64bdc703299d1a66e9cdb0bcf94328a9ed0","datavalue":{"value":{"entity-type":"item","numeric-id":3688307,"id":"Q3688307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc631dbbf7ac9e515d4d3e3b3fc7f81470769865","datavalue":{"value":{"amount":"+0.8959044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$72534742-B1A5-448C-A80C-B68DAA4EA31D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5b64e99296a9b72d1e041ded37dfba81c09167d","datavalue":{"value":{"entity-type":"item","numeric-id":2977298,"id":"Q2977298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d618e2c81dd1ae42fe67f68559bb8b515061ce2f","datavalue":{"value":{"amount":"+0.89470994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$D2F9ED5F-8E12-43CD-B455-2F0997FFF071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5377ec0785bf89200fdba444f80aaddff4e9af28","datavalue":{"value":{"entity-type":"item","numeric-id":3604634,"id":"Q3604634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2090c4852bc2728a8aa71fcfc8b0d7454558e610","datavalue":{"value":{"amount":"+0.89262277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$A4AE058C-641C-4968-AB5B-5D359BE26641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84c4c132db1ddfa996e4577533219e852d69df7f","datavalue":{"value":{"entity-type":"item","numeric-id":5124437,"id":"Q5124437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4adc770f90e7aaed39fe3e0386824f71e029c02a","datavalue":{"value":{"amount":"+0.8908274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$204359A9-ED5C-4D46-8A17-0C3FCF9AD306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cac988a37f90725ee9f44dad917e9d4a6bd8385","datavalue":{"value":{"entity-type":"item","numeric-id":5394266,"id":"Q5394266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74d40994387c608dd08f77fb24a5035a1d4f521d","datavalue":{"value":{"amount":"+0.8906167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$4F5B789D-2FAF-4C87-B119-E12DE779488D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08fb071ab879b6926d4a98a6d25c0bd5ce71aceb","datavalue":{"value":{"entity-type":"item","numeric-id":1752605,"id":"Q1752605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04b2084face7f61bfd1aa1632058a8c0d1b4dfff","datavalue":{"value":{"amount":"+0.88989437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$161FC6C8-D061-4119-BD4B-1A0A794B6BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c436944c5b6c2b1752178c21f2edb6a1245fb90","datavalue":{"value":{"entity-type":"item","numeric-id":4508379,"id":"Q4508379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0807143f4e7cc072c69571832bf636e58d2d5610","datavalue":{"value":{"amount":"+0.8853732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$799B1815-A809-49F6-A746-BEF1D55D43C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e7ef7448998d1cb8ff225b47f089d71d124fb02","datavalue":{"value":{"entity-type":"item","numeric-id":4975805,"id":"Q4975805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"559a7beb2ade7a0dcdf35ebba8fef11f989f0ffa","datavalue":{"value":{"amount":"+0.884012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$2798D275-6445-4D30-9CD0-F7423EDC7393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d0cfdeac7f5c0d48686ddd7ac195bb2b36d205","datavalue":{"value":{"entity-type":"item","numeric-id":3604768,"id":"Q3604768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea6e8a641ab7ac25123f7e42057ced47aaa1eaae","datavalue":{"value":{"amount":"+0.8818301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$63E5DD54-36DA-46CF-A720-9F6E34333D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd2961d2e67fed0b3418a350b2f29bb97219d5bb","datavalue":{"value":{"entity-type":"item","numeric-id":5387768,"id":"Q5387768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea6e8a641ab7ac25123f7e42057ced47aaa1eaae","datavalue":{"value":{"amount":"+0.8818301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5953598$767CB3ED-C3A9-475F-92CD-5CA0040C7FBE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5953598","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5953598"}}}}}