最长公共子序列

摘要： 针对战场态势智能化分析与深度感知需求,在积累的活动航线规律知识基础上,结合实时目标运动特征,采用滑动窗口处理、活动阵位特征过滤、数据格式化处理等手段,运用最长公共子序列处理思想,提出一种快速实用的航线规律匹配算法。通过若干案例仿真验证了该算法模型的可行性和有效性。该模型能够综合考虑战场态势分析的时效性和快速性,准确匹配出实时目标相关联的活动规律信息,并且该算法计算量小、耗时短、匹配效率高,易于工程实现。

摘要： 为探索最大编队长度和路网中行驶货车数目对自发编队的影响以及评估真实世界自发编队油耗节省潜力,提出了既可保证一定程度的搜索又能防止为过分追求更大编队长度而花费较长时间等待的动态时空搜索范围策略,利用辽宁省货车轨迹数据挖掘了多辆货车的最长公共子序列,并构建整数规划模型求解,获取最大节省油耗下的编队方案。结果显示:编队油耗节省会随着路网中行驶货车数目和最大编队长度的增加而增加,编队中车辆平均行驶距离和平均节省油耗最终分别收敛至一范围;编队行驶距离并不一定会随着允许最大编队长度的增加而增加,即自发编队最大油耗节省策略并非编队最大行驶距离策略;在不考虑时间搜索范围时,通过继续增大空间搜索范围可实现更多的燃油节省,但不考虑空间搜索范围时持续增加时间搜索范围却不能获得更多燃油节省;4000辆车的数据集进行自发编队时每天最多可节省燃油2026.21 L,最大允许编队长度为5辆比最大允许编队长度为2辆的车辆平均节省油耗最多可提升13.92%。将本文整套处理流程应用于更大规模的货车数据集,可组成自发编队的目标车辆将会显著增加,相应地也可减少更多的能源消耗和污染物的排放,具有很大的应用潜力。

摘要： 日志事件提取指将非结构化的日志消息解析为系统中对应的事件,是多数日志分析中必不可少的前置工作。传统的日志事件提取以批处理方法为主,需要等待所有日志数据到达再进行处理,实时性不佳。能够进行实时日志采集并处理的流处理方法逐渐成为主要研究方向,但已有的流处理方法在解析模型的构建方面存在缺陷,准确性不够高。针对上述问题,提出了层次化不变序列搜索方法,即HISS(Hierarchical Invariant Sequence Search)。该方法以流处理方式解析日志,基于启发式规则分别在不同层次对日志进行标识和划分,通过日志文本相似度和事件模板质量评价机制维护解析模型,生成日志事件。将该方法和现有日志事件提取方法基于典型系统的日志数据集进行对比实验,实验表明,HISS在执行效率上与最快方法 Drain相当,并拥有更高的准确性,在结构较复杂的日志数据上准确度可提高7.6%~19.8%。

摘要： 动态规划是指一种通过若干步骤使决策不断优化的通用方法,在运筹学、控制论,以及对如今热议话题“人工智能”衍生的近似动态规划中得到广泛的应用。本文将从公共子序列的最大长度问题入手,并引入0-1背包问题,对动态规划进行应用。

摘要： 在经典轨迹的相似度量问题中提出一个新问题:假设有待相似度量的经典轨迹和实时轨迹,在经典轨迹中存在部分点为重要点,实时轨迹受这些重要点约束。针对此问题,将经典轨迹和实时轨迹作为相似度量的两序列,重要点作为实时轨迹的约束序列,利用带约束的最长公共子序列理论提出带重要点约束的经典轨迹相似度量基础算法和快速算法。实验结果表明,快速算法比基础算法的计算时间减少了36%以上。

摘要： 针对用户评分信息密度稀疏以及推荐结果排序不够理想的问题,提出一种基于改进相似度的深度神经网络矩阵分解推荐算法。该算法将用户信息作为类序列,采用最长公共子序列算法寻找相似用户,让近期更符合用户兴趣的推荐结果出现在更靠前的位置,使得相似用户间的隐藏特征向量更加接近,并在运用深度神经网络学习用户和项目之间的隐藏特征时维持这种关系,从而提高模型的预测精度。在Epinions数据集上根据不同的性能指标进行对比实验,验证了该算法的推荐效果。

