-Order: New combinatorial properties & a simple comparison algorithm

详细信息    查看全文

• 作者：Ali Alatabbi^a ; ^{ali.alatabbi@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Jacqueline W. Daykin^a ; ^b ; ^{jackie.daykin@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; ^{jackie.daykin@rhul.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Juha Kä ; rkkä ; inen^c ; ^{juha.karkkainen@cs.helsinki.fi" class="auth_mail" title="E-mail the corresponding author} ; M. Sohel Rahman^d ; ^{msrahman@cse.buet.ac.bd" class="auth_mail" title="E-mail the corresponding author} ; W.F. Smyth^a ; ^e ; ^f ; ^{smyth@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Combinatorics ; Experiments ; Lexorder ; Linear ; On-line algorithm ; Optimal ; String comparison ; VV-comparison ; VV-order
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：41-46
• 全文大小：494 K

文摘

class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303158&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303158&_rdoc=1&_issn=0166218X&md5=d41360cd20749e79722e3ae0f1b825d5" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303158&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303158&_rdoc=1&_issn=0166218X&md5=d41360cd20749e79722e3ae0f1b825d5" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$-order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows–Wheeler transform. Efficient class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303158&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303158&_rdoc=1&_issn=0166218X&md5=d41360cd20749e79722e3ae0f1b825d5" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$-ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303158&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303158&_rdoc=1&_issn=0166218X&md5=d41360cd20749e79722e3ae0f1b825d5" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$-order, then explore the computational consequences; in particular, a fast, simple on-line class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303158&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303158&_rdoc=1&_issn=0166218X&md5=d41360cd20749e79722e3ae0f1b825d5" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$-order comparison algorithm that requires no auxiliary data structures.