{"entities":{"Q1662518":{"pageid":1673259,"ns":120,"title":"Item:Q1662518","lastrevid":56779329,"modified":"2026-03-23T14:06:07Z","type":"item","id":"Q1662518","labels":{"en":{"language":"en","value":"Linear-time text compression by longest-first substitution"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920485"}},"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":"Q1662518$5118ABFD-461D-4152-8AA0-4E0EBE3E7617","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f0fc7cb6e48798c936bf81ca880d68d8c7c7adaa","datavalue":{"value":{"text":"Linear-time text compression by longest-first substitution","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662518$0B0B5547-13D8-4EA9-83D7-F37724BB1EBC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b12fcfed84012a56e880593819c8b050d4c3dfa2","datavalue":{"value":"1445.68365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$D6BCA4EA-C613-4A12-A295-2575A9FA373C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb8177f53b506ccd6a5e11af159567ae013da031","datavalue":{"value":{"entity-type":"item","numeric-id":1662516,"id":"Q1662516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$07972767-625F-4AB7-AADF-54DBB9C2358F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f1cdf9c209db229e3386fe9c7a37bf9ab08ad32","datavalue":{"value":{"entity-type":"item","numeric-id":313753,"id":"Q313753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$0C8C571B-4421-4E03-83E7-1A2BCEC07D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4edc45c3d84b898eeb448befcc7fe95b9efff6f3","datavalue":{"value":{"entity-type":"item","numeric-id":313750,"id":"Q313750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$899B09BF-6DA0-4DB8-9C7E-786735D68A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1204d2b183067006ee61e052c2222112e64d1d35","datavalue":{"value":{"entity-type":"item","numeric-id":1662517,"id":"Q1662517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$A41D777A-B59F-4B4F-B9C4-37FA2997E324","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":"Q1662518$F4CA1FCB-4442-44FE-A224-A0E0FFE1C6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f919044541ff85168c0a049d263045de77e3a296","datavalue":{"value":{"entity-type":"item","numeric-id":496551,"id":"Q496551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$CF50EE9D-8289-4FEC-9FF4-FE5AD7B8BEE2","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":"Q1662518$22552456-2BD0-4227-8679-466663E1BB44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"431a43c637c8a2264e4d8145aa5a3c26bfb96786","datavalue":{"value":{"time":"+2018-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1662518$32AB63DC-3BF9-4C05-93B3-64E2B998CBD9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"78dd24a6f0cd41b07e6e33d405d1b50d72e728de","datavalue":{"value":"Summary: We consider grammar-based text compression with \\textit{longest first substitution} (LFS), where non-overlapping occurrences of a longest repeating factor of the input text are replaced by a new non-terminal symbol. We present the first linear-time algorithm for LFS. Our algorithm employs a new data structure called \\textit{sparse lazy suffix trees}. We also deal with a more sophisticated version of LFS, called LFS2, that allows better compression. The first linear-time algorithm for LFS2 is also presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662518$473BB007-75B3-470D-A8A9-0420BB22566C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$1284801B-F2C5-4512-BB21-AC064E47C345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$38DF4A97-DBD2-4A46-87C9-9766AC4D86A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$E99CA882-4011-46E0-A9F0-752649737E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$90F6C2F3-615A-41D5-895E-9713CE35EE68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53596bf7aec99c8a1e02ac05c6258d6fff11e78b","datavalue":{"value":"6920485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$96A82E50-DEEE-411B-940F-198EB45DA373","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84d08c99c76166fd89d212473a14f7d9bb79eb30","datavalue":{"value":"grammar-based text compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662518$4F6A0C3E-E232-4EAB-8F23-84FBD5BDFFCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5ee40f8f543659211b421d3bc4734492ddad5ca","datavalue":{"value":"suffix trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662518$6BB9F420-6D0B-4610-93C9-8F646FFADABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662518$23BED054-1D5F-4A3A-B042-138B06EC80E6","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":"Q1662518$169F0985-9E05-44DB-8FD8-D34436F10328","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aefef684df0dede57f07d142a33cddd9e1ada771","datavalue":{"value":"https://doi.org/10.3390/a2041429","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662518$7BD22FCD-EEAB-4705-A26A-3DAAA6F6DF45","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5b0c7511c6262050622f52e6df707f1c5fd3d868","datavalue":{"value":"W2085254467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$3F033EB0-6401-4725-9AB4-3CA30E50E30A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9877e7545b0712220c74d963ed8195b00ef3878d","datavalue":{"value":{"entity-type":"item","numeric-id":1874240,"id":"Q1874240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$E5D18C37-3BB1-435A-AA6D-1448A8C2C0B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"634152992dfd981e624e589f56bcf8bbcec2b3b4","datavalue":{"value":{"entity-type":"item","numeric-id":1402213,"id":"Q1402213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$752CBDE1-81AD-4C75-8889-013E4E8A8F7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e90d0777849a94de122d696ad5d535fcd2dd25ee","datavalue":{"value":{"entity-type":"item","numeric-id":3506925,"id":"Q3506925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$420C7457-FE29-4C79-86D4-09ACE24C71BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79122641c5cb50a2f50968ca65ff8014e332d5fc","datavalue":{"value":{"entity-type":"item","numeric-id":1006070,"id":"Q1006070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$D7539585-93B2-44CD-A40A-6E2F09760516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1e036d83bacaa6af1d0b4f51814d957f070dee","datavalue":{"value":{"entity-type":"item","numeric-id":5390005,"id":"Q5390005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$1B99B61F-DDB9-4F4D-83F4-F60A6D28F21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9eda11f38c86729dc76e91ab75429a76112f60fd","datavalue":{"value":{"entity-type":"item","numeric-id":5414581,"id":"Q5414581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$1B806AF5-F556-4FC1-910D-62D2CCC04F16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d47ec4bf230b762d5c82f8bac81eddabc36456","datavalue":{"value":{"entity-type":"item","numeric-id":4386970,"id":"Q4386970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$E7B7B58E-26DC-4F88-9077-7B362AED7563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"575f711eda7323d4ce758ae488440fb4b6149690","datavalue":{"value":{"entity-type":"item","numeric-id":465689,"id":"Q465689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$B44914CE-0FB4-4636-B263-AE0D50F1F87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cc19e791edae5e8627a6e4d51b2d96428236e6","datavalue":{"value":{"entity-type":"item","numeric-id":4503585,"id":"Q4503585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$AD681FD0-A446-4A94-8347-DF7E52234D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e57fccc8c00238fd458ec81341321c0921c881c","datavalue":{"value":{"entity-type":"item","numeric-id":4174617,"id":"Q4174617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$3C88F6D9-9402-4A99-AD6B-AD675597E2D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbed00ea24f0743b01f5dd8e7558b7b77151cdd2","datavalue":{"value":{"entity-type":"item","numeric-id":4501756,"id":"Q4501756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$D15FAC1A-2433-40B8-A183-E6B48EC5CCD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5cd6da1c6efd56e67d3d891405501faf884b29b","datavalue":{"value":{"entity-type":"item","numeric-id":2569418,"id":"Q2569418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$7B654E16-C56D-445D-A88D-CCE7CF8A127B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4398a001fabea33eee52a30a71cfd3a06816389b","datavalue":{"value":{"entity-type":"item","numeric-id":1401326,"id":"Q1401326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$92CB0074-284B-46C8-9FA0-57461F9F93F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88d206d4cbc8d8e320cb9ec4bf8947ea28927767","datavalue":{"value":{"entity-type":"item","numeric-id":4158937,"id":"Q4158937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$16015EFB-5718-44D8-9E58-B207A90462A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f33b467ab72277e3a9cbcd40ce9faa12b2d2a03","datavalue":{"value":{"entity-type":"item","numeric-id":5897137,"id":"Q5897137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$D8F7BD2A-6248-497C-A681-804B46B4A471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d8bfe2b1db5784579aa52b41e4fb8610eb152ae","datavalue":{"value":{"entity-type":"item","numeric-id":4952646,"id":"Q4952646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$0CFCBDDB-7768-416D-856B-4ECAE01F839D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d13f9f67ee9c12462b09322feae7787641afc07f","datavalue":{"value":{"entity-type":"item","numeric-id":1897476,"id":"Q1897476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$77E76DA9-921B-4040-9481-A9A63DFC8978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5a3bf58d5585976613feb0e5f6bc6bfd81aae90","datavalue":{"value":{"entity-type":"item","numeric-id":1913702,"id":"Q1913702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$12FFB4BF-1E4B-4201-BEAA-9D0C99600488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e4bdd5a190d0780fdaead3c16941942ecd87517","datavalue":{"value":{"entity-type":"item","numeric-id":4737203,"id":"Q4737203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662518$04BBB1F3-2038-4D69-A7FA-D9C323AFF89E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce9ab5d54848a12a67d630f62f364373a0114df0","datavalue":{"value":"10.3390/A2041429","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662518$246DB647-48D3-40D2-8510-7D2883C31B56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf039272abd10e03d555c8abc1d544d1b2690856","datavalue":{"value":{"entity-type":"item","numeric-id":5897137,"id":"Q5897137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"844740bb391359d7d98f6b1dbddb7f5605495aa8","datavalue":{"value":{"amount":"+0.907849371433258","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":"Q1662518$BA7DDCEA-9DF7-44F9-8583-9CF187DAD2D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c089765d248299b24c129c9bf44edf612a6b7d5c","datavalue":{"value":{"entity-type":"item","numeric-id":3840319,"id":"Q3840319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91b341b232e2f11c5429b699fa0ae40852730281","datavalue":{"value":{"amount":"+0.8000139594078064","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":"Q1662518$2C0208DC-AE28-4512-B457-E6FFCC7192B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20e03df0c857da1942c440a1d0c7db3fcdea22ea","datavalue":{"value":{"entity-type":"item","numeric-id":5110882,"id":"Q5110882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24a9f2af1ea0d5b128acb6290d53004aef5616c2","datavalue":{"value":{"amount":"+0.8000138998031616","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":"Q1662518$8FF15901-13F8-4795-8759-57FD1019DC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8468bb0331a509af068d4ed59d780d75ddcde3f","datavalue":{"value":{"entity-type":"item","numeric-id":4913725,"id":"Q4913725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5551bf1867d9f4e119a3fd28dc08bd673da1c5b2","datavalue":{"value":{"amount":"+0.7987454533576965","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":"Q1662518$86DEA727-925A-4275-B9AB-64057C8900A2","rank":"normal"},{"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":"16641df712bd3090197683f37f7c371b28f105fc","datavalue":{"value":{"amount":"+0.7916253805160522","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":"Q1662518$D35D911C-1174-49BD-81AA-2EF299563277","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":"Q1662518$0ACE620D-C430-4DDB-A832-2BB4F54D8F14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1662518","badges":[]}}}}}