课程文献中心 更多>>

关键词： 数据结构   鲁棒性   哈希表   非阻塞   无锁   无等待  

摘要： 数据结构是计算机存储、组织和操作数据的基础,是算法的基础之一,也是计算机科学的重要基础。但是,部分数据结构存在鲁棒性问题:数据结构的关键参数(例如哈希表的哈希函数)是预先设定的,系统一旦启动后,这些关键参数便无法被高效地修改。针对数据结构缺乏鲁棒性的问题,本文以哈希表为例,设计并实现了一种具有良好鲁棒性的哈希表,所提方法为解决数据结构缺乏鲁棒性的问题提供了一种解决思路。本文所提方法依赖于新兴的多核处理器所提供的冗余计算能力,可以在通过修改数据结构的关键参数对其重建的同时,还可以维护数据结构的服务不终止。本文主要完成了以下工作:(1)设计了一个具有良好鲁棒性的可动态重建哈希表DRHT。当哈希表中某个桶的节点数超过阈值时,通过新建一个新的哈希表实例对哈希表进行重建。重建哈希表时采用无锁的机制,可以原子地将旧的哈希表中的节点转移到新的哈希表中,同时不阻塞并发的查找、插入以及删除操作,保证了系统的可用性。(2)通过实现一个高效的DCSS(Double-Compare-and-Single-Swap)原语,使得DRHT的哈希桶的查找、插入以及删除操作实现了无阻塞,从而实现了一个无锁的可动态重建哈希表LDRHT。(3)对一个提供了无等待的查找操作的链表算法进行优化修改,并将其作为DRHT的哈希桶的实现,实现了一个具有无等待的查找操作的可动态重建哈希表WLDRHT。(4)实验表明,DRHT可以有效地改变其哈希函数,本文所提方法能够高效地解决数据结构缺乏鲁棒性的问题。此外,实验结果表明DRHT在并发操作的吞吐量和响应时间方面优于其他的动态哈希表。

关键词： 股价走势   双支持向量机   数据结构   马氏距离   股票预测  

摘要： 股票市场是宏观经济的“晴雨表”，对股票价格走势的分析，及“智能”化预测，一直备受投资者的关注.股票价格受政策，宏观经济以及公司经营状况等多方因素的影响，且各因素之间存在较高的相关性，因此股票数据具有的高噪声，非平稳等特性使得股票预测充满阻碍与困难.为了减少数据中存在的噪声对分类结果的影响,本文构建了两种股票预测模型，对股票价格走势进行预测.并在以上两种模型预测结果的基础上提出股票交易策略，以此获得超额收益.　　本文提出了一种融入样本结构信息的最大间隔分类器，称为结构化最大间隔双支持向量机.该方法通过马氏距离消除了特征间不同量纲的影响，可以更好地衡量每类样本与其他类超平面的距离，更加合理地利用结构信息，从而在一定程度上降低了数据中存在的高噪声对分类决策的影响.在人工数据集和基准数据集上的实验结果表明，结构化最大间隔双支持向量机具有良好的分类精度和较强的抗噪能力.　　考虑到股票交易中存在时限性,结合结构化最大间隔双支持向量机和最小二乘双支持向量机，本文提出了最小二乘最大间隔双支持向量机.该方法将不等式约束改为等式约束，并将损失函数替换为松弛向量内积的形式.因此最小二乘最大间隔双支持向量机只需求解两个线性方程组，而不需要求解两个二次规划问题，极大的提升了模型的学习速度.在基准数据集上的数值实验表明，相较于最小二乘双支持向量机,最小二乘最大间隔双支持向量机具有更高的正确率和更少的计算时间.　　本文选取了9支股票的16个主要影响因素作为输入特征.并采用主成分分析法对原始数据进行预处理，消除特征间多重共线性以及提高模型的计算速度.同时,引入遗传算法进行参数优化，提高模型预测的准确率.实验结果表明，通过主成分分析降维后，模型预测的正确率和年化收益率在未受损的情况下，提升了运算速度.在参数优化方面，由于遗传算法在更广的范围内搜寻最佳参数，因此，遗传算法的预测正确率，年化收益率和运算所需时间均远超网格搜索算法.在模型方面，将双支持向量机，最小二乘双支持向量机以及本文提出的两个模型应用到股票涨跌趋势预测中，通过对分类精度和收益率的分析，验证了结构化最大间隔双支持向量机和最小二乘最大间隔双支持向量机的有效性与实用性.

关键词： 字符串检索   前缀树   数据结构   动态位数组  

