论文研究-de Bruijn序列查寻表标签的k位修正构造法.pdf

【文件属性】：
文件名称：论文研究-de Bruijn序列查寻表标签的k位修正构造法.pdf
文件大小：559KB
文件格式：PDF
更新时间：2022-09-30 12:03:27
论文研究 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的指数式倍。