(18.210.12.229) 您好!臺灣時間:2021/03/05 12:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:徐玉玲
研究生(外文):Yu-Ling Hsu
論文名稱:有效的實數縮放之字串比對演算法
論文名稱(外文):An Efficient Real Scaled String Matching Algorithm
指導教授:王有禮
指導教授(外文):Yue-Li Wang
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:46
中文關鍵詞:字串比對縮放演算法
外文關鍵詞:String matchingScaleAlgorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:110
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
本文搜尋廣泛地使用在科技上,例如:電腦科學、多媒體圖書館和web搜尋等,本文提出如何在本文中找出所有可能縮放大小下出現的pattern,此縮放大小加入適合實數縮放,本文將合適的實數縮放分為大於等於一和小於等於一兩種情況加以探討,並利用實數縮放索引樹(Real Scaled Indexing Tree, RSIT)來舉例說明,子字串在各種縮放大小下與本文比對結果是否吻合。在給定本文長度為n和pattern長度為m下,本文時間複雜度為O(n^3)。
Text searching is used on a wide variety of technologies, such as computer science, multimedia library, web search, etc. This thesis proposes how to find all possible patterns that appear under the real scales in text. On our algorithm, we consider two cases of real scales. One of them contains the scale range is greater than or equal to 1. The other case contains the range is less than or equal to 1. By using the Real Scaled Indexing Tree (RSIT), we can determine whether a substring under every scale can match the text or not. Assume that the lengths of text and pattern length are n and m, respectively. The time complexity is O(n^3).
誌謝 I
論文名稱:有效的實數縮放之字串比對演算法 II
Title of Thesis: An Efficient Real Scaled String Matching Algorithm III
目錄 IV
圖目錄 VI
第一章、緒論 1
1.1 研究動機 1
1.2 研究背景 1
1.3 論文架構 2
第二章、文獻探討 4
2.1 符號定義 4
2.1.1 字串長度壓縮表示法 4
2.1.2 比對 4
2.1.3 k倍縮放 4
2.1.4 完全比對 5
2.1.5 線性時間的縮放比對 5
2.2 相關研究 6
2.2.1 可縮放字串比對 6
2.2.2 縮放與排列字串比對 7
2.2.3 兩個字尾中最大的共同字首 10
2.2.4 實數比對 12
2.2.5 實數縮放索引樹 14
第三章、有效的實數縮放之字串比對演算法 17
3.1 實數縮放大於等於一 17
3.2 實數縮放小於等於一 27
3.3 在各種實數縮放下pattern與本文間的轉換關係 32
3.3.1 實數縮放大於等於一 32
3.3.2 實數縮放小於等於一 33
第四章、證明與分析時間複雜度 35
4.1 實數縮放大於等於一 35
4.2 實數縮放小於等於一 37
第五章、結論 41
參考文獻 43
[1] M. I. Abouelhoda, S. Kurtz, E. Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms 2 (2004) 53–86.
[2] A. V. Aho, J. E. Hopcroft, J. D. Ullman, On finding lowest common ancestors in trees, Annual ACM Symposium on Theory of Computing Proceedings of the fifth annual ACM symposium on Theory of computing (1973), 253 - 265.
[3] A. Amir, A. Butman, Moshe Lewenstein, Real scaled matching, Information Processing Letters 70, 1999, pp.185-190.
[4] A. Amir, G. Calinescu, Alphabet independent and dictionary scaled matching, in: Proc. 7th Annual Symposium on Combinatorial Pattern Matching (CPM 96), 1996, pp. 320–334.
[5] A. Amir, G.M. Landau, U. Vishkin, Efficient pattern matching with scaling, J. Algorithms 13 (1) (1992) 2–32.
[6] A. Apostolico, Z. Galil (Eds.), Pattern Matching Algorithms, Oxford University Press, 1997.
[7] M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms 57 (2005) 75–94.
[8] R.S. Boyer, J.S. Moore, A fast string searching algorithm,Comm. ACM 20 (1977) 762–772.
[9] A. Butman, R. Eres, G..M. Landau, Scaled and permuted string matching, Information Processing Letters 92, 2004, pp.293-297.
[10] H. Chim, X. Deng, A New Suffix Tree Similarity Measure for Document Clustering, International World Wide Web Conference Proceedings of the 16th international conference on World Wide Web(2007), 121 – 130.
[11] F.Y.L. Chin, Alfredo De Santis, Anna Lisa Ferrara, N.L. Ho, S.K. Kim, A simple algorithm for the constrained sequence problems, Information Processing Letters 90 (2004) 175-179.
[12] F.Y.L. Chin, N.L. Ho, T.W. Lam, P.W.H. Wong, M.Y. Chan, Efficient constrained multiple sequence alignment with performance guarantee, in: Proceedings of the IEEE Computer Society Conference on Bioinformatics, IEEE Computer Society (2003) 337–346.
[13] M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994.
[14] T. Eilam-Tzoreff and U. Vishkin, Matching Patterns in a String Subject to Multi-linear Transformations, Theoretical Computer Science, Vol. 60, 1988, pp. 231-254.
[15] D. Gusfield, Algorithms on Strings, Trees, and SequencesComputer Science and Computational Biology, Cambridge University Press, 1997.
[16] D. Harel and R. E. Tarjan, Fast Algorithms for Finding Nearest Common Ancestors, SIAM J. Comp., Vol.13, 1984, pp. 338-355.
[17] D.S. Hirschberg, Algorithms for the longest common subsequence problem, J. ACM 24 (4) (1977) 664–675.
[18] E. Horowitz, S. Sahni, Fundamentals of Data Structures in Pascal, 4th ed., Freeman, 1994.
[19] J.W. Hunt, T.G. Szymanski, A fast algorithm for computing longest common subsequences, Comm. ACM 20 (1977) 350–353.
[20] R. Karp, M.O. Rabin, Efficient randomized pattern-matching algorithms, IBM J. Res. Dev. (1987) 249–260.
[21] T. Kasai, G.. Lee, H. Arimura, S. Arikawa and K. Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Lecture Notes in Computer Science 2089(2001), 181-192.
[22] D.E. Knuth, J.H. Morris, V.R. Pratt, Fast pattern matching in strings, SIAM J. Comput. 6 (1977) 323–350.
[23] G. M. Landau and U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, Vol. IO, No. 2, June 1989, pp. 157-169.
[24] R.C.T. Lee, R.C. Chang, S.S. Tseng, Y.T. Tsai, Introduction to the design and analysis of algorithms (second edition), 旗標出版社 (2004) 404-407.
[25] R. Lin and S. Olariu, A simple optimal parallel algorithm to solve the lowest common ancestor problem, Lecture Notes in Computer Science 497(1991) 455-461.
[26] E. M. McCreight, A space-economical sufhx tree construction algorithm, Journal of the ACM, 23, 1976, pp. 262-272.
[27] J.H. Morris, V.R Pratt, A linear pattern-matching algorithm, Technical Report 40 (1970), University of California, Berkeley.
[28] B. Phoophakdee, M. J. Zaki, Genome-scale disk-based suffix tree indexing, International Conference on Management of Data Proceedings of the 2007 ACM SIGMOD international conference on Management of data(2007), 833 - 844.
[29] B. Schieber and U. Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization, SIAM J. Comp., Vol. 17, 1988, pp. 1253-1262.
[30] D.M. Sunday, A very fast substring search algorithm, Communications of the ACM . 33(8) (1990) 132-142.
[31] C.Y. Tang, C.L. Lu, M.D.T. Chang, Y.T. Tsai, Y.J. Sun, K.M. Chao, J.M. Chang, Y.H. Chiou, C.M. Wu, H.T. Chang, W.I. Chou, Constrained multiple sequence alignment tool development and its application to RNase family alignment, J. Bioinformation Computing. Biol. 1 (2003) 267–287.
[32] Yin-Te Tsai, The constrained longest common subsequence problem, Information Processing Letters 88 (2003) 173-176.
[33] B.-F. Wang, J.-J. Lin, and S.-C. Ku, Efficient algorithm for the scaled indexing problem, Journal of Algorithm 52, 2004, pp.82-100.
[34] P. Weiner, Linear Pattern Matching Algorithm, Prot. 14 IEEE Symposium on Switching and Automata Theory, 1973, pp. l-11.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