一种基于频域特征的子序列检索方法和系统

摘要

本发明提供一种基于频域特征的子序列检索方法和系统，检索方法包括：将滑动窗口在数据库的所有序列上依次滑动，滑动窗口任一次滑动获取一个与滑动窗口长度相等的子序列；对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；遍历频域特征序列集合，基于降维规则对频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；通过空间索引方法对降维表示的序列进行检索。本发明能够有效减少虚假匹配结果的数量，使得降维表示后的序列之间的距离更加接近原序列之间的实际距离，进而减小子序列近似查询的响应时间。本发明具备应对大数据的能力，且具有更好的实用价值。

权利要求

1.一种基于频域特征的子序列检索方法，其特征在于，包括：将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；

对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；

遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；

通过空间索引方法对所述降维表示的序列进行检索；

所述遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列之前还包括：获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；

获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；

将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

2.根据权利要求1所述的检索方法，其特征在于，所述基于降维规则对所述频域特征序列集合进行降维进一步包括：通过如下降维规则对所述频域特征序列集合进行降维：

其中，RFi,j为降维表示后的序列值，RFi,j包括R个，Fi,0为所述频域特征序列集合所包括的第i条频域特征序列中位置下标为0的元素，Pos[j]为所述幅值位置集合的第j个元素，1≤i≤R，0≤j≤f-1，f为所述预设个数，R为所述频域特征序列集合包括的频域特征序列的个数，Fi,Pos[j]为所述频域特征序列集合包括的第i条频域特征序列中位置下标为Pos[j]的元素，w为滑动窗口的长度，RFi,j的长度与f的值相等。

3.根据权利要求1所述的检索方法，其特征在于，所述指定维度通过下式获取：其中，L为指定维度，w为滑动窗口的长度， 是下取整符号。

4.根据权利要求1所述的检索方法，其特征在于，通过下式获取所述频域特征序列集合的平均序列：其中，为所述频域特征序列集合的平均序列，R为所述频域特征序列集合包括的频域特征序列的个数，Fi＝[Fi,0,Fi,1,…,Fi,w-1]，1≤i≤R，w为滑动窗口的长度，Fi为所述频域特征序列集合中的第i个频域特征序列，Fi的长度与滑动窗口的长度相等。

5.根据权利要求1所述的检索方法，其特征在于，所述一个与所述滑动窗口长度相等的子序列通过下式表示：Si[offset:offset+w-1],1≤i≤N,0≤offset≤Len(Si)-w；

其中，Si为一个与所述滑动窗口长度相等的子序列，offset为滑动窗口的移动偏置，w为滑动窗口的长度，N为数据库的序列个数，Len(Si)为一个与所述滑动窗口长度相等的子序列的长度，S[i:j]为序列S从第i维到第j维的子序列。

6.根据权利要求1所述的检索方法，其特征在于，所述数据库的每一序列的任一维度的值为实数。

7.一种基于频域特征的子序列检索系统，其特征在于，包括：获取子序列模块，用于将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；

获取频域特征序列模块，用于对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；

降维模块，用于遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；

检索模块，用于通过空间索引方法对所述降维表示的序列进行检索；

所述检索系统还包括：

获取平均序列模块，用于获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；

获取第一幅值集合模块，用于获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；

记录模块，用于将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

说明书

一种基于频域特征的子序列检索方法和系统

技术领域

[0001] 本发明涉及计算机数据管理技术领域，更具体地，涉及一种基于频域特征的子序列检索方法和系统。

背景技术

[0002] 子序列近似查询的一般做法是：输入一个查询序列Q和不相似度阈值ε，输出数据库中所有满足匹配条件的子序列。匹配条件是指匹配序列和查询序列之间的不相似度不超过阈值ε。度量两条序列之间的不相似度的一种常见做法是使用序列距离函数，一种典型的序列距离函数是欧式距离，即给定两个等长序列 和 它们之间基于欧式距离的不相似度为

