臺灣博碩士論文加值系統

對差異性查詢(difference detection)、主動式資料庫(active database)、版本管理(version control)及組態管理(configuration management)而言，藉著比較資料的snapshot來偵測資料的更動是一個相當重要的要求。從目前來看，用來處理結構化資料的這些結構大都以樹狀、圖形等可以用來處理多維度或非線性資料的資料結構為主，而其中不是以ordered labeled tree來代表結構化資料，就是以unordered labeled tree來代表結構化資料，然而，但就實際處理的狀況來說，結構化資料中可能同時存在list和set的資料需求，但卻沒有可以同時處理這種同時具有ordered及unordered狀況的資料表示結構，並且結構化資料的更動偵測會因使用者的不同應用狀況及不同要求而有所不同，單就以一種結構來代表，可能不能完全符合需求。本文就在於對可能同時需要ordered及unordered狀況的結構化資料的這方面的需求提出一個探索性的研究，並實際發展一個系統來驗證我們的論點。

第一章 緒論3
1.1研究動機3
1.2 研究範圍5
1.3 文章結構8
第二章 相關文獻的探討9
2.1線性資料的更動偵測9
2.1.1 word-to-word Comparison9
2.1.2 String-to-string Comparison10
2.1.3 A simple string-to-string comparison with Longest Common Sequence14
2.2非線性資料的更動偵測22
2.2.1 Tree comparison22
2.2.2 Ordered Tree Comparison24
2.2.3 Unordered Tree Comparison28
2.3結論30
第三章 概論32
3.1問題定義35
3.2 編輯操作(Edit Operations)37
3.3 編輯稿40
3.4 成本模式42
第四章 合理性編輯稿45
4.1編輯的處理階段46
4.2排列小孩順序53
4.3編輯稿演算法55
第五章 合適的配對58
5.1配對標準60
5.2 A simple matching algorithm63
5.3 Try-all-solution matching algorithm66
5.4 Quick matching algorithm72
第六章 系統發展77
6.1 系統結構77
6.2一個完整的範例79
6.2.1原始文件79
6.2.2樹狀的結構化資料81
6.2.3 配對處理及編輯稿84
第七章 結論及未來展望88
參考文獻89
附錄Ａ LATEX文件範例92

[ACN 1967] Alberga, Cyril, N. String smilarity and misspellings. Comm.
ACM, Vol.10,Number 5, May 1967,pp302-313.

[BG 1976] Billy E. Gilett. Introducion to operations research ---a
computer-oriented algorithmic approach. McGraw-HILL Series,
1976.

[Blair 1960] Blair, Charles R. A program for correcting spelling errors.
Information and Control 3, Mar. 1960,pp 60-67

[CGM 1997] S.S.Chawathe, H.Garcia-Molina. Meaningful change detection in
structured data. ACM SIGMOD 1997.

[CGRMW 1996] S.S.Chawathe, A. Rajaraman,H.Garcia-Molina,and J. Widom.
Change detection in hierarchically structured information.
ACM SIGMOD, June 1996, pp493-504.

[CK 1982] Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial
Optimization: Algorithms and Complexity, Prentice-hall Inc,
1982.

[FT 1996] F. Douglis, T. Ball. Tracking and viewing changes on the web.
In Proceedings of 1996 USENIX Technical Conference, Jan 1996.

[HLM 1970] Howard L. Morgan. Spelling Correction in Systems Programs.
Comm. ACM, Vol.13,Number 2, Feb 1970,pp90-94

[KDW 1996] Kaizhong Zhang, Dennis Shasha,Tsong-Li Wang. Internal
Journalof Foundations of Computer Science. Vol.7, No.1,
1996,pp43-57

[KDWF 1994] Kaizhong Zhang, Dennis Shasha,Tsong-Li Wang, Frank Y.Shih.
Exact and Approximation algorithms for ordered tree
matching.IEEE Transactions on Systems, Man, and Cybernetics.
Vol.24, April 1994.

[KRD 1992] Kaizhong Zhang, Rick Statman,Dennis Shasha. On the editing
distance between unordered labeled tree. Informaton
Processing letters, Vol 42, 1992,pp133-139

[KT 1979] kuo-Chung Tai. The tree-to-tree correction problem. Journal
of ACM, Vol. 26, No. 3, July 1979,pp422-433

[Mye 1986] E.Mayers. An O(ND) difference algorithm and its variations.
Algorithmica, Vol. 1, No. 2, 1986, pp251-266

[RS 1983] Robert Sedgewick. Algorithms. Addison-Weiley Publishing,1983.

[SB 1970] S.B. Needleman and C.D. Wunsch. A general method applicable
to the search for similiarities in the amino acid sequence
of two proteins Journal of Molecular Biology,vol,48, 1970,
pp443-453

[SZ 1990] Dennis Shasha, Kaizhong Zhang. Fast algorithms for the unit
cost editing diatance between trees. Journal of algorithms,
Vol.11, No.4, 1994,pp581-612

[TK 1968] T.K. Vintsyuk. Speech discrimination by dynamic programming.
Cybernetics, Vol. 4, 1968, pp55-57

[WAG 1975] Roy Lowrance, Robert A. Wagner. An extension of the
string-to-string correction problem. Journal of ACM, Vol.22,
No.2, April 1975, pp177-183

[WDC 1997] Tsong-Li Wang, Dennis Shasha, George J.S. Chang, Kaizhong
Zhang,Liam Relihan, andd Girlsh Patel. Structural Matching
and discovery in Document Database,ACM Sigmod 1997,pp560-563

[WF 1974] Wagner, R.A., and Fischer, M.J. The string-to-string
correction problem. Journal of ACM, Vol 21, Number 1, Jan.
1974,pp168-173

[WMG 1990] S. Wu, U. Manber, and G. Myers. An O(NP) sequence comparison
algorithm. Information Processing Letters, 35:pp317-323, Sep
1990

[WT 1984] Walter F. Tichy. The sting-to-string correction problem with
block moves. ACM Transactions on Computer Systems, Vol.2,
Nov 1984, pp 309-321

[ZS 1989] Kaizhong Zhang,Dennis Shasha. Simple fast algorithms for the
editing distance between trees and related problems. SIAM
Journal on Computing, Vol. 18,No.6,Dec 1989, pp 1245-1262