面向關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵字近似搜索技術(shù)研究.pdf

1、近年來Web數(shù)據(jù)大量增長(zhǎng)，如何為用戶提供有效的搜索技術(shù)成為研究的熱點(diǎn)。在分布式環(huán)境下，通過數(shù)據(jù)收集，得到的Web數(shù)據(jù)主要存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中，大量來自不同數(shù)據(jù)源的Web數(shù)據(jù)，具有異構(gòu)模式。在目前的發(fā)展階段，搜索引擎是支持用戶查詢請(qǐng)求的重要手段。用戶根據(jù)興趣，通過搜索引擎接口輸入相關(guān)的關(guān)鍵字，系統(tǒng)提供快速響應(yīng)回答用戶的請(qǐng)求。很多情況下，用戶提交的請(qǐng)求不能與數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行精確匹配，例如：用戶對(duì)數(shù)據(jù)了解的程度有限、錄入的數(shù)據(jù)包含錯(cuò)誤信息、來

2、自多個(gè)數(shù)據(jù)源的數(shù)據(jù)存在不一致性等。因此，在關(guān)系數(shù)據(jù)庫(kù)上有效地支持近似關(guān)鍵字搜索帶來了一系列新的挑戰(zhàn)，諸如，面向關(guān)系數(shù)據(jù)庫(kù)的近似查詢處理，字符串近似匹配的執(zhí)行效率和查詢結(jié)果的排序等問題。本文針對(duì)上述問題進(jìn)行研究，主要工作包括以下幾點(diǎn)：
　　 (1)為改善對(duì)關(guān)系元組中字符串?dāng)?shù)據(jù)的近似查詢效率，提出一種新穎的索引結(jié)構(gòu)，簡(jiǎn)稱VGRAM（變長(zhǎng)GRAM）。與傳統(tǒng)的解決近似字符串查詢的索引方法相比，VGRAM索引不但節(jié)省了近似查詢算法的時(shí)間，

3、并且將索引的空間縮小了1倍以上。同時(shí)，該技術(shù)具有很好的可移植性，任何一個(gè)基于gram思想的近似字符串查詢算法都可以采用該索引技術(shù)并提高原有算法的執(zhí)行效率。其主要思想是：在字符串集合中，選擇高質(zhì)量的變長(zhǎng)gram來支持該集合上的查詢。重點(diǎn)研究的問題包括：如何從特定集合中選擇高質(zhì)量的gram、如何基于預(yù)選的gram將字符串分解成一組變長(zhǎng)的gram集合，以及分析兩個(gè)gram集合間的相似度同它們編輯距離間的關(guān)系。基于真實(shí)數(shù)據(jù)集上大量的實(shí)驗(yàn)測(cè)試結(jié)果

4、表明，VGRAM索引技術(shù)可以顯著地改善最新的三種經(jīng)典算法的查詢性能。
　　 (2)提出了基于代價(jià)的高質(zhì)量gram選擇技術(shù)。當(dāng)采用基于gram的倒排列表作為索引結(jié)構(gòu)時(shí)，索引項(xiàng)gram的選取直接決定索引結(jié)構(gòu)，進(jìn)而決定近似查詢的執(zhí)行效率。針對(duì)gram索引項(xiàng)集和查詢性能間的關(guān)系，提出一種計(jì)算兩個(gè)字符串公共gram數(shù)目的下限的動(dòng)態(tài)規(guī)劃算法，以提高下限值，從而獲得更快的近似匹配時(shí)間。系統(tǒng)地分析gram索引結(jié)構(gòu)對(duì)近似匹配性能的影響，并提出一個(gè)

5、自動(dòng)構(gòu)造高質(zhì)量gram索引項(xiàng)集的算法。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)展示了這些技術(shù)對(duì)查詢性能的改善。就目前所知，這是第一個(gè)基于代價(jià)分析的gram選擇方法。
　　 (3)針對(duì)有限的form查詢接口進(jìn)行查詢擴(kuò)展，提出基于form查詢接口的改菩近似搜索能力的查詢重寫技術(shù)。很多近似搜索引擎為用戶提供form接口，用戶通過form接口提交關(guān)鍵字并獲得搜索結(jié)果。返回給用戶的結(jié)果大多數(shù)是根據(jù)填寫在查詢接口中不同值域內(nèi)的關(guān)鍵字計(jì)算得到的，導(dǎo)致查詢結(jié)果的查

6、全率(recall)很低。本文提出一種數(shù)據(jù)挖掘方法，通過對(duì)歷史查詢及其結(jié)果進(jìn)行挖掘分析，得到一組查詢重寫知識(shí)，包括數(shù)據(jù)項(xiàng)樹和推理規(guī)則。利用這些重寫知識(shí)，可以對(duì)用戶查詢進(jìn)行擴(kuò)展，以提高基于form的近似搜索能力，特別是查全率。從不同Web網(wǎng)站上隨機(jī)選取的3,800篇文檔組成的測(cè)試集上的實(shí)驗(yàn)結(jié)果表明：所提出的數(shù)據(jù)挖掘和查詢重寫方法獲得的平均查準(zhǔn)率和查全率均高于80％，而假通過率低于2.0％。
　　 (4)針對(duì)關(guān)系數(shù)據(jù)表之間以及元組間

7、的數(shù)據(jù)依賴關(guān)系，提出一種支持關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵字近似搜索的語(yǔ)義評(píng)價(jià)模型，包括語(yǔ)義相關(guān)度計(jì)算和語(yǔ)義評(píng)分函數(shù)。基于提出的語(yǔ)義評(píng)分函數(shù)，提出兩種以數(shù)據(jù)塊為處理單位的Top-k搜索算法，分別為BA(Blocking Algorithm)算法和EBA(Early-stopping Blocking Algorithm)算法。EBA在BA基礎(chǔ)上引入了過濾閾值以便盡早終止算法的迭代過程。實(shí)驗(yàn)結(jié)果顯示所提出的語(yǔ)義評(píng)分函數(shù)保證了搜索結(jié)果的高查準(zhǔn)率和查全率，