de Bruijn序列查寻表标签的定值构造法  

Algorithms for constructing look-up table labels of de Bruijn sequences using fixed value label

作　　者：谢深泉[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与应用》2008年第19期16-19,38,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.60673193);湖南省重点学科建设项目;湖南省教育厅重点项目(No.07A067)

摘　　要：de Bruijn序列结构是一个查寻表,其核心是它的表标签。因此构造出查寻表标签对于生成de Bruijn序列十分重要。给出一种定值标签构造法,即对大多数节点设定为定值标签,对少部分节点则根据查寻表标签的必要条件指定或任意选定标签。该方法构造的查寻表标签数随着m,n增长而成指数式增长。在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小了。该方法在目前缺乏更好的方法的情况下还是最有效的。The structure of de Bruijn sequences is a look-up table whose kernel is their look-up table labels.So it is very important for generating de Bruijn sequences to construct their look-up table labels.This paper presents an algorithm for constructing m＋1-ary n stage look-up table labels using fixed value,i.e.setting a fixed value label for most of nodes and specifying Or random choosing value label for some few nodes according to some necessary conditions of look-up table labels.The increasing speed of the amount of look-up table labels constructed by the algorithm is exponential by m,n.It seems that the algorithm is efficient,but the speed is not worth to say when comparing with the rapid increasing speed of the amount of look- up table labels themselves.Whatever the algorithm is most efficient now for lack of more efficient algorithms.

关 键 词：DE Bruijn序列 查寻表 查寻表标签 节点标签表 节点链 

分 类 号：O157.4[理学—数学] TN911[理学—基础数学]