摘要： 随着互联网信息技术和计算机的发展与推广,社会生活中的许多方面都以数字化方式呈现,这样的社会变革引发了各行业数据的爆炸性增长,使人们踏入了21世纪的大数据时代。大数据时代是在利用相关算法对海量数据进行处理、分析的过程中,挖掘数据财富和数据价值,并运用它来决策发展方向、服务于生活与生产的时代。在大数据时代,数据分析和挖掘是重中之重,大数据时代的数据挖掘区别于传统数据挖掘的显著特征在于,其处理速度快且时效性高。这要求高效的数据结构与算法支持对字符串的各种处理。作为实现字符串高效处理的基础保证——字符串检索,如何提高字符串检索在大数据场景的各项性能表现,成为推动相关大数据产品落地的关键。针对这个角度,本文从字符串检索方向进行了深入学习研究,具体完成的工作包括: (1)详细分析了广泛用于字符串检索领域的前缀树(Trie)搜索结构与算法原理,针对基于Trie树的多种实现结构包括经典Trie树结构、压缩前缀树(Radix-tree)结构以及双数组(Double-array Trie,DAT)结构分别进行了深入的原理剖析及时间空间复杂度分析,并分别指出了这些结构存在的缺陷和不足。通过汇总所有的问题,提出了实现基于Trie树的高效搜索结构的优化方案。 (2)根据提出的优化方案,实现了一个基于Trie树的、具备高效时空表现的以及支持动态更新场景的高效字符串搜索结构——动态位数组(Dynamic-Bit Array,D-BA)结构。D-BA结构以2n+1个bit位的空间消耗实现了Trie树的有效表示,这样的特征促进了其在大数据应用场景中的使用。此外,D-BA结构支持Trie树动态更新的性质扩大了其应用于更多场景的可能。 (3)针对字符串插入、删除、查询等基本操作,设计了基于D-BA结构的实现算法,此外,为实现在大数据应用场景中D-BA结构Trie树的快速构建,基于D-BA结构的分层位数组特征以及指令集批处理思想,设计了D-BA结构的快速构建算法。算法通过程序并发的执行方式,同时构建不同层级字符对应的位数组,避免了较长字符串导致算法性能退化的问题,使构建算法时间复杂度恒定为O(n),n为输入数据集包含的字符串数量。 (4)针对D-BA结构以及其相匹配的相关操作算法,设计了定长字符串不同数量规模数据集以及定量字符串不同字符串长度数据集两类数据集情况下,交叉验证D-BA结构性能表现的测试方案。经过与经典Trie树实现结构、Radix-tree结构以及双数组结构的测试对比,D-BA结构的内存空间消耗分别约占上述实现结构的1%、3%、2%。同时,随着字符串数据量级的增长,D-BA结构消耗的内存空间呈较低系数的线性增长,系数约为1.2,而其他结构以大于1.2的系数(测试结果显示,最大增长系数约为2.4)波动增长。这样的性质增强了D-BA结构应用大数据场景内存空间消耗的可预测性,面对实际的业务增长能较好地把控内存空间消耗风险。对计算机资源分配更加友好。 本文图40幅,表10张,参考文献56篇。

关键词： 数据结构化   知识图谱   轨道交通设备   智能应用  

