quantadev 2 days 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".

2
JohnKemeny 1 day ago

The name derives from an analogy with the wavelet transform for signals, which recursively decomposes a signal into low-frequency and high-frequency components (Wikipedia).

jltsiren 2 days 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 1 day ago

You're seriously nit picking what "collective label" means? It means that name was accepted by the community.

bawolff 1 day ago

Doesn't really seem like a nitpick to me. Your description of the situation feels a bit misleading.

quantadev 1 day ago

Sounds like you haven't quite found a mistake yet. Keep thinking. Maybe you'll think of something.