摘要： 当今社会移动终端设备在极大便利人们生产生活的同时产生了海量轨迹数据.如何利用轨迹数据检测犯罪嫌疑人在物理空间中的异常行为成为公共安全领域的研究热点.基于行为人的GPS坐标数据,研究设计异常轨迹检测算法.对于某人在一段时间内的轨迹数据,首先将其划分为若干停留区域,未被停留区域覆盖的轨迹点被直接去除;然后将每一个停留区子轨迹内的轨迹点匹配至具体地址,进而编码为数字组成的字符串,得到整个停留区子轨迹接轨迹点时序组合的字符序列;采用最长公共子序列计算各停留区子轨迹编码间的相似度,并根据相似度判别得到异常停留区候选集;最后在敏感地点验证模块,将异常停留区候选集和敏感地点集的交集作为异常停留区域输出.在公开轨迹数据集Geolife上的实验结果显示研究方法取得较理想的检测精度.

摘要： 随着国家高性能计算环境各个节点产生日志数量的不断增加,采用传统的人工方式进行异常日志分析已不能满足日常的分析需求.提出一种异常日志流量模式的定义方法:同一节点相同时间片内日志类型的有序排列代表了一种日志流量模式,并以该方法为出发点,实现了一个异常日志流量模式检测方法,用来自动挖掘异常日志流量模式.该方法从系统日志入手,根据日志内容的文本相似度进行自动分类.然后将相同时间片内日志各个类型出现的次数作为输入特征,基于主成分分析的异常检测方法对该输入进行异常检测,得到大量异常的日志类型序列.之后,使用基于最长公共子序列的距离度量对这些序列进行层次聚类,并将聚类结果进行自适应K项集算法,以得出不同异常日志流量模式的序列代表.将国家高性能计算环境半年产生的日志根据不同时间段(早、晚、夜)使用上述方法进行分析,得出了不同时间段的异常日志流量模式和相互关系.该方法也可以推广到其他分布式系统的系统日志中.

摘要： 最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS).针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选.通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在O(mn)时间复杂度下快速估算LCCS长度的近似算法.大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好.

摘要： 本文针对生物序列提出一种快速的求最长公共子序列的并行算法,该算法首先对多条序列建立同字符后续表,随后对于所有的初始同字符组并行地搜索其后继同字符组,以得到所有的同字符组及相应的层次值。最后由最大层次值的同字符组进行回溯,得到相应的比对结果。对于n个序列X1,X2,…,Xn,该算法的并行复杂度为O(|LCS(X1,X2,…,Xn)|),该复杂度与序列个数n无关。定义了一些剪枝操作,以缩小搜索空间,加快处理速度。对tigr数据库中的基因序列在MPP并行处理机深腾1800上进行的实验结果证明,本算法与其它经典的LCS算法相比,不但能够取得准确的结果,而且在速度、效率上有了很大的提高。

摘要： 为了解决由于移动用户轨迹数据具有随机性和繁杂性而导致算法效率和精度低的问题,首先抽取用户轨迹时间位置序列,然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性,最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性.实验证明,该算法具有一定的有效性和扩展性.

摘要： 为了解决由于移动用户轨迹数据具有随机性和繁杂性而导致算法效率和精度低的问题,首先抽取用户轨迹时间位置序列,然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性,最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性.实验证明,该算法具有一定的有效性和扩展性.

摘要： 为了解决由于移动用户轨迹数据具有随机性和繁杂性而导致算法效率和精度低的问题,首先抽取用户轨迹时间位置序列,然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性,最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性.实验证明,该算法具有一定的有效性和扩展性.

摘要： 为了解决由于移动用户轨迹数据具有随机性和繁杂性而导致算法效率和精度低的问题,首先抽取用户轨迹时间位置序列,然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性,最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性.实验证明,该算法具有一定的有效性和扩展性.

摘要： 符号化时间序列聚类是聚类研究中的热点之一,其中关键问题是时间序列符号化相似度问题.本文针对传统的基于欧式距离度量存在的缺陷,以LCS度量为基础,提出了ELCS相似性度量,克服了LCS度量需要依赖线性函数选取的不足.在两类数据集上进行的实验表明,同其他常用度量的比较,该度量有着更好的聚类效果.

