【摘 要】
：
在信息世界中,很多数据都可以用序列的形式表示,而检测数据间的相似性一直是工程领域中一个重要的研究课题,所以如何计算两个或多个序列的相似性是极其有意义的。例如,在生物技术领域中,通过分析两个生物基因序列的相似性可以判断它们是否具有近亲关系;在图片搜索中,通过计算目标图片与搜索集中图片之间的相似性可以发现与目标最匹配的图片。然而,计算序列之间的相似性通常可以转化为求多个序列的最长公共子序列（MLCS）
论文部分内容阅读
在信息世界中,很多数据都可以用序列的形式表示,而检测数据间的相似性一直是工程领域中一个重要的研究课题,所以如何计算两个或多个序列的相似性是极其有意义的。例如,在生物技术领域中,通过分析两个生物基因序列的相似性可以判断它们是否具有近亲关系;在图片搜索中,通过计算目标图片与搜索集中图片之间的相似性可以发现与目标最匹配的图片。然而,计算序列之间的相似性通常可以转化为求多个序列的最长公共子序列（MLCS）问题。目前,针对MLCS问题,许多算法已经相继提出,例如经典的动态规划算法、基于支配点的图计算方法等等。尽管这些方法在一定程度上可以快速的计算出结果,但是随着序列长度的增长,这些方法都暴露出内存不足以及时间开销大等缺陷。面对这样一些问题,本文做出了如下几点研究成果:为了高效地解决更复杂的MLCS问题,本文提出了基于缩图的启发式搜索算法,其包含四个创新点:1)设计了一个新的计算MLCS长度下界的方法,该方法通过优先搜索距离轴线AL最近且拥有最小坐标值的点可以快速地得到MLCS长度的下界;2)改进了动态规划表计算MLCS长度上界的方法,通过使用一种自适应的方法动态地调整这些表的数量,以至于算法可以在计算大规模MLCS问题的时候不会因为动态规划表数量过多而导致严重的空间和时间负担;3)设计了一个基于分支定界的缩小DAG图规模的方法,在构建DAG图的时候,使用估计出的上、下界删除一些对寻找MLCS没有意义的节点和路径,从而降低了DAG图的规模;4)将缩小图规模方法与启发式搜索方法相结合,提高算法的效率,使其适合超长序列集的MLCS问题。为了能够加速DAG图的构建速度,本文还设计了一种新的栅栏式并行算法,其中包括三个新的策略:1)提出了新的分割DAG图的方式,可以保证每个线程间所负责构建的子图大小近似相同;2)通过缓冲区机制降低了线程间访问共享资源的竞争次数,提高了并行效率;3)在并行构建DAG图的过程中,通过一种新的点更新机制保护了所有点之间的前后继关系不会被破坏。通过大量实验测试,相较于目前一些优秀方法,本文的方法能够更高效地求解复杂的MLCS问题。
其他文献
随着芯片制造工艺的发展,单个晶体管的体积和功耗变得越来越小,单位芯片面积可集成的晶体管数量遵循摩尔定律提升,这导致高端芯片的整体功耗在不断上升。晶体管密度的增加使芯片上的金属布线变得越来越密集和纤细,芯片整体功耗的增大又使金属布线的电流密度越来越大,从而引发了芯片出现EM、IR-Drop等非理想效应,这些效应对芯片的可靠性构成了严重威胁,同时芯片整体功耗的上升也给芯片的热设计带来了巨大的困难,可以
近年来,无线充电技术的普及对各类便携电子设备提出了快速发展的要求。无线充电芯片由于其耦合线圈输入范围较宽,无法直接对芯片内部各个功能模块进行供电,所以需要一种低压差线性稳压器（LDO,Low Dropout Regulator）电路,可将输入电压转换为合适的低电压并对内部电路供电,从而使无线充电芯片内部模块正常工作。基于上述问题,本文的主要研究目标是设计一个用于无线充电芯片内部的宽输入LDO电路。
在卷积神经网络中,深度学习技术凭借其强大的特征提取能力、较强的分类能力,近年来在自然语言处理、语音识别、计算机视觉等领域都有广泛应用。但这种优异性能依赖于大量的参数量和计算量,随着卷积神经网络应用领域的不断扩大,与之对应的是需要有更好的硬件平台,其中就包括更高的计算能力和更好的数据带宽。目前行业内的佼佼者都在致力于挖掘各种基于芯片的解决方案。而CPU和GPU更高的功耗以及需要根据场景进行布置,此方
在当今这个剧烈变化着的时代,伴随着诸如可穿戴电子产品、无人机、商用服务机器人、电动车内的各系统的车载控制器等智能设备越来越成熟、产品性能需求越来复杂,对充当伺服控制器的芯片的功能要求也越来越多变。因此采用旧有硬件结构的伺服控制器逐渐难以平衡实际应用中工程需求的各个方面。与此同时具备相当灵活性的So C设计也逐渐应用于伺服控制领域,伺服控制集成电路IP化已经是必然的趋势。目前,国内主打面向控制类需求
随着信息时代和人工智能时代的快速发展,移动终端设备已经在人们的生活和工作中发挥了不可替代的作用,这对移动设备的充电速度以及充电设备的便携性都提出了更高的要求。反激式变换器以其拓扑结构简单、成本低和天然隔离输入输出环路的优点,在小功率变换器以及便携式设备的充电器领域广受欢迎。GaN功率管因为有着更高的迁移率,相比于传统的Si功率管有着更好的开关响应,在高速开关的场合中得到了越来越广泛的应用。本文设计
近年来,随着人工智能快速发展,深度学习技术已经在许多领域发挥出巨大的作用。目前TensorFlow框架作为最主流神经网络框架之一,根据实际应用或再训练场景的改变,部署神经网络模型需要重新构建和训练模型,并且部署过程十分耗时。为了解决这一问题,微软联合多家公司推出了开放神经网络交换格式（Open Neural Network Exchange,ONNX）,采用统一的标准保存深度学习模型。将Tenso
随着后摩尔时代的到来,在超大规模集成电路设计阶段验证已经逐渐成为困扰各大芯片设计人员的关键问题,虽然可以使用软件仿真、硬件加速仿真等验证方法来加速验证流程,但是随着集成电路设计规模逐渐增大,原先的验证方法在时间成本上已经无法满足当前快速设计迭代的需求,使用FPGA进行芯片设计原型验证已逐渐成为验证阶段主流。但随着设计的规模剧增,单片FPGA已无法满足超大型集成电路设计的验证需求,从而衍生出高密度F
计算机技术发展催生的建筑信息模型（BIM）是建筑工程行业近年来最热门的发展方向,已在建筑设施的规划设计、建造运营等环节发挥重要作用。随着物联网技术的发展,主要采用C/S架构的传统BIM服务对客户端的硬件配置要求高,学习和使用成本高,难以应对新的需求,构建基于Web端的BIM展示系统成为BIM发展的新出路。然而,在Web端BIM数据加载缓慢且渲染帧率低下,是Web端BIM展示系统的瓶颈。本文聚焦于在
随着党政机关的文印市场以及各种书刊出版市场的不断扩大,机关及企业部门对印刷品质量的精确度要求也在不断地提高。而在印刷品的生产过程中,受到生产条件的影响,印刷品经常会出现各种各样的问题:例如在电子文件的排版阶段,图像分辨率的调整从而造成的信息缺失;输出印刷机的印刷生产阶段的漏印,飞墨等,都有可能导致打印出来的文件与原始文件有一些或多或少的差异,这种差异会体现在图文版式,漏字错字等可能造成信息缺失和信
随着互联网技术的发展,社交媒体平台已成为人们日常沟通交流、获取信息的重要渠道,由于网络的虚拟性与隐蔽性,一些非法用户借助于社交媒体平台发布和传播负面言论,其中不乏充斥着色情、赌博、暴恐等敏感信息,严重影响着正常用户的网络社交体验,也影响着社会的稳定和长治久安。敏感文本通常以短文本形式出现,这些文本特征稀疏、包含的可用信息少、语法句式多变。其次,为了规避自动化匹配检测,这类文本中的敏感词还经常以其音