| 词条 | Ukkonen's algorithm |
| 释义 |
In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.[1] The algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property. The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix.[2] A simpler algorithm was found by Edward M. McCreight, going from the longest to the shortest suffix.[3] The naive implementation for generating a suffix tree going forward requires O(n2) or even O(n3) time complexity in big O notation, where n is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to O(n) (linear) time, for constant-size alphabets, and O(n log n) in general, matching the runtime performance of the earlier two algorithms. References1. ^{{Cite journal | last1 = Ukkonen | first1 = E. | title = On-line construction of suffix trees | doi = 10.1007/BF01206331 | journal = Algorithmica | volume = 14 | issue = 3 | pages = 249–260 | year = 1995 | url = http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf| pmid = | pmc = | citeseerx = 10.1.1.10.751 }} 2. ^{{Cite book | last1 = Weiner | first1 = Peter | contribution = Linear pattern matching algorithms | doi = 10.1109/SWAT.1973.13 | title = 14th Annual Symposium on Switching and Automata Theory (SWAT 1973) | pages = 1–11 | year = 1973 | contributionurl = http://airelles.i3s.unice.fr/files/Weiner.pdf| pmid = | pmc = | title-link = Symposium on Switching and Automata Theory | citeseerx = 10.1.1.474.9582 }} 3. ^{{Cite journal | last1 = McCreight | first1 = Edward Meyers| authorlink = Edward M. McCreight| title = A Space-Economical Suffix Tree Construction Algorithm | doi = 10.1145/321941.321946 | journal = Journal of the ACM| volume = 23 | issue = 2 | pages = 262–272 | year = 1976 | pmid = | pmc = | citeseerx = 10.1.1.130.8022}} External links
3 : Bioinformatics algorithms|Algorithms on strings|Substring indices |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。