摘要： 符号化时间序列聚类是聚类研究中的热点之一,其中关键问题是时间序列符号化相似度问题.本文针对传统的基于欧式距离度量存在的缺陷,以LCS度量为基础,提出了ELCS相似性度量,克服了LCS度量需要依赖线性函数选取的不足.在两类数据集上进行的实验表明,同其他常用度量的比较,该度量有着更好的聚类效果.

摘要： 符号化时间序列聚类是聚类研究中的热点之一,其中关键问题是时间序列符号化相似度问题.本文针对传统的基于欧式距离度量存在的缺陷,以LCS度量为基础,提出了ELCS相似性度量,克服了LCS度量需要依赖线性函数选取的不足.在两类数据集上进行的实验表明,同其他常用度量的比较,该度量有着更好的聚类效果.

摘要： 符号化时间序列聚类是聚类研究中的热点之一,其中关键问题是时间序列符号化相似度问题.本文针对传统的基于欧式距离度量存在的缺陷,以LCS度量为基础,提出了ELCS相似性度量,克服了LCS度量需要依赖线性函数选取的不足.在两类数据集上进行的实验表明,同其他常用度量的比较,该度量有着更好的聚类效果.

摘要： 本申请公开了一种基于最长公共子序列的文本段落识别对比方法及系统。该文本段落识别对比方法包括：获取第一文本字符串和第二文本字符串；对所述第一文本字符串和所述第二文本字符串进行段落识别；对所述第一文本字符串和所述第二文本字符串进行段落顺序调整；将段落顺序调整后的所述第一文本字符串和所述第二文本字符串进行对比，获得差异项。该文本段落识别对比系统包括：前端、转换模块、段落识别模块、以及对比模块。本申请解决了解决了现有的文档对比工具无法对不能获取段落信息的文档进行对比、以及无法对段落对调情况进行很好的处理的问题。

摘要： 本发明涉及信息查询和知识挖掘技术领域，且公开了一种大规模多序列最长公共子序列问题的求解方法，本发明利用计算后继节点的方式将求解多序列最长公共子序列问题转化为求解有向无环图中的最长路径问题；在构建有向无环图的过程中，对每一个节点进行判断，若为无用节点，则将其与经过它的所有路径从图中删除，从而保证所构建的有向无环图为最小有向无环图，即图中的节点数和有向边的数目为最小；最小有向无环图中从起始点O(0,0,…,0)到终点∞(∞,∞,...,∞)之间的最长路径即对应多序列的最长公共子序列；该方法因为所构建的有向无环图的规模很小，所花费的时间和空间代价也小，从而能够快速高效求解大规模多序列最长公共子序列问题。

摘要： 本发明涉及一种基于BIDE算法与最长公共子序列的序列型数据同一鉴定系统及方法，包括以下步骤：建立基于用户行为模式的数字证据同一鉴定模型；采用BIDE算法实现用户频繁行为模式的快速挖掘；设计基于最长公共子序列的用户行为模式综合相似度的计算方法。该方法可有效地对序列型用户数据进行同一鉴定，在数字取证中，确认匿名数据是否归属某一特定用户，可应用于对嫌疑人及其数据进行侦查和取证领域。即具备同一性的证据数据所包含的用户行为特征信息与特定犯罪嫌疑人的用户行为特征信息是相同的或相吻合的。

摘要： 本申请涉及基于最长公共子序列的游戏工作室用户检测方法，该方法包括：在用户事件记录中的子序列中，随机选择多个子序列并基于子序列初始化多个类中心；分别计算每个子序列与每个类中心之间的最长公共连续子序列，并分别计算最长公共连续子序列的长度值；根据最长公共连续子序列的长度值，分别将子序列划分至类中心对应的类簇，并分别获取类簇的关键子序列；在用户事件记录中，基于关键子序列圈定目标范围，通过分析目标范围内的用户事件记录，在游戏数据库中确定工作室用户。通过本申请，解决了相关技术中在游戏前期识别工作室用户人力成本较高的问题，能够缩小核查范围，提升了区分工作室用户的人力和时间成本。

摘要： 一种基于最长公共子序列的纤维分类方法，首先对原始数据的扩散信息进行纤维方向估计并纤维跟踪获得符合解剖的大脑纤维流线；其次提取离散化后的质心纤维及将分类的纤维每个节点的多特征信息，获得描述每一根纤维的多特征描述序列；然后加入控制参数ε和δ对几何特征描述序列对应点是否匹配进行约束，求解基于控制参数的特征序列最长公共子序列；最后通过加入权重参数θi对不同的纤维描述多特征序列描述纤维结构信息的比重进行描述；通过深度学习对人工标注的标记纤维进行训练其权重，获得拟分类集群的纤维分类模型。本发明能够完成高效精确的纤维分类，同时对纤维相似性提出新的衡量标准，为识别大脑纤维提供有效的工具。

