基于相似度過濾的大數(shù)據(jù)保序匹配與檢索算法

　　伴隨大數(shù)據(jù)時代的到來，數(shù)據(jù)快速保序匹配與檢索成為眾多大數(shù)據(jù)應(yīng)用急需解決的關(guān)鍵問題，通過抽象與歸約等措施，數(shù)據(jù)對象可抽象為具有若干屬性的點(diǎn)集或序列，從而將數(shù)據(jù)匹配問題轉(zhuǎn)化為字符或數(shù)字序列匹配問題。提出一種基于相似度過濾的數(shù)據(jù)保序匹配與檢索算法，算法分三步：（l）數(shù)據(jù)轉(zhuǎn)換，基于幅值變化趨勢將原始序列轉(zhuǎn)換為二進(jìn)制，對序列中任何一個字符，通過判斷包括其前后鄰居在內(nèi)的三個點(diǎn)的關(guān)系定義二進(jìn)制序列，準(zhǔn)確反映相鄰三點(diǎn)之間的凸增長（降低）或凹增長（降低）關(guān)系；（2）數(shù)據(jù)歸約，為方便候選序列與模式序列之間的相似度計算，運(yùn)用基于幅度變化比例的數(shù)據(jù)歸約方法，將候選序列與模式序列均歸約到固定區(qū)間；（3）相似度計算，為區(qū)分不同趨勢的凸增長（降低）或凹增長（降低）幅度，通過計算候選序列與模式序列對應(yīng)點(diǎn)之間的差值絕對值之和作為相似度判斷依據(jù)，提出基于相似度過濾的快速匹配方法，尋找與模式序列變化趨勢一致的子序列集合，并按照相似度大小排序。理論分析與實驗結(jié)果表明：（1）該算法具有亞線性時間復(fù)雜度；（2）該算法能有效解決Chhabra等人算法對數(shù)據(jù)震蕩幅度失控的問題，同時解決數(shù)據(jù)序列與模式序列分段規(guī)律但整體不相似的閘題；（3）解決了Chhabra等人算法中對匹配序列排序造成的匹配結(jié)果疏漏問題。該方法不僅能更準(zhǔn)確、更多地匹配出變化趨勢一致的子字符串，同時將多個候選子串根據(jù)與模式之間的相似度進(jìn)行排序，為進(jìn)一步的數(shù)據(jù)精確檢索提供判斷依據(jù)。