共查询到16条相似文献,搜索用时 203 毫秒
1.
谢深泉 《计算机工程与应用》2008,44(19):16-19
de Bruijn序列结构是一个查寻表,其核心是它的表标签。因此构造出查寻表标签对于生成de Bruijn序列十分重要。给出一种定值标签构造法,即对大多数节点设定为定值标签,对少部分节点则根据查寻表标签的必要条件指定或任意选定标签。该方法构造的查寻表标签数随着m,n增长而成指数式增长。在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小了。该方法在目前缺乏更好的方法的情况下还是最有效的。 相似文献
2.
谢深泉 《小型微型计算机系统》2009,30(9)
de Bruijn序列结构是一个查寻表,其核心是它的表标签.因此构造出查寻表标签对于生成de Bruijn序列十分重要.本文给出一种m+1元n级de Bruijn序列查询表标签的末位基准构造法.方法一为末住复制构造法,即对大部分节点用构成该节点的串的末位字符拷贝值作为该节点的标签.方法二为末位分组构造法,即对大部分节点按构成该节点的串的末位字符值分成两组,第一组的标签设为定值,第二组的标签任取为第一组节点的末位值.这些方法构造的壹寻表标签数随着m,n增长而成指数式增长.但仍与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小.方法二与定值标签构造法比较其速度提高了关于m和n的指数式倍. 相似文献
3.
谢深泉 《计算机工程与应用》2008,44(2):38-41
提出一种加元算法,通过对给定的一个m+1元的de Buijn序列添加一元来产生m+2元de Bruijn序列。实现的方法是通过由一个m+1元de Bruijn序列找出它的Look-up表标签,并由该Look-up表标签产生多个m+1元Look-up表标签,然后合成这些Look-up表标签产生一个m+2元Look-up表标签,再由它产生m+2元de Bruijn序列。 相似文献
4.
谢深泉 《小型微型计算机系统》2009,30(1)
讨论一种由n级de Bruijn序列产生n-1级de Bruijn序列的降级算法.方法是由n级de Bruijn序列找出其n级查寻表标签;接着通过删除该查寻表标签的相应节点的首符号,验证n-2级节点链的合法性,发现并删除节点链中的套结,实现查寻表标签的降级,最终成为n-1级查寻表标签;在此基础上建立其相应的n-1级查寻表,从而求得n-1级de Bruijn序列.文章最后给出关于算法的注解. 相似文献
5.
提出一种生成de Bruijn序列的升级算法。该算法根据给定的n级de Bruijn序列查寻表标签,采用合成的方法构造出n+1级de Bruijn序列的查寻表标签,从而产生n+1级de Bruijn序列。实验结果表明,该算法是有效的。 相似文献
6.
单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为 O(nk22k2+mlogm+mk1)的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数(通常小于10),k2为覆盖同一SNP位点的片段的最大数(通常不大于10)。对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值。 相似文献
7.
考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,在k-tree core问题的基础上,提出了同时带有度约束的k-tree core问题,即k-tree core中的每个节点在子树中的度不超过给定常数q,记为q-DTC(k)(Degree constrained Tree Core)。利用动态规划的方法,采用最优化原则先找出文中所定义的局部根核集,然后利用贪婪思想对不满足度限制的节点所在的分支加以删减,对无权树和赋权树得到了复杂度分别为O(kn)和O(max{n log n,kn})多项式时间算法,其中n是树的节点数。 相似文献
8.
通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O(mn)+O(m2),而由TT(TTT)-1直接求解所需运算量为O(m2n)+O(m3)。数值算例表明了该快速算法的有效性。 相似文献
9.
目前提出的许多关于二值可视密码方案的论文都致力于研究在可视秘密共享方案里如何使像素扩展比较小或恢复图像的对比度比较高的问题。基于Shamir的秘密共享方案的思想,提出一种新的二值图像(k,n)-VCS可视密码方案。该方案利用二元域上线性方程组解的特征及多层(k,k)-VCS构造基础矩阵S0,S1,给出一个强的访问结构,从而获得(k,n)-VCS可视密码方案更小的像素扩展。 相似文献
10.
提出一种生成de Bruijn序列的消元算法,通过一个m+1元n级de Bruijn序列找出其Look—up表和Look—up表标签,基于该Look-up表标签进行修正,找出m元n级的Look-up表和Look-up表标签,并由其产生m元n级de Bruijn序列。该算法在已知一个deBruijn序列的情况下有效。 相似文献
11.
de Bruijn序列间的映射及升级算法 总被引:3,自引:3,他引:0
谢深泉 《计算机工程与应用》2007,43(22):12-14
通过由n级de Bruijn序列找出n+1级de Bruijn序列的look-up表标签,并由相应的look-up表求出n+1级de Bruijn序列,从而建立起n级de Bruijn序列到n+1级de Bruijn序列的映射,发现de Bruijn序列间的一种内在联系,导出一类任意元de Bruijn序列的升级算法。 相似文献
12.
de Bruijn序列间的映射及降级算法 总被引:2,自引:2,他引:0
谢深泉 《计算机工程与应用》2007,43(28):21-24
通过由一个n级de Bruijn序列找出它的LOOK-UP表标签,并由该LOOK-UP表标签经修正找出n-1级LOOK-UP表标签,再由它计算出n-1级de Bruijn序列,从而建立起n级de Bruijn序列到n-1级de Bruijn序列的映射,发现de Bruijn序列间的一种内在联系,导出一类任意元de Bruijn序列的降级算法。 相似文献
13.
为解决全景图像查表展开法所需查找表空间过大问题,提出八向对称重用的策略.首先,把展开前圆环状全景图像看作一系列同心圆环,沿圆心将这些圆环均匀划分成八个对称的扇形区域.然后,利用空间几何对称性原理,建立八个区域中像素点之间的对称变换关系,这样只需保存一个扇形区域的全景变换像素坐标映射结果,从而将查找表存储空间降低为原来的八分之一.嵌入式应用实验表明,与传统的全景图像查表展开方法相比,所提出方法不仅将所需查找表存储空间降低了8倍,而且将全景图像展开速度平均提高2.74倍. 相似文献
14.
针对Baptista型算法的一些不足,提出一种基于控制符的混沌加密算法.通过混沌迭代生成控制符,由控制符确定对明文的预处理方式,利用查找表加密预处理后的明文;同时,运用控制符不断更新查找表,使算法具有较高的安全性和较均匀的密文分布;另外,根据控制符不断改变混沌轨道,从某种程度上克服了数字混沌动力学特性的退化,进一步提高了算法的安全强度.最后,通过实验验证了算法的有效性. 相似文献
15.