[發(fā)明專利]一種新的基于相似度過濾的大數(shù)據(jù)保序匹配與檢索算法

在審

• 申請?zhí)枺?/td>: 201711348334.8
• 申請日: 2017-12-15
• 公開（公告）號: CN108052621A
• 公開（公告）日: 2018-05-18
• 發(fā)明（設(shè)計）人: 岑錦潮
• 申請（專利權(quán)）人: 佛山租我科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 佛山幫專知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44387
• 代理人: 顏春艷

本發(fā)明公開了一種新的基于相似度過濾的大數(shù)據(jù)保序匹配與檢索算法，包括(1)數(shù)據(jù)轉(zhuǎn)換,基于變化幅度趨勢的字符序列二進制轉(zhuǎn)換方法,該方法通過相鄰三個點之間的關(guān)系定義二進制序列,從而準確反映三點之間是凸增長或凹增長關(guān)系；(2)數(shù)據(jù)歸約,為方便候選序列與模式之間的相似度計算,提出基于趨勢比例的數(shù)據(jù)歸約方法,將候選序列與模式均歸約到區(qū)間[0,1],歸約后候選序列與模式的最小值均為0,最大值均為1；(3)相似度計算與過濾。為區(qū)分不同變化幅度的凸增長或凹增長之間的震蕩幅度,對歸約后的序列計算相似度并進行過濾,最終按相似度大小給出與模式匹配的各子序列集合。

技術(shù)領(lǐng)域

本發(fā)明涉及一種新的基于相似度過濾的大數(shù)據(jù)保序匹配與檢索算法。

背景技術(shù)

大數(shù)據(jù)快速匹配與檢索成為眾多大數(shù)據(jù)應(yīng)用急需解決的關(guān)鍵問題！比如視頻檢索與分析、股票分析與預(yù)測、氣候分析與預(yù)測等。盡管通過云計算、超級計算等先進基礎(chǔ)設(shè)施和并行分布式處理手段可以有效提高大數(shù)據(jù)處理的速度。但尋求一種精確、快速的匹配與檢索算法對于提高大數(shù)據(jù)應(yīng)用數(shù)據(jù)匹配和檢索精確度異常重要。通過抽象與歸約等措施。大數(shù)據(jù)應(yīng)用中的數(shù)據(jù)對象可抽象為具有若干屬性的點集或序列，進而將大數(shù)據(jù)匹配與檢索問題轉(zhuǎn)化為點集或序列的匹配與檢索。更進一步將點集抽象為一組字符或數(shù)字，問題的本質(zhì)就成為字符或數(shù)字序列的保序匹配與檢索，字符或數(shù)字序列的保序匹配是一類重要的模式匹配問題。

問題描述如下：假設(shè)給定長度為n的字符串T和長度為m的模式P，字符串保序匹配的任務(wù)是在T中找出所有與P變化趨勢一致且長度相等的子字符串u。如圖1所示，假設(shè)P＝(10,22,15,30,20,18,27),T＝(22,85,79,24,42,27,62,40,32,47,69,55,25),那么T中與P相一致的子字符串u＝(24,42,27,62,40,32,47)。針對該問題已經(jīng)有若干相關(guān)研究,Kim等人利用KMP(Knuth-Morris-Patt)算法來解決該問題,但其方法時間復(fù)雜度較高。之后Cho等人基于Boyer-Moore算法給出了該問題的亞線性解決方案。幾乎同一時期,Belazzougui等人給出了另外一種優(yōu)化的亞線性解決方法。到目前為止,該問題的最新研究是Chhabra等人給出的基于篩選的匹配算法,該算法根據(jù)公式(1)將原字符序列T＝(t1,t2,…,ti-1,ti,ti+1,…,tn)與模式P＝(p1,p2,…,pi-1,pi,pi+1,…,pn)根據(jù)前后兩個字符的大小關(guān)系轉(zhuǎn)化為相應(yīng)的二進制序列T′＝100101001100與P′＝101001。

如果后一個字符比前一個字符大,即:兩個字符之間是升序關(guān)系,則定義為1,否則為0。因此,匹配T中與P趨勢一致的子序列問題即可轉(zhuǎn)化為在T′中匹配與P′一致的子序列問題。Chhabra等人首先對P中各字符進行排序,之后按從小到大的順序核對T中對應(yīng)各字符的大小關(guān)系,任何一個數(shù)據(jù)大小順序不一致即被排除。