What is the process of counting the frequencies of each character which is then feeded into huffman encoding?

Question

I'm reserching about a method to decreses the time and space complexity of the process before huffman encoding where the computer have to give the frequency of each character to the code.I wanted to know the process of finding the frequency like is it done through 2 nested loops with O(n2) complexity or is it done using a more efficent way like Hash map with complexity O(n).Or is it some other way that the machine calculates the freq of the characters.

As the whole process of huffman encoding takes O(nlogn).I wanted to ask that if the character counting is also included in this process resulting in the overall time to O(n) + O(nlogn) or is it something else that the machine's internal do?

And is there any method by which the counting of frequency can be eliminated?

I tried going through the various papers but can not find the process by which the huffman gets the frequency of chacters as intput.

Answer 1

How many possible characters are there? 256? Whatever the number is, make a table of integers with that many entries. Make the integers large enough to contain the length of the longest possible input. Set them all to zero. Then make one pass through the input data, incrementing the count for each character encountered.

No language was specified in the tags, but something like:

    table[ch]++;

for each character ch in the input.