{"entities":{"Q1736509":{"pageid":1747250,"ns":120,"title":"Item:Q1736509","lastrevid":56805459,"modified":"2026-03-23T15:58:47Z","type":"item","id":"Q1736509","labels":{"en":{"language":"en","value":"An online algorithm for lightweight grammar-based compression"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042122"}},"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":"Q1736509$3E00D7BE-D73C-4F69-A802-A43AC9D3F274","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"16e0855eb2bc6b8edba7f9e7db6031aba4a23325","datavalue":{"value":{"text":"An online algorithm for lightweight grammar-based compression","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736509$C3D8C394-A69A-4DC5-B26F-4487C495E7C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0d51dd3a728050d85fc0233aa0a687b6d422d30","datavalue":{"value":"1461.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$6A880568-B12D-40AE-A1A5-6BB050D3ADE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6c5d4cd1e2690e5be29daf64689640328725273","datavalue":{"value":{"entity-type":"item","numeric-id":1736508,"id":"Q1736508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736509$65E85347-D662-4B8C-9307-1DE009A7EDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ecba06da1291beb2f77aecfa4b3f126c91ea535","datavalue":{"value":{"entity-type":"item","numeric-id":782201,"id":"Q782201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736509$609DB48F-97A9-4ADF-BD2E-267C40480C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d0113d8101c678c76a9ca5f8acc6e79257d1982","datavalue":{"value":{"entity-type":"item","numeric-id":390900,"id":"Q390900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736509$3E2B0D34-3B9F-4692-B0A0-7A77CBCE0F55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736509$AF3158CA-8D67-40EE-8E59-4A92288215A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736509$51B2A157-13DA-48FE-BA06-5B6375241305","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e24a378093b4c7679cb29751c979637502893c89","datavalue":{"value":"Summary: Grammar-based compression is a well-studied technique to construct a context-free grammar (CFG) deriving a given text uniquely. In this work, we propose an online algorithm for grammar-based compression. Our algorithm guarantees \\(O(\\log^2n)\\)-approximation ratio for the minimum grammar size, where \\(n\\) is an input size, and it runs in input linear time and output linear space. In addition, we propose a practical encoding, which transforms a restricted CFG into a more compact representation. Experimental results by comparison with standard compressors demonstrate that our algorithm is especially effective for highly repetitive text.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736509$77F01D9B-5FEB-41EC-A424-2E2C950F611C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$C86A0DE1-E004-41AE-8DA6-AEDAD609B863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$663C28C6-BAC2-43F8-8532-0BF2EDF50909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$92F7EEA9-5F2A-4EB8-B49D-1570615C9554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$38EADC5F-BE4F-4381-9028-B425471117CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"452bc38cdda20b7aa04ce144fde2a2a4ca542d27","datavalue":{"value":"7042122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$D0488DED-45B0-42DF-9946-7EA0A397C7B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a118d437360385968d5840b397af382d21e0ea5e","datavalue":{"value":"lossless compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736509$FC804B8C-8319-4162-9EAD-C4EDDDC71224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f09b5231d1500a63c98fde88b36502be9956a155","datavalue":{"value":"grammar-based compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736509$39615991-4B27-4F00-B73E-8F89D20BE3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80b6ab4c1cd966e2c3c7723d9876f1cbe5352dfe","datavalue":{"value":"online algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736509$7ECA4A7E-8405-419B-BD06-101C7A186BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736509$6E245E20-C0F2-4442-9594-123FA4FBCD2C","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":"Q1736509$41179069-BBF3-4829-9862-A1B3DF64E490","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b4f09a0854be4895ece4b379d378fc7d530ed68","datavalue":{"value":"https://doi.org/10.3390/a5020214","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736509$C476F508-A98B-4F26-B062-CDB06F04A093","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a99380652b9ef60118aa1dd3ffe550423e55bad","datavalue":{"value":"W2489658791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$1372C5F7-7C4E-4277-9025-A2014314DA54","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"690e8bdea7ed8b52b8d9b55c3ded00260a983719","datavalue":{"value":"10.3390/A5020214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736509$02E95E98-6DCD-41B7-8A55-DA7E5553E69A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e9123c92b0f90ddd31d5e9dd2ce48e606269c72","datavalue":{"value":{"entity-type":"item","numeric-id":5393963,"id":"Q5393963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57e664c2166e48420a2f60cdd4cf1cfdb079fba","datavalue":{"value":{"amount":"+0.876035749912262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736509$2DC5C379-ADCB-4974-9600-025B3C6C4F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74470260319b6820810c97d49948b106b64ba19b","datavalue":{"value":{"entity-type":"item","numeric-id":5111756,"id":"Q5111756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b2310164f4a6e9e96a08a79bf382659da5ca048","datavalue":{"value":{"amount":"+0.8738298416137695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736509$9C753CBA-2319-4186-BA03-83F4ADE53002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9687d427ff39a8f0b83f1ccc13a9f96c85a1124f","datavalue":{"value":{"entity-type":"item","numeric-id":500975,"id":"Q500975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21f90090dc6436a39817efae5a74ae364d31fb78","datavalue":{"value":{"amount":"+0.8399913907051086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736509$0C92752C-D070-4AEE-8A2D-E00D23CDBE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e65d7f7ad13c66e2c6388f8bf0bdc6c45c503eef","datavalue":{"value":{"entity-type":"item","numeric-id":3550846,"id":"Q3550846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abd091b95effbd724f0c770db245a622ede27cd6","datavalue":{"value":{"amount":"+0.8373432159423828","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736509$99C9EBC2-A537-4605-86CD-FA7822E893E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"603be9f73c44e09b9b245722e4c3fc8bb37f56a8","datavalue":{"value":{"entity-type":"item","numeric-id":4928570,"id":"Q4928570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c02ae97c512691cf1070171f1262375f064de21","datavalue":{"value":{"amount":"+0.8328203558921814","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736509$7942BF4B-8A31-4400-BBD0-9B1D00EF02F5","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736509$D25B312B-93E5-41FD-A81A-23884896AC31","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736509","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736509"}}}}}