English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54371/62179 (87%)
Visitors : 9060401      Online Users : 117
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    National Tsing Hua University Institutional Repository > 電機資訊學院 > 資訊工程學系 > 博碩士論文  >  利用非重疊的反轉進行近似字串的比對

    Please use this identifier to cite or link to this item: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86628

    Title: 利用非重疊的反轉進行近似字串的比對
    Authors: 黃詩元
    Huang, Shih-Yuan
    Description: GH02101062616
    Date: 2014
    Keywords: 近似字串比對;非重疊反轉;動態規劃
    approximate string matching;non-overlapping inversions;dynamic programming
    Abstract: 在本論文中,我們介紹並研究一個考量非重疊反轉距離(Non-overlapping Inversion Distance)的近似字串比對問題(Approximate String Matching Problem)。給一個內文t、樣版p和一個非負整數k,這個問題的目標是要去找出內文t中所有子字串的位置使得每一個子字串最多使用k個非重疊反轉(Non-overlapping Inversions)轉換成樣版p。首先,我們利用動態規劃(Dynamic Programming)的方法設計出一個演算法可以在O(nm^2 )時間且O(m^2)空間內解決這個問題,其中n是內文的長度,而m是樣版的長度。接著,我們利用一個有效率的篩選策略(Filtering Strategy)提出另一個演算法,這個演算法的時間與空間複雜度皆與我們提出的第一個演算法相同。
    In this thesis, we introduce and study the approximate string matching problem under non-overlapping inversion distance. Given a text t, a pattern p and a non-negative integer k, the goal of the problem is to find all locations in the text t that match the pattern p with at most k non-overlapping inversions. First, we use the dynamic programming approach to design an algorithm that solves this problem in O(nm^2 ) time and O(m^2) space, where n is the length of the text and m is the length of the pattern. Next, we present another algorithm based on an efficient filtering strategy that has the same worst-case time and space complexities as the first algorithm.
    URI: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86628
    Source: http://thesis.nthu.edu.tw/cgi-bin/gs/hugsweb.cgi?o=dnthucdr&i=sGH02101062616.id
    Appears in Collections:[資訊工程學系] 博碩士論文

    Files in This Item:

    File SizeFormat
    GH02101062616.pdf244KbAdobe PDF182View/Open


    SFX Query


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback