计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2008年
33期
37-40
,共4页
de Bruijn序列%查寻表%查寻表标签%节点标签表%节点链
de Bruijn序列%查尋錶%查尋錶標籤%節點標籤錶%節點鏈
de Bruijn서렬%사심표%사심표표첨%절점표첨표%절점련
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序列的結構是一箇查尋錶,其覈心是它的錶標籤.因此構造齣查尋錶標籤對于生成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서렬적결구시일개사심표,기핵심시타적표표첨.인차구조출사심표표첨대우생성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적지수식배.
