小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2009年
9期
1819-1823
,共5页
de Bruijn序列%查寻表%查寻表标签%节点标签表%节点链
de Bruijn序列%查尋錶%查尋錶標籤%節點標籤錶%節點鏈
de Bruijn서렬%사심표%사심표표첨%절점표첨표%절점련
de Bruijn序列结构是一个查寻表,其核心是它的表标签.因此构造出查寻表标签对于生成de Bruijn序列十分重要.本文给出一种m+1元n级de Bruijn序列查询表标签的末位基准构造法.方法一为末住复制构造法,即对大部分节点用构成该节点的串的末位字符拷贝值作为该节点的标签.方法二为末位分组构造法,即对大部分节点按构成该节点的串的末位字符值分成两组,第一组的标签设为定值,第二组的标签任取为第一组节点的末位值.这些方法构造的壹寻表标签数随着m,n增长而成指数式增长.但仍与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小.方法二与定值标签构造法比较其速度提高了关于m和n的指数式倍.
de Bruijn序列結構是一箇查尋錶,其覈心是它的錶標籤.因此構造齣查尋錶標籤對于生成de Bruijn序列十分重要.本文給齣一種m+1元n級de Bruijn序列查詢錶標籤的末位基準構造法.方法一為末住複製構造法,即對大部分節點用構成該節點的串的末位字符拷貝值作為該節點的標籤.方法二為末位分組構造法,即對大部分節點按構成該節點的串的末位字符值分成兩組,第一組的標籤設為定值,第二組的標籤任取為第一組節點的末位值.這些方法構造的壹尋錶標籤數隨著m,n增長而成指數式增長.但仍與定值構造法一樣,在跼部看是有效的,但與查尋錶標籤本身數目的驚人增長比較起來就很渺小.方法二與定值標籤構造法比較其速度提高瞭關于m和n的指數式倍.
de Bruijn서렬결구시일개사심표,기핵심시타적표표첨.인차구조출사심표표첨대우생성de Bruijn서렬십분중요.본문급출일충m+1원n급de Bruijn서렬사순표표첨적말위기준구조법.방법일위말주복제구조법,즉대대부분절점용구성해절점적천적말위자부고패치작위해절점적표첨.방법이위말위분조구조법,즉대대부분절점안구성해절점적천적말위자부치분성량조,제일조적표첨설위정치,제이조적표첨임취위제일조절점적말위치.저사방법구조적일심표표첨수수착m,n증장이성지수식증장.단잉여정치구조법일양,재국부간시유효적,단여사심표표첨본신수목적량인증장비교기래취흔묘소.방법이여정치표첨구조법비교기속도제고료관우m화n적지수식배.
