Есть ли лучший способ рассчитать частоту всех символов в файле?

Question

Хорошо, скажем, у меня есть текстовый файл (не обязательно содержащий все возможные символы), и я хотел бы рассчитать частоту каждого символа, а после вычисления частоты мне нужно получить доступ к каждому символу и его частоте. от самого частого к наименее частому. Символы не обязательно являются символами ASCII, они могут быть произвольными байтовыми последовательностями, хотя все они имеют одинаковую длину.

Я собирался сделать что-то вроде этого (в псевдокоде):

function add_to_heap (symbol)
    freq = heap.find(symbol).frequency
    if (freq.exists? == true)
        freq++
    else
        symbol.freq = 1
        heap.insert(symbol)

MaxBinaryHeap heap
while somefile != EOF
    symbol = read_byte(somefile)
    heap.add_to_heap(symbol)
heap.sort_by_frequency()

while heap.root != empty
    root = heap.extract_root()
    do_stuff(root)

Мне было интересно: есть ли лучший, более простой способ вычислить и сохранить, сколько раз каждый символ встречается в файле?

Answer 1

Вы всегда можете использовать HashMap вместо кучи. Таким образом, вы будете выполнять операции, которые находятся в O (1) для каждого найденного символа вместо O (log n), где n - это количество элементов, находящихся в данный момент в куче.

Однако, если число различных символов ограничено разумным числом (1 байт идеален, 2 байт должен быть в порядке), вы можете просто использовать массив этого размера и снова иметь O (1), но с значительно ниже постоянные затраты.

Answer 2

Если вы ищете «лучшее» решение на основе времени выполнения, вот что я бы посоветовал:

Когда вы читаете файл, ваши символы должны быть отсортированы (или хешированы)по значению самих символов, а не их частоты.Это позволит вам быстро найти текущий символ в списке уже увиденных символов, а не искать по всему списку.Вы также должны иметь эту первоначальную структуру, способную выполнять быстрые вставки - я бы порекомендовал двоичное дерево хеша.

После того, как вы прочитали все свои символы, вам следует переключить порядок, чтобы он основывался начастота считает.Я прочитал бы все в массив и затем выполнил бы сортировку на месте, но есть множество эквивалентных способов сделать это.

Надеюсь, это поможет!