计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (33): 37-40.DOI: 10.3778/j.issn.1002-8331.2008.33.011

• 理论研究 • 上一篇    下一篇

de Bruijn序列查寻表标签的k位修正构造法

谢深泉1,2   

  1. 1.湘潭大学 信息工程学院,湖南 湘潭 411105
    2.广东培正学院 计算机信息管理系,广州 510830
  • 收稿日期:2008-05-13 修回日期:2008-08-04 出版日期:2008-11-21 发布日期:2008-11-21
  • 通讯作者: 谢深泉

algorithms for constructing look-up table labels of de Bruijn sequences by modifying k-th character of Node

XIE Shen-quan1,2   

  1. 1.College of Information and Engineering,Xiangtan University,Xiangtan,Hunan 411105,China
    2.Department of Educational Administration,Guangdong Peizheng College,Guangzhou 510830,China
  • Received:2008-05-13 Revised:2008-08-04 Online:2008-11-21 Published:2008-11-21
  • Contact: XIE Shen-quan

摘要: de Bruijn序列的结构是一个查寻表,其核心是它的表标签。因此构造出查寻表标签对于生成de Bruijn序列十分重要。给出两种k位修正构造法。方法1为k位提升构造法,即对大部分节点将其第kk=1,2,…,n-1)位提升一个定值c(1≤cm),来作为该节点的标签。方法2为k位收缩构造法,即对大部分节点将其第kk=1,2,…,n-1)位向定值r(0≤rm)收缩,来作为该节点的标签。这些方法构造的查寻表标签数随着mn增长而成指数式增长。与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小。方法2与定值标签构造法比较其速度提高了关于mn的指数式倍。

关键词: de Bruijn序列, 查寻表, 查寻表标签, 节点标签表, 节点链

Abstract: The structure of de Bruijn 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 k-th character of the node.Method 1 is a construct method by stepping up a fixed value c(1≤cm) to the k-th character of the node as its label for most of nodes.Method 2 is a construct method by shrinking the k-th character of node to a fixed value r(0≤rm) as its label for most of nodes.The increasing speed of the amount of Look-up table labels constructed by these methods is exponential by mn.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 mn compared with the method by using fixed value labels.

Key words: de Bruijn sequence, look-up table, look-up table label, node-label table, node chain