摘要： 本发明涉及一种基于最长公共子序列的偷逃通行费车辆识别方法，该方法包括：获取原始通行数据库和ETC门架交易数据库；根据原始通行数据库，筛选出其中的至少一条车辆通行记录；根据至少一条车辆通行记录中的车辆信息在ETC门架交易数据库中查询，确定对应的门架交易数据；根据至少一条车辆通行记录中的车辆信息和卡号信息在门架交易数据中进行查找，确定同一辆车至少一个卡号对应的门架交易流水集；根据至少一个卡号对应的门架交易流水集两两之间的最长公共子序列，识别并向前端推送车辆偷逃通行费的情况。本发明利用车辆通行数据与ETC门架交易数据的映射关系，结合轨迹分析，能够有效找出潜在的“一车多卡逃费”车辆。

摘要： 本发明公开了一种基于分支定界的大规模最长公共子序列问题求解方法：步骤1，初始化有向无环图；步骤2，按照k的大小，由小到大依次处理每个Hashtable(k)；若Hashtable(k)≠Φ，执行步骤3，否则执行步骤4；步骤3，处理Hashtable(k)中所有节点；步骤4，若Hashtable(k)＝Φ，则删除Hashtable(k)，k＝k+1；步骤5，若还有未处理的Hashtable(k)，则对未处理的Hashtable(k)执行步骤2；否则，输出有向无环图，执行步骤6；步骤6，根据有向无环图，求解得到最长公共子序列问题的结果。本发明通过新的哈希表构建策略，将节点存储在不同的哈希表中，并在搜索的过程中及时删除之前创建的哈希表从而减少了大量的计算机存储资源。本发明给出了一种分支定界的策略，极大地减少了算法的搜索空间，从而节省了大量的计算和存储资源。

摘要： 本申请公开了一种基于最长公共子序列的文本段落识别对比方法及系统。该文本段落识别对比方法包括：获取第一文本字符串和第二文本字符串；对所述第一文本字符串和所述第二文本字符串进行段落识别；对所述第一文本字符串和所述第二文本字符串进行段落顺序调整；将段落顺序调整后的所述第一文本字符串和所述第二文本字符串进行对比，获得差异项。该文本段落识别对比系统包括：前端、转换模块、段落识别模块、以及对比模块。本申请解决了解决了现有的文档对比工具无法对不能获取段落信息的文档进行对比、以及无法对段落对调情况进行很好的处理的问题。

摘要： 本发明提出一种确定最长公共子序列的方法和装置，其中，该确定最长公共子序列的方法包括：获取待匹配的第一字符序列和第二字符序列，根据所述第一字符序列构建以所述第一字符序列中的字符为关键字，并以对应字符的位置值为哈希值的哈希表；根据预设规则、所述第二字符序列和所述哈希表更新一维动态数组和二维动态数组，并获取遍历所述第二字符序列中最后一个字符之后所获得的目标一维数组和目标二维数组，根据所述第一字符序列、所述目标一维数组和所述目标二维数组确定最长公共子序列。由此，提出了一种新的确定最长公共子序列的方式，利用哈希表和动态数组计算最长公共子序列，对LCS算法的时间进行优化，提高了确定最长公共子序列的效率。

摘要： 本发明的目的在于提供一种基于最小公共子序列的加密网络流量分类识别方法，属于信息安全技术领域。该方法基于KMP算法和最长公共子序列算法，将网络流量中能表示某一行为的特征码族提取出来，构建多种行为特征码族数据库，将待测网络流量的特征码族与数据库中的特征码族进行匹配，从而完成对网络流量的分类识别。本发明流量分类识别方法中所采用的算法复杂度较小，无需机器学习的大量训练，所以也不需要大量算力，适合部署在小型嵌入式设备；特征码很少因为设备或者系统或者时间变化而变化，能够减少过拟合带来的风险，因此相对以往的流量检测算法，有更高的算法准确度，更短的检测时间，能够进行实际应用。