de Bruijn序列查寻表标签的末位基准构造法  

Algorithms for Constructing Look-up Table Labels of de Bruijn Sequences Based on Value of Last Character of Node

作　　者：谢深泉[1,2] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105 [2]广东培正学院计算机信息管理系,广东广州510830

出　　处：《小型微型计算机系统》2009年第9期1819-1823,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673193)资助;湖南省重点学科建设项目资助;湖南省教育厅重点项目(07A067)资助

摘　　要：de Bruijn序列结构是一个查寻表,其核心是它的表标签.因此构造出查寻表标签对于生成de Bruijn序列十分重要.本文给出一种m+1元n级de Bruijn序列查询表标签的末位基准构造法.方法一为末位复制构造法,即对大部分节点用构成该节点的串的末位字符拷贝值作为该节点的标签.方法二为末位分组构造法,即对大部分节点按构成该节点的串的末位字符值分成两组,第一组的标签设为定值,第二组的标签任取为第一组节点的末位值.这些方法构造的查寻表标签数随着m,n增长而成指数式增长.但仍与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小.方法二与定值标签构造法比较其速度提高了关于m和n的指数式倍.The structure of de Bmijn sequences is a Look-up table whose kernel is its Look-up table label. So it is very important for generating de Bruijn sequences to construct their Look-up table labels. This paper presents two methods for constructing m ＋ 1-ary n stage look-up table labels based on the value of the last character of the node. Method 1 is a construct method by using the copy of the last character of the node as its label for most of nodes. Method 2 is a construct method by dividing into two groups according to the value of the last character of nodes, the labels are set a fixed value for node of the first group and are taken the value of the last character of the node belong to the first group for the second group. The increasing speed of the amount of Look-up table labels constructed by these methods is exponential by m, n. It is still the same as the method by using fixed value labels. It seems that these methods are 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. The speed of method 2 raises exponential times on m and n compared with the method by using fixed value labels.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]