Ukkonen's algorithm
http://dbpedia.org/resource/Ukkonen's_algorithm an entity of type: Software
En ciencias de la computación, el algoritmo de Ukkonen es un algoritmo on-line, con tiempo de computación lineal, para construir un de una cadena . Este algoritmo fue propuesto por en 1995. Anteriormente existían dos algoritmos capaces de construir el árbol de sufijos de una cadena en tiempo lineal, estos son el (1973) y el (1976). Pero el algoritmo de Ukkonen se destaca por ser más sencillo y por tener la característica de ser en línea.
rdf:langString
En informatique, l'algorithme d'Ukkonen construit incrémentalement en temps linéaire l'arbre des suffixes d'un mot. Cet algorithme a été proposé par (en) en 1995. L'algorithme est essentiellement la linéarisation d'une version naïve quadratique d'un algorithme de construction de l’arbre des suffixes.
rdf:langString
In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995. 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 proceeded backward from the last character to the first one from the shortest to the longest suffix. A simpler algorithm was found by Edward M. McCreight, going from the longest to the shortest suffix.
rdf:langString
Algorytm Ukkonena – algorytm budowy drzewa sufiksowego zaproponowany przez Esko Ukkonena w 1995 roku. Algorytm ten działa w czasie liniowym i jest algorytmem online. Algorytm zaczyna budowę od drzewa sufiksowego dla pierwszego znaku ciągu. W kolejnych krokach algorytm przekształca drzewo tak, aby było ono drzewem sufiksowym dla ciągu o 1 znak dłuższego. W momencie gdy algorytm doda ostatni znak ciągu drzewo sufiksowe jest gotowe. Taki sposób budowy drzewa zapewnia algorytmowi jego właściwość "on-line", poprzednie algorytmy budowały drzewo sufiksowe zaczynając od ostatniego znaku ciągu. Naiwna implementacja algorytmu ma złożoność O(n2), natomiast zaproponowana przez Ukkonena O(n).
rdf:langString
Em ciência da computação, o algoritmo de Ukkonen é um de tempo linear para construção de árvores de sufixos, proposto por em 1995. O algoritmo inicia com uma árvore de sufixos implícita contendo o primeiro caracter da string. Então ele prossegue através da string adicionando caracteres sucessivos até que a árvore esteja completa. Esta ordem de adição dos caracteres dá ao algoritmo de Ukkonen a sua propriedade "online". Anteriormente, os algoritmos procediam de forma inversa, do último caractere ao primeiro, seja do maior ao menor sufixo ou do menor ao maior sufixo. A implementação ingênua para a geração de uma árvore de sufixos requer tempo O(n²) ou mesmo O(n3), aonde n é o tamanho da string. Ao explorar um número de técnicas algorítmicas, Ukkonen reduziu para um tempo O(n) (linear), par
rdf:langString
rdf:langString
Algoritmo de Ukkonen
rdf:langString
Algorithme d'Ukkonen
rdf:langString
Algorytm Ukkonena
rdf:langString
Algoritmo de Ukkonen
rdf:langString
Ukkonen's algorithm
xsd:integer
4067031
xsd:integer
1092492022
rdf:langString
En ciencias de la computación, el algoritmo de Ukkonen es un algoritmo on-line, con tiempo de computación lineal, para construir un de una cadena . Este algoritmo fue propuesto por en 1995. Anteriormente existían dos algoritmos capaces de construir el árbol de sufijos de una cadena en tiempo lineal, estos son el (1973) y el (1976). Pero el algoritmo de Ukkonen se destaca por ser más sencillo y por tener la característica de ser en línea.
rdf:langString
En informatique, l'algorithme d'Ukkonen construit incrémentalement en temps linéaire l'arbre des suffixes d'un mot. Cet algorithme a été proposé par (en) en 1995. L'algorithme est essentiellement la linéarisation d'une version naïve quadratique d'un algorithme de construction de l’arbre des suffixes.
rdf:langString
In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995. 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 proceeded backward from the last character to the first one from the shortest to the longest suffix. A simpler algorithm was found by Edward M. McCreight, going from the longest to the shortest suffix.
rdf:langString
Algorytm Ukkonena – algorytm budowy drzewa sufiksowego zaproponowany przez Esko Ukkonena w 1995 roku. Algorytm ten działa w czasie liniowym i jest algorytmem online. Algorytm zaczyna budowę od drzewa sufiksowego dla pierwszego znaku ciągu. W kolejnych krokach algorytm przekształca drzewo tak, aby było ono drzewem sufiksowym dla ciągu o 1 znak dłuższego. W momencie gdy algorytm doda ostatni znak ciągu drzewo sufiksowe jest gotowe. Taki sposób budowy drzewa zapewnia algorytmowi jego właściwość "on-line", poprzednie algorytmy budowały drzewo sufiksowe zaczynając od ostatniego znaku ciągu. Naiwna implementacja algorytmu ma złożoność O(n2), natomiast zaproponowana przez Ukkonena O(n).
rdf:langString
Em ciência da computação, o algoritmo de Ukkonen é um de tempo linear para construção de árvores de sufixos, proposto por em 1995. O algoritmo inicia com uma árvore de sufixos implícita contendo o primeiro caracter da string. Então ele prossegue através da string adicionando caracteres sucessivos até que a árvore esteja completa. Esta ordem de adição dos caracteres dá ao algoritmo de Ukkonen a sua propriedade "online". Anteriormente, os algoritmos procediam de forma inversa, do último caractere ao primeiro, seja do maior ao menor sufixo ou do menor ao maior sufixo. A implementação ingênua para a geração de uma árvore de sufixos requer tempo O(n²) ou mesmo O(n3), aonde n é o tamanho da string. Ao explorar um número de técnicas algorítmicas, Ukkonen reduziu para um tempo O(n) (linear), para alfabetos de tamanho constante, e O(n log n) em geral.
xsd:nonNegativeInteger
7747
