Improved algorithms on strings

点击翻译按钮获取中文摘要

I conduct research into methods (algorithms) for processing sequences of letters called strings -- objects so simple that there seems to be no need of "algorithms"!  But, first of all, strings are ubiquitous: a text file, a computer program (millions of letters), a book (in English or Chinese), the human genome (3 billion letters), one day's e-mail traffic (trillions of letters).  Secondly, efficient processing of strings is essential: repeating substrings in a genome may be of great biological/genetic significance, phrases may need to be identified/changed in a text file or computer program, books may need to be searched for significant phrases, e-mail traffic may need to be searched for undesirable messages (spam).For 18 years I have been designing such algorithms.  Current and future research focusses on three main areas:(1) Using recent insights into the nature of "regularities" in strings, I seek new methods to efficiently compute repeating substrings -- with applications particularly to computational biology, data mining and data compression.  Essentially I seek a more precise mathematical understanding of periodicity in strings.(2) The "suffix array" is a specialized data structure used to improve the efficiency of string algorithms.  I seek new efficient algorithms that use suffix arrays, again with frequent application to computational biology and many other areas.(3) In many problems that arise in practice, it may be necessary to process strings that contain "indeterminate" (not fully defined) entries.  I seek faster more effective algorithms for doing pattern-matching and other operations on these indeterminate strings.