Abstract
We give a detailed review of results obtained for a relatively new problem of finding, indexing, and querying character sets, which are called fingerprints in fragments of one- and two-dimensional words, and explain basic ideas used for obtaining these results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. I. Abouelhoda, S. Kurtz, and E. Ohlenbusch, “Replacing suffix trees with enhanced suffix arrays,” J. Discrete Algorithms, 2, No. 1, 53–86 (2004).
A. Amir, A. Apostolico, G. M. Landau, and G. Satta, “Efficient text fingerprinting via Parikh mapping,” J. Discrete Algorithms, 1, No. 5-6, 409–421 (2003).
D. Belazzougui, R. Kolpakov, and M. Raffinot, “Various improvements to text fingerprinting,” J. Discrete Algorithms, 22, 1–18 (2013).
D. Belazzougui, R. Kolpakov, and M. Raffinot, “Indexing and querying color sets of images,” Theor. Comput. Sci., 647, 74–84 (2016).
C.-Y. Chan, H.-I. Yu, W.-K. Hon, and B.-F. Wang, “Faster query algorithms for the text fingerprinting problem,” Inf. Comput., 209, No. 7, 1057–1069 (2011).
G. Didier, T. Schmidt, J. Stoye, and D. Tsur, “Character sets of strings,” J. Discrete Algorithms, 5, No. 2 330–340 (2007).
R. Kolpakov and M. Raffinot, “New algorithms for text fingerprinting,” in: Combinatorial Pattern Matching. 17th Annual Symp., CPM 2006, Barcelona, Spain, July 5–7, 2006. Proceedings, Lect. Notes Comput. Sci., Vol. 4009, Springer, Berlin (2006), pp. 342–353.
R. Kolpakov and M. Raffinot, “New algorithms for text fingerprinting,” J. Discrete Algorithms, 6, No. 2 243–255 (2008).
R. Kolpakov and M. Raffinot, “Faster text fingerprinting,” in: Proc. 15th Int. Symp. on String Processing and Information Retrieval, Lect. Notes Comput. Sci., Vol. 5280, Springer, Berlin (2009), pp. 15–26.
E. M. McCreight, “A space-economical suffix tree construction algorithm,” J. Algorithms, 23, No. 2, 262–272 (1976).
E. Porat, “An optimal bloom filter replacement based on matrix solving,” in: CSR ’09. Proc. Fourth Int. Comput. Sci. Symp. in Russia on Comput. Sci. — Theory and Applications, Lect. Notes Comput. Sci., Vol. 5675, Springer, Berlin (2009), pp. 263–273.
R. Raman, V. Raman, and S. Rao Satti, “Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets,” ACM Trans. Algorithms, 3, No. 4, Art. No. 43 (2007).
E. Ukkonen, “Constructing suffix trees on-line in linear time,” in: Proc. IFIP 12th World Comput. Congr. on Algorithms, Software, Architecture — Information Processing ’92, Vol. 1, North-Holland, Amsterdam (1992), pp. 484–492.
P. Weiner, “Linear pattern matching algorithm,” in: SWAT ’73 Proc. 14th Annual Symp. on Switching and Automata Theory, IEEE Comput. Soc., Washington (1973), pp. 1–11.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 20, No. 6, pp. 3–16, 2015.
Rights and permissions
About this article
Cite this article
Belazzougui, D., Kolpakov, R. & Raffinot, M. Indexing and Querying Character Sets in One- and Two-Dimensional Words. J Math Sci 233, 1–9 (2018). https://doi.org/10.1007/s10958-018-3921-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-018-3921-y