- 學位論文
樹狀結構編輯距離在可擴展標記語言文件上之分析研究
Analysis of Tree Edit Distance on XML Data
摘要
在資訊科學研究中，樹狀結構比較問題廣泛地出現在各種領域，其中也包括了可擴展標記語言文件的處理。而在解決樹狀結構比較問題時，樹狀結構編輯距離是一個常見且重要，並可用來量化樹狀結構差異的方法。因此，在比較大量串流可擴展標記語言文件時，有效率的樹狀結構嵌入演算法就相當重要。 在本篇論文中，我們提出一個新的樹狀距離嵌入演算法，用來比較從串流可擴展標記語言文件中取得的無標記有序樹狀結構。與最近的研究相較，我們的貢獻是在不增加時間及空間複雜度的情況下，簡化得到樹狀距離的過程。同時我們也分析了這個演算法在樹狀結構編輯距離上造成失真的上下界以及誤差的機率。
並列摘要
The problem of comparing tree structures occurs in various areas in computer science and engineering, including the application to XML data processing. To solve this problem, tree edit distance is a common and significant measurement defining the difference between two tree structures quantitatively. Efficient tree edit distance embedding algorithms are therefore of significant importance in comparing large streaming XML document trees. In this thesis, we propose a new algorithm to obtain edit distance between unlabeled ordered trees derived from streaming XML data. In comparison with the previous work, our contribution lies in simplifying the procedure of obtaining the tree edit distance without increasing the time and space complexities. The upper and lower bounds as well as the error probability of our algorithm are also analyzed in this thesis.
參考文獻
延伸閱讀
- Liu, L. C. (2016). 樹狀結構評價法的延伸及其在訂價或有請求權與分析實證現象上的應用 [doctoral dissertation, National Chiao Tung University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0030-0803201714403038
- 洪志緯（2011）。應用於無線感測網路環境之樹狀結構資料聚集機制〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2011.00053
- 劉禎宇（2019）。利用樹狀結構在密度導向分群的動態演算法設計〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-0206202016175919
- Li, W. C. (2010). A Study on Compound Distance Problems between Two Mixture Trees [master's thesis, National Chi Nan University]. Airiti Library. https://doi.org/10.6837/NCNU.2010.00268
- 魏良縈（2010）。Analysis of XML Tree Transformation Method:from Marked Ladder Diagrams to Marked Graphs〔碩士論文，國立交通大學〕。華藝線上圖書館。https://doi.org/10.6842/NCTU.2010.00464