Simple Linear Comparison of Strings in V -order

• Autorzy: Alatabbi A. , Daykin J. W. , Rahman M. S. , Smyth W. F.

Identyfikatory

DOI

10.3233/FI-2015-1228

• Języki publikacji: EN

Abstrakty

EN

In this paper we focus on a total (but non-lexicographic) ordering of strings called V - order. We devise a new linear-time algorithm for computing the V -comparison of two finite strings. In comparison with the previous algorithm in the literature, our algorithm is both conceptually simpler, based on recording letter positions in increasing order, and more straightforward to implement, requiring only linked lists.

Słowa kluczowe

EN

algorithm; array; comparison; complexity; data structure; lexicographic order; linear; linked list; V -order; Lyndon word; string; total order; word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 2
• Strony: 115--126
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Alatabbi A.

• Department of Informatics, King’s College London, UK

autor

Daykin J. W.

• Department of Computer Science, Royal Holloway, University of London, UK
• Department of Informatics, King’s College London, UK

autor

Rahman M. S.

• AℓEDA Group, Department of CSE, BUET, Dhaka-1205, Bangladesh

autor

Smyth W. F.

• Algorithms Research Group, Dept. of Computing & Software, McMaster University, Canada School of Engineering & Information Technology, Murdoch University, Australia

Bibliografia