摘要： 在轨道交通网络的运营服务中,大量的运营生产数据和设备维护数据每日不间断的产生,这些数据分散在各个业务系统,数据异构性强,数据的流通性较弱。特别是半结构化、非结构化数据沉淀了大量业务知识,与既有结构化数据结合可以产生更加广泛的应用场景和更高的价值密度,然而其价值利用效果较为局限。 知识图谱通过结构化的方式对客观世界中的各种概念、实体、属性和关系进行描述,能够更好的对海量信息进行组织、管理、理解,并辅助数据和知识进行更加智能化的运用,促进设备管理向信息化、数字化、智能化转变。本文主要基于知识图谱技术对轨道交通设备领域数据结构化问题进行研究,围绕设备运维业务,研究基于业务要素的轨道交通设备数据认知结构模式。在此基础上,通过设备数据图谱构建和应用案例,探讨数据的提取方法和智能应用。具体研究内容包括: (1)对知识图谱在城市轨道交通设备数据结构化中的应用进行分析。通过对大量文献的总结分析,对目前轨道交通领域数据结构化及知识图谱在轨道交通领域的应用研究情况进行总结分析。对知识图谱理论理论方法进行了系统的梳理,对城市轨道交通设备数据的内容、特征和结构化需求进行了总结,探索知识图谱应用于城市轨道交通设备数据结构化的路径。 (2)研究轨道交通设备维护管理领域数据结构化认知理论与方法。首先基于系统分析的方法,从对象要素、状态要素、主体要素、行为要素、规则要素、环境要素、目标要素等方面,对轨道交通设备维护管理领域的业务要素构成及其关联关系进行梳理,在此基础上确定设备管理业务核心概念与属性数据范围。然后从数据结构化角度,对各业务要素的数据内容构成和结构特征进行分析,结合知识图谱理论方法,从具有分层分类特征的业务子域、具有多属性特征的业务子域、具有多粒度特征的业务子域,系统地梳理和构建设备数据的认知结构模式。 (3)研究城市轨道交通设备数据图谱模型构建方法。通过所构建的设备数据认知结构模式,构建城市轨道交通设备数据图谱案例。首先对案例数据源特点进行分析和分类,基于不同类别数据的结构特点分别通过基于直接转换的方法、基于规则的方法对设备数据进行抽取。其次对知识图谱数据存储方法进行梳理,选择neo4j图数据库对数据进行存储,构建了城市轨道交通设备数据图谱。 (4)城市轨道交通设备数据图谱智能应用案例分析。通过所构建的城市轨道交通设备数据图谱,对设备数据图谱在可视化关联分析、知识问答和辅助决策三个方面的应用进行实现和分析。在可视化关联分析方面,对设备故障和维护数据进行可视化关联统计分析,对设备进行单台设备可视化画像分析,以及分析基于路径关联的设备数据查询应用。在知识问答和辅助决策方面,开发了相应的问答和故障辅助辨识系统,实现基于自然语言的、便捷的、细粒度的设备数据问答获取和故障现象辨识应用,基于此对设备故障处理流程进行了优化,辅助业务人员在故障处理过程中进行决策,在提高设备数据的利用效率的同时提升故障处理效率和资源调配能效。

关键词： Social sciences  

ISBN: (数字)9783111000886;9783111001142 ISBN: (纸本)9783111000824

摘要： The immense increase on the size and type of real time data generated across various edge computing platform results in unstructured databases and data silos. This edited book gathers together an international set of researchers to investigate the possibilities offered by data-fabric solutions; the volume focuses in particular on data architectures and on semantic changes in future data landscapes.

关键词： 文艺副刊   数据结构化   媒体数据库   开放式   创新  

摘要： 很多报刊的文艺副刊历史数据规模庞大、质量上乘，如果利用技术手段将其数字化、数据化、结构化，就能转化为既可通过互联网浏览检索，又可打通历史数据与日常采编大数据平台的数据资产，从而唤醒和提升其生命活力。本文从文艺副刊历史数据结构化的必要性入手，探讨其成效及存在的问题，并提出相应建议，以期为发掘报刊存量价值、创造增量价值抛砖引玉。

关键词： 自然语言处理   机器阅读理解   预训练模型   报关单证   关键信息提取  

摘要： 在进出口报关的货物申报环节,人工对照原始报关资料在“单一贸易”窗口等报关系统填入申报数据不仅操作繁琐而且费时费力,急需引入能够与报关平台对接的智能报关单识别系统,来将表格或文档形式的报关单证转化为结构化数据。鉴于机器阅读理解技术强大的信息检索和信息抽取能力,本文提出了生成式机器阅读理解数据集扩充模型(Generate Data set Migration,GDM)用于辅助报关单数据结构化模型进行数据增强。由于在报关单证数据结构化领域存在开源数据集少的问题,本文使用企业提交的真实报关单证和报关数据来构造报关单证数据结构化数据集,并使用GDM方法引入外部数据集样本共同训练基于机器阅读理解的报关单数据结构化模型Clearance-MRC。最后,本文构造了一个以机器阅读理解深度学习推理模型等模块为核心的报关单数据结构化智能系统,该系统已投产并获得多家报关行的用户使用,为企业进行自动化货物申报贡献一份力量。 针对机器阅读理解非主流领域高质量数据集稀少的问题,本文构造了生成式数据集扩充模型 GDM,该模型由基于 CPT(Chinese Pre-trained Unbalanced Trans-former)的生成模型以及样本过滤器构成,其中生成模型使用本文提出的衰减的稀疏softmax方法计算损失,该模型能够从外部数据集样本中过滤出与源数据集风格类似的样本并与源数据集样本进行合并,达到扩充机器阅读理解片段抽取模型训练数据集的效果。实验表明该方法对比于三种添加外部数据集方法,在两类公开非主流领域数据集上进行评估达到了最好的效果,说明了方法的有效性。 针对报关单证数据结构化任务数据集缺失的问题,本文构造了包含1000条样本的高质量数据集CusMRC,在此过程中使用了提示模板和报关专业知识来构造样本中的问题。之后又构造了基于Roberta的机器阅读理解模型Clearance-MRC,并使用本文提出的GDM模型引入外部数据集样本结合CusMRC样本作为扩充后的训练集,来训练Clearance-MRC模型,并在CusMRC测试集上进行测试,最终测试的结果为F1-socre为82.27,EM得分为70.388。 本文构造了一个智能化识别报关单信息并且能够转化为结构化数据的报关单证数据结构化智能系统,该系统的核心模块为数据处理模块、深度学习模型推理模块以及数据结构化模块,最后本文展示了系统的详细设计及页面功能。

