{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T19:57:19Z","timestamp":1716494239530},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T00:00:00Z","timestamp":1427241600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00453-015-9990-0","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T15:02:45Z","timestamp":1427209365000},"page":"1099-1122","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Compressed String Dictionary Search with Edit Distance One"],"prefix":"10.1007","volume":"74","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"issue":"2","key":"9990_CR1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1006\/jagm.2000.1104","volume":"37","author":"A Amir","year":"2000","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms 37(2), 309\u2013325 (2000)","journal-title":"J. Algorithms"},{"issue":"4","key":"9990_CR2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Trans. Algorithms 7(4), 52 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9990_CR3","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/s00453-012-9726-3","volume":"69","author":"J Barbay","year":"2014","unstructured":"Barbay, J., Claude, F., Gagie, T., Navarro, G., Nekrich, Y.: Efficient fully-compressed sequence representations. Algorithmica 69(1), 232\u2013268 (2014)","journal-title":"Algorithmica"},{"key":"9990_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Faster and space-optimal edit distance \u201c1\u201d dictionary. In: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 154\u2013167 (2009)","DOI":"10.1007\/978-3-642-02441-2_14"},{"key":"9990_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Improved space-time tradeoffs for approximate full-text indexing with one edit error. Algorithmica (2014). doi: 10.1007\/s00453-014-9873-9","DOI":"10.1007\/s00453-014-9873-9"},{"key":"9990_CR6","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pp. 181\u2013192 (2012)","DOI":"10.1007\/978-3-642-33090-2_17"},{"issue":"4","key":"9990_CR7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2635816","volume":"10","author":"D Belazzougui","year":"2014","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. ACM Trans. Algorithms 10(4), 23 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"9990_CR8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Venturini, R.: Compressed string dictionary look-up with edit distance one. In: Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 280\u2013292 (2012)","DOI":"10.1007\/978-3-642-31265-6_23"},{"key":"9990_CR9","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Venturini, R.: Compressed static functions with applications. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 229\u2013240 (2013)","DOI":"10.1137\/1.9781611973105.17"},{"issue":"7","key":"9990_CR10","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"9990_CR11","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Ga\u0327sieniec, L.: Approximate dictionary queries. In: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, pp. 65\u201374. Springer (1996)","DOI":"10.1007\/3-540-61258-0_6"},{"issue":"1\u20132","key":"9990_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0020-0190(00)00079-X","volume":"75","author":"GS Brodal","year":"2000","unstructured":"Brodal, G.S., Srinivasan, V.: Improved bounds for dictionary look-up with one error. Inf. Process. Lett. 75(1\u20132), 57\u201359 (2000)","journal-title":"Inf. Process. Lett."},{"key":"9990_CR13","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"9990_CR14","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 30\u201339 (2004)"},{"key":"9990_CR15","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"9990_CR16","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Gil, J., Matias, Y., Pippenger, N.: Polynomial hash functions are reliable (extended abstract). In: Proceeding of the 19th International Colloquium on Automata, Languages and Programming (ICALP), pp. 235\u2013246 (1992)","DOI":"10.1007\/3-540-55719-9_77"},{"key":"9990_CR17","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21, 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"9990_CR18","unstructured":"Fano, RM.: On the number of bits required to implement anassociative memory. Memorandum 61, Computer Structures Group, Project MAC (1971)"},{"key":"9990_CR19","first-page":"12","volume":"13","author":"P Ferragina","year":"2008","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: from theory to practice. ACM J. Exp. Algorithmics 13, 12 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"4","key":"9990_CR20","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"1","key":"9990_CR21","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9990_CR22","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1868237.1868248","volume":"7","author":"P Ferragina","year":"2010","unstructured":"Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Trans. Algorithms 7(1), 10 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9990_CR23","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"9990_CR24","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 317\u2013326 (2001)","DOI":"10.1007\/3-540-44693-1_28"},{"issue":"2","key":"9990_CR25","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"9990_CR26","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows\u2013Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"9990_CR27","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9990_CR28","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full text indexes. ACM Comput. Surv. 39(1), 2 (2007)","journal-title":"ACM Comput. Surv."},{"key":"9990_CR29","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E., Gog, S., K\u00fcgel, A.: Computing matching statistics and maximal exact matches on compressed full-text indexes. In: SPIRE, pp. 347\u2013358 (2010)","DOI":"10.1007\/978-3-642-16321-0_36"},{"key":"9990_CR30","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal bloom filter replacement. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 823\u2013829 (2005)"},{"issue":"4","key":"9990_CR31","first-page":"53","volume":"7","author":"LMS Russo","year":"2011","unstructured":"Russo, L.M.S., Navarro, G., Oliveira, A.L.: Fully compressed suffix trees. ACM Trans. Algorithms 7(4), 53 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"9990_CR32","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9990_CR33","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"IH Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers, Burlington (1999)"},{"issue":"1","key":"9990_CR34","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1006\/jagm.1997.0875","volume":"25","author":"AC-C Yao","year":"1997","unstructured":"Yao, A.C.-C., Yao, F.F.: Dictionary look-up with one error. J. Algorithms 25(1), 194\u2013202 (1997)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9990-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9990-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9990-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9990-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9990"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9990-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,25]]}}}