[公告] 博士論文研究計畫口試: 呂嘉維 (2014/2/25)

[cwlu]

清華大學資訊工程學系博士研究計劃口試

題 目: Improved Exact and Approximate String Matching Algorithms

學 生: 呂嘉維

指導教授: 李家同教授

口試委員: 李家同教授、唐傳義教授、王炳豐教授、盧錦隆教授

時 間: 103 年 02 月 25 日 (星期二) 10:00 - 12:00

地 點: 綜二館 753 會議室

論文摘要:

In this proposal, we consider two problems, exact string matching problem and
approximate string matching problem. The exact string matching problem is to
determine all of the locations of a pattern string P appearing in a text
string T. First, we propose an improved algorithm for exact string matching
problem. Our algorithm finds the optimal selective matching order of the
pattern so that we could have a better performance in the searching phase.
To find the optimal matching order, we adopt the branch and bound approach.
The experimental results show that our algorithm indeed has the smallest
character comparisons and also efficient in time as compared with other
existing exact string matching algorithms. Second, we propose an improved
algorithm for approximate string matching algorithm. The approximate string
matching problem (also called the k-difference problem) is defined as follows:
Given a text string T, a pattern string P and an error bound k, find all the
positions i's in T such that there exists a substring of T ending at position
i whose edit distance from P is less than or equal to k. We propose a new
filtration algorithm to efficiently solve the approximate string matching
problem. Our experimental results on simulated datasets of DNA sequences show
that when compared with other filtration algorithms, our filtration algorithm
has better performance on the efficiency to filter out those positions of the
text at which the pattern does not occur approximately.


--
[;32m※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw>
[;32m◆ From: cwlu @ r717g.cs.nthu.edu.tw [m
[;36mcwlu 於 2014/02/18 Tue 16:39:59 從 r717g.cs.nthu.edu.tw 修改 [m