关键词： 笛卡尔网格   各向异性自适应   数据结构   列车   气动性能  

摘要： 笛卡尔网格具有网格质量好、自动化程度高、复杂外形/流场自适应能力强等特点,适用于开展复杂外形/流场的数值模拟研究。然而,精细模拟边界层这一各向异性流动特征时,需要的笛卡尔网格数量呈现与雷诺数指数形式的增长,尤其对高雷诺数流动面临“网格灾难”问题。各向异性自适应笛卡尔网格可根据外形/流场的实际需求只在某个特定方向加密,达到降低网格规模同时保证计算结果准确性的目的。因此,本文基于各向异性自适应笛卡尔网格,围绕网格生成、求解器构建等方面开展研究,并探索将其应用在列车气动性能评估中的可行性及可靠性。提出了鲁棒、高效、低存耗的各向异性自适应三维复杂外形笛卡尔网格自动生成方法。构建了嵌套包围盒概念的物面三角形网格数据结构和成员封装线索指向的各向异性空间笛卡尔网格数据结构;建立了邻居单元高效查询方法,并提出邻居关系需满足的三条准则,保证邻居关系正确性、合理性与唯一性;发展了基于分离轴理论的笛卡尔网格-三角形相交算法与物面三角形网格数据结构相结合的网格类型判定方法,提升了网格生成鲁棒性和效率;构建了包含外形自适应、曲率自适应、各向异性自适应、添加缓冲层、网格质量检查在内的五步几何自适应加密策略,确保几何信息高保真、网格数量合理、网格质量最优。本文各向异性自适应笛卡尔网格生成方法效率较公开文献提高一个量级,内存消耗较传统2数据结构下减少20%以上,网格数量较各向同性自适应减少50%以上。建立了高效、高精度物面边界处理及悬挂网格流场重构方法。发展了参考点位置选取合理、虚拟单元流场重构准确的壁面处理方法,实现了Spalding壁面函数在非贴体笛卡尔网格下的自适应修正与应用;构建了悬挂网格处插值模板点的选取方法和模板点流场值重构技术;结合物面三角形网格数据结构,优化了最近邻搜索算法中距物面较远数据点的回溯过程,设计了笛卡尔网格框架下壁面距离的精确高效计算方法;发展了基于速度散度、速度旋度和流场变量梯度的流场解自适应判据准则,解决了现有流场解自适应判据在各向异性自适应笛卡尔网格框架下失效的问题。构建了适用于各向异性自适应笛卡尔网格框架的数值求解器。研发了集网格生成和流场求解于一体的全自动各向异性自适应笛卡尔网格程序,实现了三维流动问题的准确、高效模拟。结合圆柱、尖劈、圆球、非对称翼型、对称翼段以及高速列车等典型算例并与试验结果进行比较,验证了程序的正确性、可靠性及高效性,以尖劈为例,各向异性自适应后的网格数量较各向同性自适应减少约20%,计算耗时相应减少约13%,同时,与解析解相比,各向同性自适应和各向异性自适应的误差分别为7.2%和6.9%。图95幅,表23个,参考文献190篇

关键词： 复杂事件识别   逆向安全   模式匹配   数据结构   后缀树  

