带有通配符和长度约束的模式匹配问题求解模型

讨论了带有通配符和长度约束的模式匹配(PMWL)问题,其中模式由子模式序列集组成,两个相邻子模式的间隔在一定长度范围内。针对PMWL问题,已有工作包括设计启发式求解算法和对特殊情况进行完备性分析,然而还需要构建问题的基础求解模型。借鉴约束可满足问题框架,构建了由变量、值域和约束组成的三元组求解模型,对PMWL问题的基本概念和基本性质给出了形式化描述。最后,给出了算法求解PMWL问题的特定条件下的完备解。     

非交换BR0-代数与其上的Quantale

提出非交换BR₀-代数的概念,然后讨论了在完备非交换BR₀-代数和完备BR₀-代数上的Quantale性质,最后得出完备Boole代数、完备MV代数、完备R₀-代数以及完备BR₀-代数都是可换的Girard quantales的结论。     

训练模式对的摄动对折线模糊神经网络稳定性的影响

引入折线模糊数及其扩张运算,针对折线模糊神经网络,定义折线模糊数的最大摄动误差、训练模式对的γ摄动等概念,并基于纠错规则设计该网络连接权的学习算法。其次,当转移函数满足Lipschitz条件和训练模式对发生γ摄动时,在定义折线模糊神经网络对训练模式对摄动的全局稳定性的基础上,应用归纳法证明三层折线模糊神经网络的连接权具有稳定性,进而获得该网络关于训练模式对的γ摄动也具有全局稳定性。最后,通过模拟实例说明训练模式对的摄动对该网络稳定性的影响。     

字符分布特征对带有通配符串匹配问题的影响

近年来,字符串匹配问题被不断扩展。其中,具有代表性的是在模式中引入可变长度的通配符,本文称之为PMWL问题。针对此问题,已有工作分析了在不同的模式特征下,匹配数Ω随文本长度增加呈指数级增长。本文同时考虑文本分布特征和模式特征,建立了期望模型E(Ω)＝n*D*π(P),其中n为文本长度,D为模式中各通配符跨度的乘积,π(P)为基于字符分布的模式出现概率。实验部分,在人工随机数据和DNA真实数据上验证了E(Ω)的准确性,得到预测误差率分别为1.8%~3.2%和4.7%~7.8%;在不同字符分布中,分析了模式模长和通配符跨度对匹配数Ω的影响。E(Ω)模型揭示了Ω的增长趋势不一定呈指数级,而取决于π(P)和D的共同影响。此外,E(Ω)模型能够在线性时间内得到近似完备解。     

图像组转置训练及非凸约束的去噪去模糊算法

