{"entities":{"Q2004905":{"pageid":2015647,"ns":120,"title":"Item:Q2004905","lastrevid":56709684,"modified":"2026-03-19T02:25:36Z","type":"item","id":"Q2004905","labels":{"en":{"language":"en","value":"Lyndon factorization algorithms for small alphabets and run-length encoded strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7257190"}},"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":"Q2004905$D3E24922-4591-42A4-8BCA-257204CA1E1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ea9a2cfcc839c696f5bccd228742ed1a84ba589","datavalue":{"value":{"text":"Lyndon factorization algorithms for small alphabets and run-length encoded strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2004905$80273FAE-9FF4-43C7-BC81-0EE8295827AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2fde1d79a0e9d929d564dc218f520589f37df9ab","datavalue":{"value":"1461.68266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004905$93BA811E-A2BC-4D98-B018-3CBE4AC87411","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a68ae0a15887415c5cd5e13f37e6debaef92fc26","datavalue":{"value":{"entity-type":"item","numeric-id":2004904,"id":"Q2004904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$2F3E5222-7905-49DB-BD36-90C2B977D840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1fb937db60a8f7be4054881cd8f009aee57c518","datavalue":{"value":{"entity-type":"item","numeric-id":401469,"id":"Q401469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$C88D22C0-70B5-4D8B-9678-E54D7887BFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8d2d335ffbea0a5cfe9e309f2069474d0aade45","datavalue":{"value":{"entity-type":"item","numeric-id":414444,"id":"Q414444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$E018883B-4236-4E22-8EEC-A9DF7B9BDEF4","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":"Q2004905$9631D2AD-5230-4EA1-AAA6-9716DB0E5B19","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7781abd2a97958fd1da5210c5f6f23fc30a06aa4","datavalue":{"value":{"time":"+2020-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2004905$F64D2233-DFD1-437A-8939-B43BC3936B71","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3583813a88dfc1add20bc4ddafa4ba2a6b7b5d7","datavalue":{"value":"Summary: We present two modifications of Duval's algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string \\(R\\) of length \\(\\rho\\), the other algorithm computes the Lyndon factorization of \\(R\\) in \\(O(\\rho)\\) time and in constant space. It is shown by experimental results that the new variations are faster than Duval's original algorithm in many scenarios.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004905$A8C0CBEB-C6C9-4362-926C-EE064ACBD3B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004905$A139441D-883D-44A7-88A3-04459B2291B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"848ac891c5ea3897dd3d6eda6aa9cc89bf576561","datavalue":{"value":"7257190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004905$9388B808-0AA8-442A-BC3F-E252FD3381F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88fa40ef7fccc550b4c7d1004335ce6c676205c6","datavalue":{"value":"Lyndon factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004905$8BC2C581-BAC1-445F-BCE3-347799AEEBEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfe87d9c5acf813f3aee69660faa8f65c2998584","datavalue":{"value":"string algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004905$17C91FB8-AE57-4B88-8056-3AF1A382FE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd11eb2a20dd4d0383bd1c9fcd72e73b614872a3","datavalue":{"value":"run-length encoding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004905$31CA17F4-790C-4C42-B39C-91AD98C5B087","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":"Q2004905$0DC79D94-81FC-4922-9C5A-A2CF991E7CF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7a805c7822da6bbb92fddc590d709d53c252ec6","datavalue":{"value":"https://doi.org/10.3390/a12060124","type":"string"},"datatype":"url"},"type":"statement","id":"Q2004905$58E09F67-8D4D-47F2-9F9A-C78F86C872D7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19b0026a2462300935f00f44f6e78cf0b8d92d85","datavalue":{"value":"W2952991946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004905$EFB1BC6C-61D6-4377-A773-0584DBA2FD03","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b0dbb5b4b782cb58543c829657352a03e93901b","datavalue":{"value":{"entity-type":"item","numeric-id":5895760,"id":"Q5895760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$934964F8-EB02-428C-AEC1-332602273E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fc288e866393acd30d2070573aa2553031b41d1","datavalue":{"value":{"entity-type":"item","numeric-id":5300835,"id":"Q5300835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$47DECF3D-4B75-4AD8-9585-92212F8E4528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99627d0a96e3b61b0ecca4f33b58ced384cb3b50","datavalue":{"value":{"entity-type":"item","numeric-id":3315005,"id":"Q3315005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$2CB1F049-19E7-4089-A37F-BEAA611F9B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b04dab5fd179b46e1ae30dfb865940ab15d13e37","datavalue":{"value":{"entity-type":"item","numeric-id":4327381,"id":"Q4327381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$5F2A91C3-6A9C-4C06-94CF-63140FBECAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a16936077dbf5bbc681d243562a084d7e582aa5","datavalue":{"value":{"entity-type":"item","numeric-id":5506326,"id":"Q5506326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$DD8138CA-D6A0-4502-B84E-2996AE6E54BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8e5150ddbe71dacdf50b0bfed443d1c4d9562c1","datavalue":{"value":{"entity-type":"item","numeric-id":507399,"id":"Q507399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$3F3D71F0-E674-450C-A77A-2B5875F4376E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d6670d23bd00bdf3d833af7ceeff5d5a1671f7d","datavalue":{"value":{"entity-type":"item","numeric-id":4928569,"id":"Q4928569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$078B8449-DB58-40FF-B1D3-12E9E1C99023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42b10886ca8b4810e91e18ed9a8c6b352daf84dc","datavalue":{"value":{"entity-type":"item","numeric-id":4341774,"id":"Q4341774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$6BC385F2-1C60-45F4-8A44-B4FEA51B0011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96d35d840059b8639ee2c55d8f885ab1d111f9ea","datavalue":{"value":{"entity-type":"item","numeric-id":990135,"id":"Q990135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$33C8247C-9D1F-40C6-9EF0-3F936E9ADF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3250026770e6ee2d036ed8fc494faa798419e673","datavalue":{"value":{"entity-type":"item","numeric-id":5463398,"id":"Q5463398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004905$56BF3B04-CDB0-44F1-9537-E8B11377556D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66aa7ce117a0c51454a2baff21e79aeee7693496","datavalue":{"value":"10.3390/A12060124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004905$2DDAF735-B1DC-4B66-BFF3-0A27B2CDB267","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67cce4fd269d8c5628fdc51192f0381de9f0560a","datavalue":{"value":{"entity-type":"item","numeric-id":428842,"id":"Q428842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0872189e897a4dca912a4ca58cfe294c80128d51","datavalue":{"value":{"amount":"+0.8634994","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":"Q2004905$5C5D15C7-B0C9-42CD-A14D-46A433D4309D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d43a4dcfccad1ccd7ca4bcb032bc4bf340f72df0","datavalue":{"value":{"entity-type":"item","numeric-id":507399,"id":"Q507399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e68c5ddf308882532ce13caf4fdda0bf876aedb8","datavalue":{"value":{"amount":"+0.8493417","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":"Q2004905$2C93F47B-500D-4E35-8D4C-9ABF881DC013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5335b78b6ca10dd5658fc308f30a2af4ab96c2f3","datavalue":{"value":{"entity-type":"item","numeric-id":2402270,"id":"Q2402270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3e89dcd801c13a792c530338543612febca0aa6","datavalue":{"value":{"amount":"+0.8489648","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":"Q2004905$DF1B4A67-7E9E-4F4D-8138-C19BFBC845E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a189dcf4a453b30446f4f5ea49a6879bd2f2277b","datavalue":{"value":{"entity-type":"item","numeric-id":2922642,"id":"Q2922642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3e89dcd801c13a792c530338543612febca0aa6","datavalue":{"value":{"amount":"+0.8489648","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":"Q2004905$39E47DF7-EC0D-4697-890B-75A899F20C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1046ba33d3e1e4d6edb8a88e0c7c613e76796a67","datavalue":{"value":{"entity-type":"item","numeric-id":1711413,"id":"Q1711413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2798598775357c75c3c9b33263d610a8a245eba","datavalue":{"value":{"amount":"+0.84883714","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":"Q2004905$5CCBE0F7-C8A8-421D-92A0-F7333F9AA475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"746c2cb3ae9efbd425a8da098d435d0901a02925","datavalue":{"value":{"entity-type":"item","numeric-id":1827280,"id":"Q1827280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95f92ec83ab7b802bc78e08648d10f20613f7032","datavalue":{"value":{"amount":"+0.8415532","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":"Q2004905$4B33F982-709F-411C-BC5C-8D01F4CD6927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5f5fc66b49e9c6e99dff0d2513fb5b0c1ef4f3","datavalue":{"value":{"entity-type":"item","numeric-id":4915247,"id":"Q4915247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cc21ca9bc27d19dc1e997d5cd8f9462db4358ed","datavalue":{"value":{"amount":"+0.8393585","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":"Q2004905$1ED0C0E1-911B-4252-8974-01A82E2A3563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"451350f307c22752826389cfb09ce70296c2e148","datavalue":{"value":{"entity-type":"item","numeric-id":405567,"id":"Q405567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c3c9aeab1181c9b5e91d18fd9caf756e0ba83b9","datavalue":{"value":{"amount":"+0.8364736","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":"Q2004905$AD5DFA42-A61A-4ABD-84E5-1E26C128CE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33721fb20528e5131ce61a351ea934033e28eb94","datavalue":{"value":{"entity-type":"item","numeric-id":2326384,"id":"Q2326384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"265a353b9c9dc437bd964a26a505045e8fe61aff","datavalue":{"value":{"amount":"+0.83188856","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":"Q2004905$14287B15-F087-42ED-941B-D737D18A8DC3","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":"Q2004905$8C535B1D-F56B-4999-9E53-1C34EF4C191C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2004905","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2004905"}}}}}