{"entities":{"Q1662548":{"pageid":1673289,"ns":120,"title":"Item:Q1662548","lastrevid":56818521,"modified":"2026-03-23T16:47:30Z","type":"item","id":"Q1662548","labels":{"en":{"language":"en","value":"Suffix-sorting via Shannon-Fano-Elias codes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920517"}},"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":"Q1662548$6DD672E4-1D10-4266-AE7A-028FC72AB0A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f261b3624d5449337a7870708076681e7d31be66","datavalue":{"value":{"text":"Suffix-sorting via Shannon-Fano-Elias codes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662548$C28810B9-3E67-47CC-951C-F9EFD7DBAABC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8362d0dcff56b5f41ff85ffdbefba69c1a203e8","datavalue":{"value":"1461.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$FEEE4F16-2440-4CFB-8FB7-7A58A9849FC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"56097a29ff6e036c1e0caa6ec8a58edf0cb5dc90","datavalue":{"value":{"entity-type":"item","numeric-id":1662547,"id":"Q1662547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$23C25F9B-9D25-416B-8C00-46129F1A3EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ddc5d1242eda8f07756f239fe779d5d1c4255f42","datavalue":{"value":{"entity-type":"item","numeric-id":396694,"id":"Q396694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$61A36D48-780D-4611-A013-B9FDAC3A266E","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":"Q1662548$C7C6B7F8-D34D-4DA1-86BC-F5AAD0C5EC5E","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":"Q1662548$8C556C91-0927-4A1A-9AD2-DC339D633A66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4021a1cbc20e3bc6299c9b68fa8649026b10e6fe","datavalue":{"value":"Summary: Given a sequence \\(T=t_0t_1\\dots t_{n-1}\\) of size \\(n=| T|\\), with symbols from a fixed alphabet \\(\\Sigma\\), \\((|\\Sigma|\\leq n)\\), the suffix array provides a listing of all the suffixes of \\(T\\) in a lexicographic order. Given \\(T\\), the suffix sorting problem is to construct its suffix array. The direct suffix sorting problem is to construct the suffix array of \\(T\\) directly without using the suffix tree data structure. While algorithims for linear time, linear space direct suffix sorting have been proposed, the actual constant in the linear space is still a major concern, given that the applications of suffix trees and suffix arrays (such as in whole-genome analysis) often involve huge data sets. In this work, we reduce the gap between current results and the minimal space requirement. We introduce an algorithm for the direct suffix sorting problem with worst case time complexity in \\(O(n)\\), requiring only \\((1\\frac{2}{3}n\\log n-n\\log|\\Sigma|+O(1))\\) bits in memory space. This implies \\(5\\frac{2}{3}n+O(1)\\) bytes for total space requirment, (including space for both the output suffix array and the input sequence \\(T\\)) assuming \\(n\\leq 2^{32}\\), \\(|\\Sigma|\\leq 256\\), and 4 bytes per integer. The basis of our algorithm is an extension of Shannon-Fano-Elias codes used in source coding and information theory. This is the first time information-theoretic methods have been used as the basis for solving the suffix sorting problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$A7DDEFC7-0AEC-407A-82E3-E511C4303814","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$13E46290-929A-4FB0-B0F1-C3684C468879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$74755238-B193-4634-A29F-196008B0B3D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$4130F34E-45A7-4996-9283-08203180C8D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$5004B28C-AFF8-4F4B-A3B2-A040CA0A3E87","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e87565473bed49034ebe9943090d728fc5dc591","datavalue":{"value":"6920517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$E4E361CE-B3EF-4373-A141-74B0DA9AD122","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"faa54db05fc069e012d42e25b1d7accdda58c8c4","datavalue":{"value":"suffix sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$E2591D45-FB4B-4CE6-885F-A188BB469463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9aef2a311c2eace7c84f21621cad39baa9972d0","datavalue":{"value":"suffix arrays","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$7F6EC934-F61C-485B-8CD4-B4749624460D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d9a3b3d8e31d2bd3ef4b7ebcac2bdf4b0710820","datavalue":{"value":"suffix tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$73F55F8E-97FB-4E10-BD07-342A0F12E3A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecbde79b9cb622ad3d0132d0b9df796d997136d0","datavalue":{"value":"Shannon-Fano-Elias codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$8C966F7B-F863-47EB-AAA7-0D044D8D00E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab316a7276e216d6fa4b79b8b3066898476ec1bf","datavalue":{"value":"source coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662548$BC64BD0A-C4EE-4A3A-B246-CBBDC85A92F6","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":"Q1662548$08CE7372-C6B5-46F7-8DBD-413908752B47","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"48b0b66806d193b5e8ab382b933d1a943dd38c9b","datavalue":{"value":"https://doi.org/10.3390/a3020145","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662548$C65CF55D-181F-47AA-A1DB-1ADB7A2FBE89","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d4fa83004bf7b36d5b82799d0b0e23db9f2a817c","datavalue":{"value":"W2175286270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$89DB4F41-F343-4539-8882-795619CE0D0B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"765e1a7b0cd5402f72cc273dc87f1f94470d841f","datavalue":{"value":{"entity-type":"item","numeric-id":3142586,"id":"Q3142586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$B35D8AA8-75F6-4321-A85E-B634B6EC26DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d14c1b29c5fbf05e07b4587c411d9a05c2be53d2","datavalue":{"value":{"entity-type":"item","numeric-id":2465058,"id":"Q2465058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$A7386879-2BBB-4F25-B337-FE3B015C95AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"171f8563837c8e14cec542dd3d7a7b58dfe05465","datavalue":{"value":{"entity-type":"item","numeric-id":1882475,"id":"Q1882475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$7ECE9478-BB05-4443-AB9E-23EA31C4A1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$0E15C2B5-C8E5-477A-A2DD-39586254AE08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f5fa024f3ceba85e016cdee70373544af599545","datavalue":{"value":{"entity-type":"item","numeric-id":3455222,"id":"Q3455222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$11375118-05D1-4C14-A497-3CBCEEBE88A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1821e1899a3f79ffbfb91244285cdbbd242d95f4","datavalue":{"value":{"entity-type":"item","numeric-id":2569393,"id":"Q2569393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$B1D92D69-1411-4F15-970F-982FC75BDD52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"506456f36bbd438f0883fad9500a97b11a67825e","datavalue":{"value":{"entity-type":"item","numeric-id":4307377,"id":"Q4307377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$8433BB59-CE9A-4935-9945-A5C5F84B18A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4b4505ecee57edec84bced67e5a0d2a405bf689","datavalue":{"value":{"entity-type":"item","numeric-id":876707,"id":"Q876707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$C31A2293-D7F0-4DC5-B0B0-646768864657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f82fa8e72d8118c4a3377a772678fd30695775","datavalue":{"value":{"entity-type":"item","numeric-id":5487881,"id":"Q5487881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$0256666E-F353-4D6E-879B-69C3BBA27720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"719bef5459243b8c90031bc9e7b3db833f9ea8ff","datavalue":{"value":{"entity-type":"item","numeric-id":2569391,"id":"Q2569391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$8DAD44E8-47AF-417A-ABAF-8DF999F301A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b05c6f87c7535b715826e584887e74ed707c67b1","datavalue":{"value":{"entity-type":"item","numeric-id":3603562,"id":"Q3603562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$A9020DF3-3190-45D4-B942-5B90F6E1CC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f027d1ec7583f9af7115e78831caa997ee771ec","datavalue":{"value":{"entity-type":"item","numeric-id":3654373,"id":"Q3654373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$25FBCAA2-1CBD-4A92-80D1-30F92C9434BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0455a2df3010821f082f0a3511066352406ae659","datavalue":{"value":{"entity-type":"item","numeric-id":5713569,"id":"Q5713569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$EB791FED-46F3-4433-99F9-4579693E5133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5e936d3aeea7bbb794139d98f4df27d00b6a20c","datavalue":{"value":{"entity-type":"item","numeric-id":3550827,"id":"Q3550827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$92DA2F63-491F-461E-9EF7-E20A1DB8A2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba8595813b99eaa91c9cda939ad7dfa7537ffbeb","datavalue":{"value":{"entity-type":"item","numeric-id":3637104,"id":"Q3637104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$F7298B3E-B6D3-416F-991F-AD6DFF9CDC2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e62cc4cbf06d380ed60f06780c6abef1e2d3f728","datavalue":{"value":{"entity-type":"item","numeric-id":5428837,"id":"Q5428837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$BD813D93-18A7-493D-81B6-2A523A8E8E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79dc2029103f69444d3b59364c36a013d061321f","datavalue":{"value":{"entity-type":"item","numeric-id":5470696,"id":"Q5470696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$97C3E6D1-34BF-4CB8-BC84-E351AD50F474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d17cfb059f90542ac618356f3d97ceef05ebdd9b","datavalue":{"value":{"entity-type":"item","numeric-id":3666654,"id":"Q3666654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$F29D4CCD-96BF-42BB-816A-8C07E8B845DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52aff9c5eb3c4c80d652d6459a06ff8ec62dd595","datavalue":{"value":{"entity-type":"item","numeric-id":4023085,"id":"Q4023085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662548$9094F812-F73D-48F2-83DD-995F304166E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96ca7f7445781ddd06a39e72803328823005bdb0","datavalue":{"value":"10.3390/A3020145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662548$C192826C-A9DC-4742-881D-EDF5F83BD34F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8255d5482fd9b7ef26c0b4e483a1dd4cd8ab9125","datavalue":{"value":{"entity-type":"item","numeric-id":2465058,"id":"Q2465058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a1334b85f104095c00e7502827804d7799b3d45","datavalue":{"value":{"amount":"+0.8359084129333496","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":"Q1662548$4818B1DD-9704-42FF-AA13-F076209AD3B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd99d6f21e23cd713996ff1917a1946faef73658","datavalue":{"value":{"entity-type":"item","numeric-id":3550836,"id":"Q3550836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce8f1bdbba6597d13262e5d14f0f090991c423c0","datavalue":{"value":{"amount":"+0.8305142521858215","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":"Q1662548$815FB40D-F9AD-4DD6-A35B-868B2ED512AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"460e6a2c7e8a5046320b5c96f57edf01e196e9bf","datavalue":{"value":{"entity-type":"item","numeric-id":2569393,"id":"Q2569393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72d294e5d9cf3183e4fcda63c07e0183f17ca429","datavalue":{"value":{"amount":"+0.8300625085830688","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":"Q1662548$F208B2D4-F9EB-42F3-A8C8-D785B7BEE279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32bed29c0b1e21b62d7c8f99d7b4177a5c138d50","datavalue":{"value":{"entity-type":"item","numeric-id":5428837,"id":"Q5428837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c948fc22ffac1f9d143f85d424edfde233f1f65b","datavalue":{"value":{"amount":"+0.8280725479125977","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":"Q1662548$7F3C1EE5-D1D8-4965-B09C-9287BB18D015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08cb795ab1defdf2a0f12280b1f343e7082d0ef7","datavalue":{"value":{"entity-type":"item","numeric-id":2672235,"id":"Q2672235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06f695ff87cd9cf9db1ec58e84eb800edf897635","datavalue":{"value":{"amount":"+0.8236234188079834","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":"Q1662548$CF927866-1B65-4444-996E-47981496C11D","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":"Q1662548$C0C4A9DF-45B9-40E8-8FE1-9C7CAFB1C542","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1662548","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1662548"}}}}}