3 ms·
Interestingly, this algo has absolutely nothing whatsoever to do with "Wavelets" or even waves. The name "wavelet" stuck to it mostly only because it uses a rec
by quantadev 1y ago
Interestingly, this algo has absolutely nothing whatsoever to do with "Wavelets" or even waves. The name "wavelet" stuck to it mostly only because it uses a recursive decomposition approach which happens to be something that Wavelet does in actual wave processing. It got collectively labeled "Wavelet" when what was really meant was just "Recursive".
- jltsiren 1y ago"Wavelet tree" is not just a collective label but the name explicitly given by the authors of the paper where the data structure was first described in. At least Vitter had worked in image/video compression, where wavelet transforms and similar techniques are common. I believe the original idea was adapting those techniques for representing strings, and the wavelet tree data structure was the final outcome.
- quantadev 1y agoYou're seriously nit picking what "collective label" means? It means that name was accepted by the community.
- JohnKemeny 1y agoThe name derives from an analogy with the wavelet transform for signals, which recursively decomposes a signal into low-frequency and high-frequency components (Wikipedia).