Ukkonen's algorithm

Ukkonen's algorithm

In 1995, Esko Ukkonen proposed a linear-time, online algorithm for constructing suffix trees that has come to be known as Ukkonen's algorithm.

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; earlier algorithms proceeded backward from the last character. The naive implementation of this algorithm requires "O"("n"2) or even "O"("n"3) time (see Big-O notation), where "n" is the number of characters in the string, but by exploiting a number of algorithmic techniques this can be reduced to "O"("n") (linear) time.

References

* E. Ukkonen. (1995). On-line construction of suffix trees. "Algorithmica" 14(3):249-260. [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1.pdf PDF] | [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf PDF with figures]

External links

* [http://marknelson.us/1996/08/01/suffix-trees/ Fast String Searching With Suffix Trees] Mark Nelson's excellent tutorial. Has an implementation example written with C++.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Online algorithm — In computer science, an online algorithm is one that can process its input piece by piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an… …   Wikipedia

  • Online algorithm — En informatique, un algorithme online (algorithme en ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les… …   Wikipédia en Français

  • Suffix tree — In computer science, a suffix tree (also called suffix trie, PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many… …   Wikipedia

  • Algorithme de Boyer-Moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J Strother Moore[1] en 1977. Sommaire 1 Efficacité / complexité en temps 2 Fonctionnement …   Wikipédia en Français

  • Algorithme de Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Суффиксное дерево — Суффиксное дерево  бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w|  длина строки w. Содержание 1 Основные определения и описание структуры …   Википедия

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Algorithme de Needleman-Wunsch — L algorithme de Needleman Wunsch effectue un alignement global maximal de deux chaînes de caractères (appelées ici A et B). Il est couramment utilisé en bio informatique pour aligner des séquences de protéines ou de nucléotides. L algorithme a… …   Wikipédia en Français

  • Algorithme de Rabin-Karp — L algorithme de Rabin Karp est un algorithme de recherche de chaînes de caractères créé par Michael O. Rabin et Richard M. Karp. Cette méthode recherche un motif donné (ie. une sous chaîne) dans un texte grâce à une fonction de hachage. L… …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne — Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du premier caractère de la sous chaîne… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”