A linearly computable measure of string complexity

被引：4

作者：

Becher, Veronica ^{[1
]}

Heiber, Pablo Ariel

机构：

[1] Univ Buenos Aires, Dept Comp, Fac Ciencias Exactas & Nat, RA-1053 Buenos Aires, DF, Argentina

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 438卷

关键词：

ENTROPY; VOLUME;

D O I：

10.1016/j.tcs.2012.03.007

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a measure of string complexity, called I-complexity, computable in linear time and space. It counts the number of different substrings in a given string. The least complex strings are the runs of a single symbol, the most complex are the de Bruijn strings. Although the I-complexity of a string is not the length of any minimal description of the string, it satisfies many basic properties of classical description complexity. In particular, the number of strings with I-complexity up to a given value is bounded, and most strings of each length have high I-complexity. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：62 / 73

页数：12

共 23 条

[1]

Adjeroh D., 2008, The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching

[2]

Asarin E, 2009, LECT NOTES COMPUT SC, V5710, P69, DOI 10.1007/978-3-642-04081-8_6

[3]

Asarin E, 2009, LECT NOTES COMPUT SC, V5813, P13, DOI 10.1007/978-3-642-04368-0_4

[4] On extending de Bruijn sequences [J].