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

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