[0003] 子序列近似查询的一种暴力解法是直接检索数据库中的所有子序列，计算并判断每个子序列是否满足匹配条件，找出所有满足匹配条件的子序列后输出结果。这种解法在实际应用中往往是不可行的，因为序列本质上是高维数据，直接处理这些高维数据会带来昂贵的计算和存储成本，并且使得查询响应时间过长而难以接受。

[0004] 一种常见的替代方法是基于序列降维表示的子序列检索方法：(1)先对查询序列和数据库中序列的所有子序列进行降维表示；(2)然后对降维表示后的子序列进行检索，得到与降维表示后的查询序列相匹配的降维表示后的子序列集合A；(3)最后将集合A还原成原空间对应的子序列集合B，并通过一定的后处理，从子序列集合B中过滤出真正满足匹配条件的子序列集合C。记数据库中实际所有满足匹配条件的子序列集合为D，保证上述方法正确性的关键是要保证集合B是集合D的超集，即集合D中的每一个元素都在集合B中，而集合B中可能包含集合D中没有的元素，从而保证了从集合B中过滤出来的集合C等于集合D，即保证子序列近似查询结果没有遗漏。

[0005] 一种序列降维表示方法是基于频域特征，其一般思路是首先通过某种方法提取序列的频域特征，构成频域特征序列，然后利用频域特征的性质进行降维表示。提取序列的频域特征的常见做法之一是使用离散傅里叶变换(Discrete Fourier Transform，DFT)，例如，一个长度为n的序列 的离散傅里叶变换为一个长度为n的频域特征序列 其中

