To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

From Wikipedia, the free encyclopedia

A wavelet tree on the string "abracadabra". At each node the symbols of the string are projected onto two partitions of the alphabet, and a bitvector denotes to which partition each symbol belongs. Note that only the bitvectors are stored; the strings in the nodes are only for illustratory purposes.

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,[1] it has found application in several contexts.[2][3] 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.

YouTube Encyclopedic

  • 1/3
    Views:
    76 598
    1 929
    34 897
  • Understanding Wavelets, Part 1: What Are Wavelets
  • Binary Trees
  • How to find Saturn with a webcam

Transcription

Properties

Let be a finite alphabet with . By using succinct dictionaries in the nodes, a string can be stored in , where is the order-0 empirical entropy of .

If the tree is balanced, the operations , , and can be supported in time.

Access operation

A wavelet tree contains a bitmap representation of a string. If we know the alphabet set, then the exact string can be inferred by tracking bits down the tree. To find the letter at ith position in the string :-

Algorithm access
  Input:
    - The position i in the string of which we want to know the letter, starting at 1.
    - The top node W of the wavelet tree that represents the string
  Output: The letter at position i
    if W.isLeafNode return W.letter
    if W.bitvector[i] = 0 return access(i - rank(W.bitvector, i), W.left)
    else return access(rank(W.bitvector, i), W.right)
  • "←" denotes assignment. For instance, "largestitem" means that the value of largest changes to the value of item.
  • "return" terminates the algorithm and outputs the following value.

In this context, the rank of a position in a bitvector is the number of ones that appear in the first positions of . Because the rank can be calculated in O(1) by using succinct dictionaries, any S[i] in string S can be accessed in [3] time, as long as the tree is balanced.

Extensions

Several extensions to the basic structure have been presented in the literature. To reduce the height of the tree, multiary nodes can be used instead of binary.[2] The data structure can be made dynamic, supporting insertions and deletions at arbitrary points of the string; this feature enables the implementation of dynamic FM-indexes.[4] This can be further generalized, allowing the update operations to change the underlying alphabet: the Wavelet Trie[5] exploits the trie structure on an alphabet of strings to enable dynamic tree modifications.

Further reading

  • Wavelet Trees. A blog post describing the construction of a wavelet tree, with examples.

References

  1. ^ R. Grossi, A. Gupta, and J. S. Vitter, High-order entropy-compressed text indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA), January 2003, 841-850.
  2. ^ a b P. Ferragina, R. Giancarlo, G. Manzini, The myriad virtues of Wavelet Trees, Information and Computation, Volume 207, Issue 8, August 2009, Pages 849-866
  3. ^ a b G. Navarro, Wavelet Trees for All, Proceedings of 23rd Annual Symposium on Combinatorial Pattern Matching (CPM), 2012
  4. ^ H.-L. Chan, W.-K. Hon, T.-W. Lam, and K. Sadakane, Compressed Indexes for dynamic text collections, ACM Transactions on Algorithms, 3(2), 2007
  5. ^ R. Grossi and G. Ottaviano, The Wavelet Trie: maintaining an indexed sequence of strings in compressed space, In Proceedings of the 31st Symposium on the Principles of Database Systems (PODS), 2012

External links

This page was last edited on 9 August 2023, at 13:09
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.