When do we stop calling this counting and start calling it estimation?
> the accuracy of this technique scales with the size of the memory.
I wonder if that's proportional to the number of distinct items to count, though.
> if the [memory] is so big that it fits all the words, then we can get 100% accuracy
Yes, but then the algorithm isn't being used any more, that's just normal counting.
They counted the distinct words in Hamlet with a memory size of 100 words, about 2.5% of the number to find, and got a result that was off by 2. If you do the same with the whole of Shakespeare, again using 2.5% of the memory needed to hold all the distinct words, is the accuracy better?
Anyway, this is limited to counting, and doesn't help list what the words are, though quickly counting them first is perhaps a way to speed up the task of actually finding them?
The same thing happens with measurement. No measurement is ever exact. If I said I was measuring a count, someone would probably correct to say that I am counting.
Common speech is like that.
Publishers generally have good data about where their audience comes from. They wouldn't do this if it wasn't the best way they know of to maximise readership.