摘要： 物联网(Internet of Things,IoT)中涉及大量的互联网传感器,这些传感器收集大量的数据流,作为各种物联网应用的输入,广泛用于监测人员行为、防范电子欺诈、监测心律失常等。为了在物联网应用中实时监控数据、搜索指定的信息,复杂事件识别(Complex Event Recognition,CER)技术的应用越来越广泛,已经逐渐从新兴技术过渡到许多行业的重要平台,发挥着重要作用。复杂事件识别将原始传感器数据流抽象为事件序列,并且已经成为一种用于监控事件序列以搜索用户感兴趣的事件模式的技术,给用户提供做出反应和前瞻性措施的机会。但是随着这一技术应用越来越广泛,如何更好地平衡其中的隐私保护问题和匹配效用成为了近年来的研究热点。研究学者提出了许多平衡隐私保护和效用的方案。现存的大多数方案是在事件的单个属性上或是在模式层面上进行隐藏,然后对事件模式进行匹配,对于完整的事件序列却没有设置机制保护,这对于试图窃取完整事件序列以分析用户行为的攻击者来说是不适用的。还有一些方案虽然在一定程度上防止了敌方重构完整的事件序列,但是在匹配效用上稍有欠缺。本文针对以上问题,对如何实现高效地匹配更多用户感兴趣的事件模式,但是又不泄露用户的完整事件序列进行了研究。本文的主要贡献为:1.本文提出了一个基于规则集的事件序列查询模型。该模型考虑了当CER系统部署在敏感环境下,能够实现对用户感兴趣的事件模式进行匹配,同时计算敌方重建完整事件序列的概率。本文提出了规则集和字符串的深度灵活截断后缀树,能够实现对用户感兴趣事件的模式匹配,其次引入de Bruijn图、AC自动机计算敌方重建完整事件序列的概率。经本文分析和实验表明,本文提出的深度灵活的截断后缀树与现有的同类方案相比,在逆向安全性和匹配效用上更好地实现了折衷。2.提出了一个敌方背景知识模型,在计算重构完整事件序列的概率上,本文考虑的方案更具有普适性。不仅能够考虑到不相交的敌方知识情况,还能够在敌方知识相交情况下,给出完整事件序列泄漏的概率。然后给出了在本文方案的背景知识模型下计算敌方重构完整事件序列概率的两种方法,分别是AC自动机法和构造边法。

关键词： 区块链   虚拟电厂   碳市场   电能量市场   电动汽车   核证减排   智能合约   数据结构   共识机制  

摘要： 随着风电、光伏等分布式新能源渗透率的提升,规模化分布式电源的接入对电网的安全、稳定及经济运行会产生重大影响,分布式电源的波动性会加剧电网运行的安全风险。因此,充分利用用户侧源、储、荷泛在资源,实现用户侧分布式能源的高效聚合,是提升电网对可再生能源的消纳水平的必然需求。虚拟电厂(Virtual Power Plant,VPP)技术将风机、光伏、电动汽车等分布式资源聚合,作为整体参与电力调度和市场交易,丰富了新型电力系统中的可控资源,促进了新能源消纳并提升了分布式资源投资收益。同时,为了响应全社会节能降碳的需求,碳交易市场也在快速发展,VPP通过参与碳交易能够量化其消纳可再生资源的环境效益,并促使VPP获得更多的经济效益。此外,由于VPP聚合多主体参与碳市场和电能量市场,同时存在内部的协调和与上级市场的交易,多主体之间数据的安全性和可信性是VPP运行的基础。区块链技术提供了一种去中心化、兼顾透明性和公平的组网方式,可以促进VPP的安全交易、高效管理和稳定运行。本文研究了VPP参与电能量市场和碳市场的多资源协调优化运行策略,面向多资源主体间的可信交易问题,研究了基于区块链的VPP参与碳市场交易管理方法。 首先,介绍了当前的碳市场运作机制,在此基础上,对VPP参与碳市场的获利空间进行了分析。进一步分析了VPP中典型分布式资源的出力和碳排放特性。最后针对风光出力的波动性,结合蒙特卡罗抽样和场景生成法,对虚拟电厂中风光资源的不确定性进行了定量分析。 其次,建立了计及电动汽车的VPP参与碳市场的优化模型。首先分析了VPP聚合管理电动汽车有序充电的方案,并对电动汽车的碳排放特性进行了分析。然后,针对电动汽车车主难以单独参与碳市场的问题,设计了虚拟电厂代理电动汽车参与碳市场的方案。接着建立了虚拟电厂中多资源参与电能量市场和碳市场的优化模型。最后通过算例验证了VPP参与碳交易市场可以在减小传统火电机组的出力的同时提升VPP的收益。 最后,针对VPP中多资源的分布式管理和调控、交易过程中的数据信任问题,结合区块链技术数据防篡改、交易透明可追溯的特点,设计了基于区块链的VPP参与碳市场的数据管理系统。首先分析了VPP的多资源数据管理需求和区块链的适用性。然后从区块链系统的底层技术、数据结构、智能合约、共识机制四个方面,结合VPP的的调度及数据流动需求,进行了区块链运行框架的设计。最后通过算例对系统的可用性进行了验证。