{"entities":{"Q383835":{"pageid":385602,"ns":120,"title":"Item:Q383835","lastrevid":61430604,"modified":"2026-04-10T23:19:33Z","type":"item","id":"Q383835","labels":{"en":{"language":"en","value":"Compressed data structures for strings. On searching and extracting strings from compressed textual data"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6236178"}},"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":"Q383835$DF30D1A1-0C52-4EDA-81A7-B06F6E08108E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00fa0984301829ffcb09150073a7925aa0257ca2","datavalue":{"value":{"text":"Compressed data structures for strings. On searching and extracting strings from compressed textual data","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q383835$B69D8D4F-29BA-4E0F-9884-8B1EBF798B9F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7c6dca6d1498446418032b32bd7824148405fc5","datavalue":{"value":"1298.68015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$460EF94C-EDB8-4263-96DF-38ED195E361B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"91a49dc1d7b1eab75e06b0e90850834170ba292d","datavalue":{"value":"10.2991/978-94-6239-033-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$30D388D4-B648-4806-935D-E8289DEB77C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58e3aa10f916863ee990f95f6f660c826db39820","datavalue":{"value":{"entity-type":"item","numeric-id":261344,"id":"Q261344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$B7D876BC-FD6A-41FF-98E6-AD75D93CAF67","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7738080bfc20434dd7bc87b453b00d8593d94bb8","datavalue":{"value":{"entity-type":"item","numeric-id":357125,"id":"Q357125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$9F39631C-4533-47F3-9E5D-4AB88EF51333","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"deb6cb3450bd256fc635dc32234471403070c2b7","datavalue":{"value":{"time":"+2013-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q383835$724581F0-DCB7-4254-BE5F-C22D10FCB12D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"991b366d262e45ae5b957f99c27d7dfb2e5f6540","datavalue":{"value":"Every two years, the Italian chapter of the EATCS (European Association for Theoretical Computer Science) selects two Italian PhD theses to be published by Atlantis Press. This book is Rossano Venturini's thesis, which was understandably judged to be the best on algorithms, automata, complexity or game theory from 2010 to 2012. It contains results from five of the author's papers [\\textit{P. Ferragina} et al., Lect. Notes Comput. Sci. 5757, 420--431 (2009; Zbl 1256.68055); \\textit{P. Ferragina} et al., SIAM J. Comput. 42, No. 4, 1521--1541 (2013; Zbl 1276.68069); \\textit{P. Ferragina} and \\textit{R. Venturini}, Theor. Comput. Sci. 372, No. 1, 115--121 (2007; Zbl 1110.68029); \\textit{P. Ferragina} et al., ACM J. Exp. Algorithm. 13, Article No. 1.12, 31 p. (2009; Zbl 1284.68255); \\textit{P. Ferragina} and \\textit{R. Venturini}, ACM Trans. Algorithms 7, No. 1, Paper No. 10, 21 p. (2010; Zbl 1295.68108)]. Although the book focuses on the problems addressed and solutions offered in these papers -- and thus should probably not be considered as a regular textbook -- Chapters 2 and 6 in particular provide a brief but insightful introduction to the theory and practice of compressed data structures for strings. It could serve as an excellent example thesis and source of research topics for other PhD students, although they should still of course check work done since it was written: e.g., the problem of linear-time BWT construction with \\(O(n \\log \\sigma)\\) bits of auxiliary space has now been solved by \\textit{D. Belazzougui} [``Linear time construction of compressed text indices in compact space'', in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14. New York, NY: ACM Press. 148--193 (2014; \\url{doi:10.1145/2591796.2591885})], and SDSL (Succinct Data Structure Library, \\url{https://github.com/simongog/sdsl-lite}) has probably replaced the Pizza \\& Chili website as the main repository of implementations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q383835$D396BCEC-B9B4-400C-9AB7-439E6B0F8AA7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"190982f8ef5a79efe62543507a2f94a300470907","datavalue":{"value":{"entity-type":"item","numeric-id":390357,"id":"Q390357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$80F28268-3F36-4AC9-B10B-C9E0C818C41E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$62F36BA7-4955-42DA-AB0E-CB9A3DF6CD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$E00859DC-F2F3-423F-9F65-073C3035A0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$6093B296-B5DC-4BFC-B3BA-614DB256B9A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$7DB3FA39-850B-4657-AEE0-0CF3E741921B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a949d7a6e72784eb53409e2ff8b59f49fe4f062","datavalue":{"value":"68U15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$CB69BE84-61C5-4AD8-AEE3-F1CB29E775D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$303A4451-3546-4E44-89C3-14329079CAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$FAF0392E-AA3A-4F80-BC52-FDD278731734","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"189de111cfbd6f4c18e1eb92278e725b65e0fe11","datavalue":{"value":"6236178","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$057310E2-347F-4FCD-B421-83D849A91DD7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8246e48eb52d9bd4d0bcc25c0db52becc67792c7","datavalue":{"value":"compressed data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q383835$BAC50217-279A-48F3-A5C0-1E16572A6A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f375d9831de7dbe7071a94820ee318a076eb222","datavalue":{"value":"strings","type":"string"},"datatype":"string"},"type":"statement","id":"Q383835$2748BDC6-344B-4672-8EEC-459385D53027","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"317a4a1a0195a920845222ef0e3a0579f8cae26f","datavalue":{"value":{"entity-type":"item","numeric-id":34994,"id":"Q34994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$002411A1-C870-4B18-A743-D6D6C6AFA7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4202bf8e68d8955fdcf9ece9f20c16783115530d","datavalue":{"value":{"entity-type":"item","numeric-id":35099,"id":"Q35099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$138BD4C3-F97A-4EFE-B20A-566AB3741095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q383835$0BBC1907-F598-439A-B2A6-A796133E626E","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":"Q383835$6D2BBAFE-47CC-413B-8331-E1932B5E4A05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12a561cb6c56c9d9b823fc9d7a4c513c4d5ac8b2","datavalue":{"value":"https://doi.org/10.2991/978-94-6239-033-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q383835$C018142C-AB5B-4E7C-B8F5-96C3DAF101E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10b3e4e709ff53668d181dfdf55b56132256b9f2","datavalue":{"value":"W2498042296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q383835$7F027A74-67F4-49F0-925D-AD59D656EF59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbea4984c7c0110257a152f31f602d6d6c20e44f","datavalue":{"value":{"entity-type":"item","numeric-id":3575253,"id":"Q3575253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b68bf722bd80873b11ff479c85ad68b05af6f49","datavalue":{"value":{"amount":"+0.9317812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$69CD6013-5832-40F8-AAD5-3DE05F421805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24c07c22482c6cb8f7238dab877a30fa8b651ab2","datavalue":{"value":{"entity-type":"item","numeric-id":6053405,"id":"Q6053405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2572e9426ed2f0e54a58129841bfb9044b361b0a","datavalue":{"value":{"amount":"+0.90711683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$C474FAAE-EE2C-483A-B0B2-1E9600504147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc9ceb7c28a27de83cafd663becaf9a1101b2418","datavalue":{"value":{"entity-type":"item","numeric-id":5470696,"id":"Q5470696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb69c187d53bc2b128e47a2745a5f625fe888c63","datavalue":{"value":{"amount":"+0.89842236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$6A672A65-027C-4544-A35F-AD3D71278E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e157507a372484172bff4a4ed7bc25bdc4de010f","datavalue":{"value":{"entity-type":"item","numeric-id":5449529,"id":"Q5449529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18ab8bd2217ad5794ff6d11a6bc7234279c9d70d","datavalue":{"value":{"amount":"+0.8972205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$B25C51F1-0C58-49CE-96A6-597BE8162472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c08a59f3b0f07c811033127cedacfe68cf116e3","datavalue":{"value":{"entity-type":"item","numeric-id":5961970,"id":"Q5961970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18ab8bd2217ad5794ff6d11a6bc7234279c9d70d","datavalue":{"value":{"amount":"+0.8972205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$810F9D7E-72C4-4A78-A3A9-BB4A7A95FC3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dec215b9357582a91a9d69d91916a979aa2f45c4","datavalue":{"value":{"entity-type":"item","numeric-id":4472515,"id":"Q4472515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0ed9b85a7a2269972bf2020e0ac268f714de400","datavalue":{"value":{"amount":"+0.893262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$58E59C51-2263-4097-AE8E-C4D98206D24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13e63e79d515d3d1b3896deb4f57fe2bc1e19b71","datavalue":{"value":{"entity-type":"item","numeric-id":6111589,"id":"Q6111589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ad4706aab7a197061747821114eeaf2892c0729","datavalue":{"value":{"amount":"+0.89312756","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$1F699CCB-A537-4693-9971-023B5FCF1EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61c9483eb7465464287ea66513ce0af368465af","datavalue":{"value":{"entity-type":"item","numeric-id":3192007,"id":"Q3192007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6cd3f760461f30049fe799218c5f468f6a9b991","datavalue":{"value":{"amount":"+0.8922908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$2BDB2B28-6807-443D-B359-22A87BB084D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a3d4ea16c86464da0382a3ffea75571c718f75a","datavalue":{"value":{"entity-type":"item","numeric-id":4392484,"id":"Q4392484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aef7a52049f05d46a35e8199e52602effcd9367a","datavalue":{"value":{"amount":"+0.8878721","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q383835$18FF99F8-7F36-4422-A2F3-993E10F38043","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Compressed data structures for strings. On searching and extracting strings from compressed textual data","badges":[]}}}}}