[0006] 离散傅里叶变换具有一些良好的性质，使得当离散傅里叶变换被用在基于频域特征的序列降维表示方法中时，能够最终保证基于序列降维表示的子序列检索方法的正确性。下面进行说明：首先离散傅里叶变换满足帕萨瓦尔定理，即如果 是序列 的离散傅里叶变换，那么有 其次，离散傅里叶变换是一种线性变换，因此如果序列 的离散傅里叶变换为 序列 的离散傅里叶变换为 那么序列 的离散傅里叶变换为 上述两条性质可以推出公式：
该公式的意义是：如果将两个等长序列 之间的距离定义为欧式距离，那么离散傅里叶变换就具有保距性，即变换前后两个序列之间的距离保持不变。因此，如果对频域特征序列进行降维，选择其中的f维(f

[0007]

[0008] 该不等式说明降维表示后的序列之间的距离是原序列之间距离的一种保守估计，即如果 则一定有 因此在做基于距离的子序列近似查询时，所有满足匹配条件的序列在基于离散傅里叶变换进行降维表示之后，仍然满足匹配条件。这个性质被用在基于频域特征的子序列检索方法中，能够保证子序列近似查询结果没有遗漏。

[0009] 另一方面，由于 因此在对降维表示后的序列进行检索时，得到的满足匹配条件 的序列还原到原空间时，
不一定满足匹配条件 即在检索过程中引入了虚假匹配结果，因此检
索方法的最后一步往往是通过后处理过滤掉虚假匹配结果。但是如果虚假匹配结果的数量过大，会导致后处理的计算量过大，从而降低方法的性能。

[0010] 现实生活中遇到的信号常常可以被归类成有色噪声，有色噪声的频域能量更多地分布在低频段，因此一种常见的基于频域特征的序列降维表示方法是直接选取频域特征序列的前f维。这种基于噪声模型的方法存在的问题是：特征选择比较粗糙，且缺乏数据适应性，可能造成对原序列之间距离的过低估计，从而产生大量的虚假匹配结果，增加子序列近似查询的响应时间。

[0011] 频域特征序列的性质中重要的一条是：实数序列的离散傅里叶变换具有共轭对称性，即如果序列 是一个实数序列，长度为N，并且 是序列 的离散傅里叶变换，那么X(N-m)＝X*(m),m＝0,1,…,N-1，其中*是共轭符号。该性质可以被用于提高降维表示后的序列之间的距离与原序列之间的距离的接近程度。例如，如果采用选取频域特征序列前f维的序列降维表示方法，得到的降维表示后的两个序列之间的距离就是 而如果利用共轭对称性，在前f维的适当维度上乘以 就可以在不改变原维度数量f的情况下，将降维表示后的两个序列之间的距离近似提高成

发明内容

[0012] 本发明提供一种克服上述问题的一种基于频域特征的子序列检索方法和系统。

[0013] 根据本发明的一个方面，提供一种基于频域特征的子序列检索方法，包括：将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；通过空间索引方法对所述降维表示的序列进行检索；所述遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列之前还包括：获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

[0014] 优选地，所述基于降维规则对所述频域特征序列集合进行降维进一步包括：通过如下降维规则对所述频域特征序列集合进行降维：

[0015]

[0016] 其中，RFi,j为降维表示后的序列值，RFi,j包括R个，Fi,0为所述频域特征序列集合所包括的第i条频域特征序列中位置下标为0的元素，Pos[j]为所述幅值位置集合的第j个元素，1≤i≤R，0≤j≤f-1，f为所述预设个数，R为所述频域特征序列集合包括的频域特征序列的个数，Fi,Pos[j]为所述频域特征序列集合包括的第i条频域特征序列中位置下标为Pos[j]的元素，w为滑动窗口的长度，RFi,j的长度与f的值相等。

[0017] 优选地，所述指定维度通过下式获取：

[0018]

[0019] 其中，L为指定维度，w为滑动窗口的长度， 是下取整符号。

[0020] 优选地，通过下式获取所述频域特征序列集合的平均序列：

[0021]

[0022] 其中， 为所述频域特征序列集合的平均序列，R为所述频域特征序列集合包括的频域特征序列的个数，Fi＝[Fi,0,Fi,1,…,Fi,w-1]，1≤i≤R，w为滑动窗口的长度，Fi为所述频域特征序列集合中的第i个频域特征序列，Fi的长度与滑动窗口的长度相等。

[0023] 优选地，所述一个与所述滑动窗口长度相等的子序列通过下式表示：

[0024] Si[offset:offset+w-1],1≤i≤N,0≤offset≤Len(Si)-w；

[0025] 其中，Si为一个与所述滑动窗口长度相等的子序列，offset为滑动窗口的移动偏置，w为滑动窗口的长度，N为数据库的序列个数，Len(Si)为一个与所述滑动窗口长度相等的子序列的长度，S[i:j]为序列S从第i维到第j维的子序列。

[0026] 优选地，所述数据库的每一序列的任一维度的值为实数。

[0027] 根据本发明的另一个方面，提供一种基于频域特征的子序列检索系统，包括：获取子序列模块，用于将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；获取频域特征序列模块，用于对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；降维模块，用于遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；检索模块，用于通过空间索引方法对所述降维表示的序列进行检索；所述检索系统还包括：获取平均序列模块，用于获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；获取第一幅值集合模块，用于获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；记录模块，用于将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

[0028] 本发明提供的一种基于频域特征的子序列检索方法和系统，使用有色噪声模型实现基于频域特征的序列降维表示，在子序列近似查询过程中引入大量的虚假匹配结果的问题，能够有效减少虚假匹配结果的数量，使得降维表示后的序列之间的距离更加接近原序列之间的实际距离，进而减小子序列近似查询的响应时间。本发明具备应对大数据的能力，且具有更好的实用价值。

附图说明

[0029] 图1为本发明实施例中的一种基于频域特征的子序列检索方法的流程图；

[0030] 图2为本发明实施例中的一种基于频域特征的子序列检索方法的流程框图；

[0031] 图3为本发明实施例中的一种基于频域特征的子序列检索系统的模块图；

[0032] 图4为本发明实施例中的一种基于频域特征的子序列检索电子设备的结构示意图。

具体实施方式

[0033] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0034] 针对现有的子序列检索方法中存在的问题，一个优化思路是通过设计更好的基于频域特征的序列降维表示方法，使得降维表示后的序列之间的距离更加接近原序列之间的距离，即使得 更加接近 从而减少虚假匹配结果，进而减少后处理的计算量，最终减小子序列近似查询的响应时间。