针对稀疏表示模型的过完备字典集训练过程中图像块采样不充分问题,提出图像组转置训练及非凸约束的去噪去模糊算法.采用组间方差约束的图像块搜索策略,并根据自适应软阈值对筛选的字典集进行转置学习.在重构过程中采用l_p(0范数约束以保证结果的强稀疏性.最后采用Bregman拆分迭代法求解文中非凸模型.实验表明,文中算法重构图像具有较好的视觉效果,去噪去模糊效果较优.     

基于3D高效率视频编码背景的信息隐藏算法

针对秘密信息在公开网络传输的安全性和容量性问题,提出了一种基于高效率视频编码（HEVC）背景的信息隐藏算法。利用HEVC中多视点图像的背景图作为载体,首先对其进行lαβ分解得到三个灰度分量子图,然后选取α和β分量子图作离散余弦变换,最后将秘密信息重复嵌入到载体区域中。隐藏区域选取能量权重较低的α及β分量子图的离散余弦变换中频系数区域,且进行重复嵌入,使得算法具有良好的不可见性和鲁棒性。实验结果表明,所提算法比基于帧间和帧内算法不可见性分别提高16.1%和11.4%,鲁棒性分别提高55.5%和20.2%。     

稀疏-平坦矩阵信号的重构条件

建立基于凸优化方法重构矩阵信号X=[x₁,…,x_n]的一组充分条件,X具有列稀疏性和平坦性的结构特征,即每个列向量x_j至多具有s个非零分量、同时所有列向量的l₁范数具有相同数值。所采用的矩阵范数是|||X|||₁≡max_j|x_j|₁。工作分两部分,第一部分分别对无观测误差和有观测误差的情况,针对求解min-|||·|||₁型凸优化问题重构以上类型矩阵信号的方法,建立保障稳定性和鲁棒性的充分条件;第二部分工作建立随机观测情况下观测空间维数的下界,用以保证信号以高概率被正确重构。所得结果优于将重构向量信号的min-l₁方法直接推广到针对矩阵信号的min-l₁方法所得到的结果,并给出数值仿真验证。所针对的信号模型出现在具有定常或缓变包络波形的多输入/多输出雷达及合成孔径雷达等新应用领域,本文工作针对这类应用提供一组实用的信号重构条件。     

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.     

基于CenterNet的实时行人检测模型

针对传统目标检测模型不能同时兼顾检测速度和准确度的问题,提出一种新的PD-CenterNet模型。在CenterNet的基础上对网络结构和损失函数进行改进,在网络结构的上采路径中,设计基于注意力机制的特征融合模块,对低级特征和高级特性进行融合,在损失函数中通过设计α、γ、δ 3个影响因子来提高正样本与降低负样本的损失,以平衡正负样本的损失。实验结果表明,相比CenterNet模型,该模型在网络结构和损失函数上的准确度分别提高5.1%、9.81%。     

基于环上容错学习和GSW的层次型全同态加密方案

针对目前全同态加密方案效率不高的问题,对GSW同态加密方案进行改进,提出基于环上容错学习和GSW的层次型全同态加密方案。首先,构造基于环上容错学习困难问题的基本公钥加密方案,利用近似特征向量方法使其具有加法、乘法同态性,进一步为简化噪声增长过程的分析而引入随机化函数技术;其次,证明了基本加密方案的正确性、安全性,并详细分析了同态加法、同态乘法和同态与非门操作的正确性;最后,根据密文对应噪声项的增长情况及困难问题的安全性设置方案安全参数,并利用快速傅里叶变换降低多项式乘法运算的计算复杂度,构造出层次型(Leveled)全同态加密方案。与GSW方案相比,新方案具有更小的公钥尺寸,且同态计算每个与非门的复杂度从Õ((nL)^2.37)降低到Õ(nL²)。     

Pattern classification of non-sparse data using optimal interpolative nets

In this paper we introduce two pattern classifiers for non-sparse data (i.e. data with overlapping class distributions) which use the optimal interpolative neural network (OI-net), derived by one of the authors based on a generalized Fock (GF) space formulation. We present a statistical pattern classifier operating as a two-stage algorithm. The first stage consists of a pre-processing operation involving a k-N N editing of the original training set T. The operation results in a new training set, T_e, which in the second stage is classified by an OI-net constructed by the recursive least squares algorithm. We also propose a new data specific classifier which has an additional third computational stage, in which samples of the original training set are added to the network piece by piece until satisfactory classification results are obtained. During the computation process the training set is iteratively updated until the number of mis-classified samples is minimized. The performance of these two classifiers has been evaluated in some illustrative examples.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

一种新的模式合一算法

传统的模式合一,使用递归调用的方法,算法的时间复杂度是指数级的,因此,往往容易耗费大量的系统资源,从而造成系统的崩溃。为了解决这个问题,本文提出一种新的模式合一算法,共时间复杂度为线性的。实验结果表明,本算法可以有效地解决原来算法中存在的递归调用问题。     

带任意长度通配符的模式匹配

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.     

(p,q)-Logical completeness for output-coherent sets of (p,q)-Logical functions and an application of the set to image processing

We have previously proposed an idea of p-valued input, q-valued output threshold logic to synthesize many-valued, p-valued, logical networks, and derived the condition for (p, q)-logical completeness for the output-closed set of (p, q)-logical functions. In this paper, the condition for (p, q)-logical completeness for the output-coherent set F of (p, q)-logical functions is described, and the proof is given in almost the same way as for the output-closed set. The output-coherent set F is applied to image processing. That is, a restoration scheme is described for images to which normal random noise is added.     

Pattern generation, topology, and non-holonomic systems

We consider the problem of achieving a desired steady-state effect through periodic behavior for a class of control systems with and without drift. The problem of using periodic behavior to achieve set-point regulation for the control systems with drift is directly related to that of achieving unbounded effect for the corresponding driftless control systems. We prove that in both cases, the ability to use periodic behavior, and more generally, bounded behavior, to achieve the desired goal implies, under a certain topological condition, the non-holonomicity of the control systems. We also prove that under a regularity condition, the resulting system trajectories must be area-generating in a precise sense.     

无重叠条件严格模式匹配的高效求解算法

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法，与同类挖掘方法相比，该方法更容易发现有价值的频繁模式，其核心问题是计算给定模式在序列中的支持度或出现数，进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现，然后剪枝无用结点的方式计算模式的支持度，其计算时间复杂度为O （m×m×n×W），其中，m，n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度，从而有效地降低无重叠条件序列模式挖掘时间，提出了一种高效的算法，该算法将模式匹配问题转换为一棵网树，然后从网树的最小树根结点出发，采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现，在网树上剪枝该出现后，无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性，并将该算法的时间复杂度降低为O （m×n×W）.在此基础上，继续指明该问题还存在另外3种相似的求解策略，分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能，特别是在序列模式挖掘中，应用该方法的挖掘算法可以降低挖掘时间.     

Pattern matching in the Hamming distance with thresholds

It has long been known that pattern matching in the Hamming distance metric can be done in time, where n is the length of the text, m is the length of the pattern, and Σ is the alphabet. The classic algorithm for this is due to Abrahamson and Kosaraju. This paper considers the following generalization, motivated by the situation where the entries in the text and pattern are analog, or distorted by additive noise, or imprecisely given for some other reason: in any alignment of the pattern with the text, two aligned symbols a and b contribute +1 to the similarity score if they differ by no more than a given threshold θ, otherwise they contribute zero. We give an time algorithm for this more general version of the problem; the classic Hamming distance matching problem is the special case of θ=0.