| dbo:abstract
|
- In der Informatik versteht man unter einem Wavelet Tree eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden und von einem Bitvektor auf ein beliebiges Alphabet. Erstmals beschrieben wurde die Datenstruktur als Hauptbestandteil zur komprimierten Volltextindexierung und gilt als geringfügige Generalisierung einer Datenstruktur aus der algorithmischen Geometrie. Der Wavelet Tree lässt sich rekursiv beschreiben. Jeder Knoten verteilt die Zeichenfolge auf seine zwei Nachfolger. Dabei wird das verbleibende Alphabet unter den Kind-Knoten aufgeteilt. Ein Bitvektor speichert für jedes Zeichen die zugeordnete Partition. Der Namensursprung der Trees liegt bei der Wavelet-Transformation, eingesetzt zur Reduzierung von Bilddaten und zur approximativen Evaluierung von Ausdrücken der relationalen Algebra. (de)
- Un arbre d'ondelettes (en anglais wavelet tree) est une structure de données qui contient des données compressées dans une représentation presque optimale, appelée succincte. Cette structure étend les opérations de parcours et de sélection définies sur les (en) compressés à des alphabets quelconques. Introduits à l'origine pour représenter des tableaux des suffixes compressés, les arbres d'ondelettes ont trouvé des applications dans des contextes variés. L'arbre d'ondelettes est défini en partitionnant récursivement l'alphabet en deux sous-ensembles; les feuilles correspondent aux symboles de l'alphabet, et à chaque nœud est associé un vecteur de bits compressé qui mémorise le sous-ensemble auquel appartiennent les symboles. Le nom dérive de l'analogie avec la transformée en ondelettes des signaux qui décompose récursivement un signal en composantes de fréquences basses et hautes. (fr)
- The Wavelet Tree is a succinct data structure to store strings in compressed space. It generalizes the and operations defined on bitvectors to arbitrary alphabets. Originally introduced to represent compressed suffix arrays, it has found application in several contexts. The tree is defined by recursively partitioning the alphabet into pairs of subsets; the leaves correspond to individual symbols of the alphabet, and at each node a bitvector stores whether a symbol of the string belongs to one subset or the other. The name derives from an analogy with the wavelet transform for signals, which recursively decomposes a signal into low-frequency and high-frequency components. (en)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7724 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In der Informatik versteht man unter einem Wavelet Tree eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden und von einem Bitvektor auf ein beliebiges Alphabet. Der Namensursprung der Trees liegt bei der Wavelet-Transformation, eingesetzt zur Reduzierung von Bilddaten und zur approximativen Evaluierung von Ausdrücken der relationalen Algebra. (de)
- Un arbre d'ondelettes (en anglais wavelet tree) est une structure de données qui contient des données compressées dans une représentation presque optimale, appelée succincte. Cette structure étend les opérations de parcours et de sélection définies sur les (en) compressés à des alphabets quelconques. Le nom dérive de l'analogie avec la transformée en ondelettes des signaux qui décompose récursivement un signal en composantes de fréquences basses et hautes. (fr)
- The Wavelet Tree is a succinct data structure to store strings in compressed space. It generalizes the and operations defined on bitvectors to arbitrary alphabets. Originally introduced to represent compressed suffix arrays, it has found application in several contexts. The tree is defined by recursively partitioning the alphabet into pairs of subsets; the leaves correspond to individual symbols of the alphabet, and at each node a bitvector stores whether a symbol of the string belongs to one subset or the other. (en)
|
| rdfs:label
|
- Wavelet Tree (de)
- Arbre d'ondelettes (fr)
- Wavelet Tree (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