[0035] 为了设计更好的基于频域特征的序列降维表示方法，有以下两条思路：(1)进一步挖掘和利用频域特征序列的性质；(2)除了基于有色噪声模型的方法之外，基于数据自适应方法，挖掘实际序列中的统计信息。

[0036] 图1为本发明实施例中的一种基于频域特征的子序列检索方法的流程图，如图1所示，检索方法包括：将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；对每一子序列进行离散傅里叶变换(discrete Fourier transform，DFT)，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；通过空间索引方法对所述降维表示的序列进行检索。

[0037] 一般地，记一个序列为S，长度为Len(S)，数据库的序列的第i维为S[i],0≤i≤Len(S)-1。序列的每一维为实数，即S[i]∈R1。序列S从第i维到第j维的子序列记作S[i:j]。记数据库中有N个这样的数据序列S1,S2,…,SN。

[0038] 具体地，傅里叶分析方法是信号分析的最基本方法，傅里叶变换是傅里叶分析的核心，通过它把信号从时间域变换到频率域，进而研究信号的频谱结构和变化规律。

[0039] 需要说明的是，本发明实施例中的空间索引方法是本领域的现有的空间索引方法，包括多种。

[0040] 本发明提供的一种基于频域特征的子序列检索方法，通过获取频域特征序列，利用离散傅里叶变换的共轭对称性，实现基于频域特征的序列降维表示，然后结合现有的空间索引方法，实现对降维表示后的序列的检索，最终得到一种使得子序列近似查询的响应时间更小的子序列检索方法。本发明使用有色噪声模型实现基于频域特征的序列降维表示，在子序列近似查询过程中引入大量的虚假匹配结果的问题，能够有效减少虚假匹配结果的数量，使得降维表示后的序列之间的距离更加接近原序列之间的实际距离，进而减小子序列近似查询的响应时间。本发明具备应对大数据的能力，且具有更好的实用价值。

[0041] 基于上述实施例，所述遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列之前还包括：获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

[0042] 具体地，获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中具体可由下述说明具体解释：

[0043] 计算 前L维的各维分量的幅值，得到L个幅值分量 对这L个幅值分量从大到小进行排序，得到 其中0≤pi≤L-1,0≤i≤L-1。
用集合Pos记录排在前f个的幅值分量的位置，即Pos＝{p0,p1,…,pf-1}。记Pos的第j个元素为Pos[j],0≤j≤f-1，f为预设值。需要说明的是，在本发明的实施例中，f≤L。

[0044] 基于上述实施例，所述基于降维规则对所述频域特征序列集合进行降维进一步包括：通过如下降维规则对所述频域特征序列集合进行降维：

[0045]

[0046] 其中，RFi,j为降维表示后的序列值，RFi,j包括R个，Fi,0为所述频域特征序列集合所包括的第i条频域特征序列中位置下标为0的元素，Pos[j]为所述幅值位置集合的第j个元素，1≤i≤R，0≤j≤f-1，f为所述预设个数，R为所述频域特征序列集合包括的频域特征序列的个数，Fi,Pos[j]为所述频域特征序列集合包括的第i条频域特征序列中位置下标为Pos[j]的元素，w为滑动窗口的长度，RFi,j的长度与f的值相等。

[0047] 进一步地，遍历结束时得到R个长度为f的基于频域特征的降维表示后的序列RF1,RF2,…,RFR。

[0048] 基于上述实施例，所述指定维度通过下式获取：

[0049]

[0050] 其中，L为指定维度，w为滑动窗口的长度， 是下取整符号。