• [1] D. Adjeroh, T. Bell, A. Mukherjee, The Burrows-Wheeler trans- form: data compression, suffix arrays, and pattern matching, Springer (2008) 352 pp.
• [2] Ali Alatabbi, Jacqueline W. Daykin, M. Sohel Rahman, William F. Smyth: Simple Linear Comparison of Strings in V-Order (Extended Abstract).WALCOM 2014: 80-89
• [3] D. Breslauer, R. Grossi and F. Mignosi, Simple real-time constant-space string matching, Proc. 22nd Annual Symposium on Combinatorial Pattern Matching, R. Giancarlo & G.Manzini (eds.), Lecture Notes in Comput. Sci. 6661 (2011) 173-183.
• [4] S. Brlek, J.-O. Lachaud, X. Provenc¸al and C. Reutenauer, Lyndon + Christoffel = digitally convex, Pattern Recognition 42 (10) (2009) 2239-2246.
• [5] M. Chemillier, Periodic musical sequences and Lyndon words, Soft Computing - A Fusion of Foundations, Methodologies and Applications, Springer-Verlag, ISSN 1432-7643 (Print) 1433-7479 (Online), Vol. 8, Issue 9 (September 2004) 611-616.
• [6] M. Chemillier and C. Truchet, Computation of words satisfying the “rhythmic oddity property” (after Simha Arom’s works), Inf. Proc. Lett. 86 (2003) 255-261.
• [7] K.T. Chen, R.H. Fox and R.C. Lyndon, Free differential calculus, IV - The quotient groups of the lower central series, Ann. Math. 68 (1958) 81-95.
• [8] M. Crochemore, J. D´esarm´enien and D. Perrin, A note on the Burrows-Wheeler transformation, Theor. Comput. Sci. 332(1-3) (2005) 567-572.
• [9] M. Crochemore and D. Perrin, Two-way string-matching, J. Assoc. Comput. Mach. 38(3), (1991) 651-675.
• [10] D.E. Daykin, Ordered ranked posets, representations of integers and inequalities from extremal poset problems, Graphs and Order, Proceedings of a Conference in Banff, Canada (1984), NATO Advanced Sciences Institutes Series C: Mathematical and Physical Sciences 147 ( I. Rival (ed.); Reidel, Dordrecht-Boston, 1985) 395-412.
• [11] D. E. Daykin, Algorithms for the Lyndon unique maximal factorization, J. Combin. Math. Combin. Comput. 77 (2011) 65-74.
• [12] T.-N. Danh and D.E. Daykin, The structure of V -order for integer vectors, Congr. Numer. Ed. A.J.W. Hilton. Utilas Mat. Pub. Inc.,Winnipeg, Canada, 113 (1996), 43-53.
• [13] T.-N. Danh and D. E. Daykin, Ordering integer vectors for coordinate deletions, J. London Math. Soc. (2) 55 (1997) 417-426.
• [14] D.E. Daykin and J.W. Daykin, Lyndon-like and V -order factorizations of strings, J. Discrete Algorithms 1 (2003) 357-365.
• [15] D.E. Daykin and J.W. Daykin, Properties and construction of unique maximal factorization families for strings, Internat. J. Found. Comput. Sci. Vol. 19, No. 4 (2008) 1073-1084.
• [16] D. E. Daykin, J. W. Daykin, C. S. Iliopoulos andW. F. Smyth, Generic algorithms for factoring strings, Proc. Memorial Symp. for Rudolf Ahlswede, H. Aydinian, F. Cicalese & C. Deppe (eds.), Lecture Notes in Comput. Sci. Festschrifts “Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede”, 7777 (2013) 402-418.
• [17] D. E. Daykin, J. W. Daykin and W. F. (Bill) Smyth, Combinatorics of unique maximal factorization families (UMFFs), Fund. Inform. 97-3, Special Issue on Stringology, R. Janicki, S. J. Puglisi andM. S. Rahman (eds.) (2009) 295-309.
• [18] D. E. Daykin, J. W. Daykin and W. F. Smyth, String comparison and Lyndon-like factorization using V - order in linear time, Proc. 22nd Annual Symposium on Combinatorial Pattern Matching, R. Giancarlo and G. Manzini (eds.), Lecture Notes in Comput. Sci. 6661 (2011) 65-76.
• [19] D. E. Daykin, J. W. Daykin and W. F. Smyth, A linear partitioning algorithm for Hybrid Lyndons using V -order, Theoret. Comput. Sci. 483 (2013) 149-161.
• [20] J.W. Daykin, C.S. Iliopoulos andW.F. Smyth, Parallel RAM algorithms for factorizing words, Theoret. Comput. Sci. 127 (1994) 53-67.
• [21] J.W. Daykin andW. F. Smyth, A bijective variant of the Burrows-Wheeler transformusing V -Order, Theoret. Comput. Sci. 531 (2014) 77–89.
• [22] J.P. Duval, Factorizing words over an ordered alphabet, J. Algorithms 4 (1983) 363-381.
• [23] F. Gray, Pulse code communication,March 17, 1953. U.S. patent no. 2,632,058.
• [24] C.S. Iliopoulos, Optimal cost parallel algorithms for lexicographical ordering, Purdue University, Tech. Rep. 86-602 (1986).
• [25] C.S. Iliopoulos and W.F. Smyth, Optimal algorithms for computing the canonical form of a circular string, Theoret. Comput. Sci. 92 (1) (1992) 87-105.
• [26] J. K¨arkk¨ainen, P. Sanders and S. Burkhardt, Linear work suffix array construction, J. ACM 53 (6) (2006) 918–936.
• [27] P. Ko and S. Aluru, Space efficient linear time construction of suffix arrays, Proc. 14th Annual Symposium on Combinatorial Pattern Matching (2003) 200–210.
• [28] D.L. Kreher and D.R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press (1998).
• [29] M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983; 2nd Edition, Cambridge University Press, Cambridge, (1997).
• [30] G. Navarro and V. M¨akinen, Compressed full-text indexes, ACM Computing Surveys - CSUR , vol. 39, no. 1, pp. 2-es, (2007).
• [31] G. Nong, S. Zhang and W. H. Chan, Linear suffix array construction by almost pure induced-sorting, Proc. 2009 Data Compression Conf. (2009) 193–202.
• [32] F. Ruskey, Combinatorial Generation (Unpublished book). CiteSeerX: 10.1.1.93.5967, on combinatorics (2003).
• [33] C. Savage, A survey of combinatorial Gray codes, SIAM Rev., vol. 39, no. 4, (1997) 605-629.
• [34] J. Sirén, N. V¨alim¨aki and V. M¨akinen. Indexing finite language representation of population genotypes. Proc. Workshop on Algorithms in Bioinformatics, Springer, Lecture Notes in Comput. Sci. 6833 (2011) 270-281.
• [35] Bill Smyth, Computing patterns in strings, Pearson (2003) 423 pp.