可延伸標記語言之關鍵字搜尋與編碼機制研究

Abstract

可延伸標記語言(XML)現今已被廣泛地使用於資料儲存與轉換。為了從XML文件中擷取有意義的資訊，許多關鍵字搜尋機制因此被提出來討論。一般來說，XML 文件可被視為一棵樹狀結構，而最小最低共同祖先(SLCA)關鍵字搜尋是一種常用的方法，它可以根據給定的關鍵字來找出合適的子樹回傳給使用者。然而在SLCA 機制下，所有被回傳的子樹裡的節點都被視為等同重要，因此又有新概念建構子被提出，進而只回傳有意義節點而非整棵子樹。在本論文中，我們提出兩個方法MinMap 以及SingleProbe 來改進找尋有意義節點的時間效能。此外，當XML 樹的寬度很大且關鍵字個數也多的情況下，子集合偵測是一個自然衍生出來的問題。我們同時也提出一個有效率的方法來處理此情況，同時實作到MinMap方法裡，並稱為MinMap+方法。此外，傳統的SLCA 關鍵字搜尋只允許AND 運算子。在本論文裡，我們同時針對使用NOT 運算子之關鍵字搜尋來擷取有意義的資訊，並提出一個演算法找出有效且有意義的節點。根據一個對XML 文件的觀察，我們將節點分成有效的與無效的，而只有有效的節點才有資格成為被回傳的節點。因為NOT 運算子的使用，關鍵字搜尋變得更為複雜，因此我們也討論單調性以及一致性在我們定義的架構中的變化。我們同時亦實作所有的方法來做實驗測試，以證明我們提出的方法的效能。根據實驗結果，MinMap 以及SingleProbe都比之前的方法來得有效率，而MinMap+也被證實當XML 樹寬度很大且關鍵字個數也多時，能夠大幅改善時間效能。此外，關於使用NOT 運算子之關鍵字搜尋的部份，我們也證明我們所提出的方法能夠比之前的方法找出更合理的資訊。 另一方面，編碼機制的運用允許我們快速的決定兩個節點之間的結構關係，而不用整個XML 樹都重新訪視一遍。也就是XML 樹上的每一個節點都會被配置一個獨一無二的編碼，並利用此編碼決定任二個節點之間的結構關係。這些結構關係包含文件順序、祖先子孫、父子以及兄弟。目前最常見的編碼機制可分為兩大類：包含式以及字首式，其中杜威碼是字首式的代表。這兩種編碼機制都因它們簡單以及有效率而被廣泛地使用，但它們仍然有被改善的空間。在本論文裡，我們也提出一個基於完整樹的編碼機制，並稱為CT(complete-tree)編碼機制。我們提出的編碼機制相當簡潔且緊密。實驗結果顯示CT 編碼機制可以有效地支援所有結構關係的偵測，同時在大部份的情況下它也有最佳的空間效能表現。