[0051] 基于上述实施例，通过下式获取所述频域特征序列集合的平均序列：

[0052]

[0053] 其中， 为所述频域特征序列集合的平均序列，R为所述频域特征序列集合包括的频域特征序列的个数，Fi＝[Fi,0,Fi,1,…,Fi,w-1]，1≤i≤R，w为滑动窗口的长度，Fi为所述频域特征序列集合中的第i个频域特征序列，Fi的长度与滑动窗口的长度相等。

[0054] 基于上述实施例，所述一个与所述滑动窗口长度相等的子序列通过下式表示：

[0055] Si[offset:offset+w-1],1≤i≤N,0≤offset≤Len(Si)-w；

[0056] 其中，Si为一个与所述滑动窗口长度相等的子序列，offset为滑动窗口的移动偏置，w为滑动窗口的长度，N为数据库的序列个数，Len(Si)为一个与所述滑动窗口长度相等的子序列的长度，S[i:j]为序列S从第i维到第j维的子序列。

[0057] 基于上述实施例，所述数据库的每一序列的任一维度的值为实数。

[0058] 作为一个优选实施例，下面以一个具体的例子来具体说明本发明提供的基于频域特征的子序列检索方法。图2为本发明实施例中的一种基于频域特征的子序列检索方法的流程框图，本实施如图2所示。

[0059] 首先，记一个序列为S，长度为Len(S)，序列的第i维为S[i],0≤i≤Len(S)-1。序列的每一维为实数，即S[i]∈R1。序列S从第i维到第j维的子序列记作S[i:j]。记数据库中有N个这样的数据序列S1,S2,…,SN。

[0060] 本实施例中，以数据库中有且只有一个长度为10的序列S为例进行说明。该数据序列为：

[0061] S＝[11,15,14,17,19,20,24,28,31,34,36,42],Len(S)＝10。

[0062] 进一步地，定义一个在数据序列上滑动的窗口，滑动窗口的长度固定，记为w，w不超过数据库中所有序列的最小长度。滑动窗口的移动偏置记为offset。将滑动窗口在数据库中的所有序列上依次滑动，每次滑动得到一个长度为w的子序列Si[offset:offset+w-1],1≤i≤N,0≤offset≤Len(Si)-w，对该子序列进行离散傅里叶变换，对应得到一个长度为w的频域特征序列。随着窗口的滑动，最终得到R个频域特征序列的集合，记为集合F＝{F1,F2,…,Fi,…,FR}，其中每一个集合元素Fi＝[Fi,0,Fi,1,…,Fi,w-1]是一个长度为w的频域特征序列。

[0063] 本实施例中，取w＝9，因此offset的可能取值为0、1。随着滑动窗口在序列S上滑动，得到两个长度为9的子序列，依次离散傅里叶变换之后得到频域特征序列的集合[0064] F＝{F1,F2}＝{[179,-3.62+i30.48,-11.1+i13.84,-11.5+i2.6,-13.78+i1.55,-13.78-i1.55,-11.5-i2.6,-11.1-i13.84,-3.62-i30.48],[202,-4.74+i35.81,-11.56+i14.12,-8+i8.66,-9.19+i1.7,-9.19-i1.7,-8-i8.66,-11.56-i14.12,-4.74-i35.81]}。

[0065] 进一步地，计算集合F的平均

[0066]

[0067] 本实施例中，计算

[0068]

[0069] 进一步地，计算 是下取整符号。预设参数f，要求f≤L。计算 前L维的各维分量的幅值，得到L个幅值分量 对这L个幅值分量从大到小进
行排序，得到 其中0≤pi≤L-1,0≤i≤L-1。用集合Pos记录排在
前f个的幅值分量的位置，即Pos＝{p0,p1,…,pf-1}。记Pos的第j个元素为Pos[j],0≤j≤f-
1。

