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

摘要：

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

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

所属期刊栏目：44

分类号：O157.4;TN911(代数、数论、组合理论)

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

在线出版日期：2009-02-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：37-40