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

• 作者: 谢深泉
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: de Bruijn序列 查寻表 查寻表标签 节点标签表 节点链
• 年，卷（期）: 2008,（33）
• 所属期刊栏目: 理论研究
• 页码范围: 37-40
• 页数: 4页
• 分类号: O157.4|TN911
• 字数: 4981字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.33.011

摘要

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的指数式倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢深泉	湘潭大学信息工程学院	43	456	10.0	20.0