[0070] 本实施例中， 用户给定参数f＝2。计算 前5维的各维 分 量 的 幅 值 ， 得 到 5 个 幅 值 分 量
对 这 5 个 幅 值 分 量 从 大 到 小 进 行 排 序 ，得 到
用集合Pos记录排序排在前2个的幅值分量的位置，
得到Pos＝{0,1}。

[0071] 进一步地，遍历步骤集合F，对每一个序列Fi＝[Fi,0,Fi,1,…,Fi,w-1],i＝1,2,…,R，按照如下规则计算得到降维表示后的新序列RFi＝[RFi,0,RFi,1,…,RFi,f-1]。RFi,j(1≤i≤R,0≤j≤f-1)的计算规则如下：

[0072]

[0073] 于是遍历结束时得到R个长度为f的基于频域特征的降维表示后的序列RF1,RF2,…,RFR。

[0074] 本实施例中，计算规则为 遍历集合F中的序列，对序列F1计算得到 对序列F2
计算得到 于是遍历结束时得到2(＝
R)个长度为2(＝f)的基于频域特征的降维表示后的序列。

[0075] 进一步地，结合现有的空间索引方法实现对降维表示后的序列的检索，完成子序列近似查询。

[0076] 本实施例中可以结合R*-tree来实现对降维表示后的序列的检索，完成子序列近似查询。

[0077] 基于上述实施例，图3为本发明实施例中的一种基于频域特征的子序列检索系统的模块图，如图3所示，包括：获取子序列模块，用于将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；获取频域特征序列模块，用于对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；降维模块，用于遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；检索模块，用于通过空间索引方法对所述降维表示的序列进行检索。

[0078] 基于上述实施例，所述检索系统还包括：获取平均序列模块，用于获取所述频域特征序列集合的平均序列，所述平均序列包括与所述滑动窗口长度相等个数维度的分量；获取第一幅值集合模块，用于获取所述平均序列前指定维度的分量的幅值，并对所述前指定维度的分量的幅值按照数值大小进行排序，获取第一幅值集合；记录模块，用于将所述第一幅值集合前预设个数的幅值的位置记录入幅值位置集合中。

[0079] 基于上述实施例，图4为本发明实施例中的一种基于频域特征的子序列检索电子设备的结构示意图，如图4所示，本发明还提供一种基于频域特征的子序列检索电子设备，包括：存储器和处理器，所述处理器和所述存储器通过总线完成相互间的通信；所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令能够执行如上述任一所述的检索方法，例如包括：将滑动窗口在数据库的所有序列上依次滑动，所述滑动窗口任一次滑动获取一个与所述滑动窗口长度相等的子序列；对每一子序列进行离散傅里叶变换，获取每一子序列对应的频域特征序列，所有子序列对应的频域特征序列构成频域特征序列集合；遍历所述频域特征序列集合，基于降维规则对所述频域特征序列集合进行降维，获取基于频域特征的降维表示的序列；通过空间索引方法对所述降维表示的序列进行检索。

[0080] 本发明提供的一种基于频域特征的子序列检索方法和系统，通过获取频域特征序列，利用离散傅里叶变换的共轭对称性，实现基于频域特征的序列降维表示，然后结合现有的空间索引方法，实现对降维表示后的序列的检索，最终得到一种使得子序列近似查询的响应时间更小的子序列检索方法。本发明使用有色噪声模型实现基于频域特征的序列降维表示，在子序列近似查询过程中引入大量的虚假匹配结果的问题，能够有效减少虚假匹配结果的数量，使得降维表示后的序列之间的距离更加接近原序列之间的实际距离，进而减小子序列近似查询的响应时间。本发明具备应对大数据的能力，且具有更好的实用价值。本发明具有数据自适应性，结合数据来实现基于频域特征的序列降维表示，摆脱了基于有色噪声模型方法的不确定性。本发明能与多种现有的空间索引方法相结合，具有很强的适用性。本发明通过对序列进行降维表示，避免了维数灾难，能够更好地与现有的空间索引方法相结合。

[0081] 最后，本发明的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。