Таблица частот символов

Таблица частот символов показывает, сколько раз каждый символ встречается в строке. Она помогает решать задачи на подсчёт вариантов, выбор символов с заданными свойствами и анализ строк; перед изучением полезно повторить частоту символов и абсолютную частоту.

Основные понятия

Пусть дана строка длины \(n\). Рассмотрим некоторый символ \(c\). Число его появлений в строке называют абсолютной частотой символа. Например, в строке «АБРАКАДАБРА» буква «А» встречается пять раз, поэтому её абсолютная частота равна \(5\).

Относительная частота показывает долю всех символов строки, приходящуюся на символ \(c\). Она равна отношению абсолютной частоты к длине строки. Относительную частоту можно записывать десятичной дробью, процентом или обыкновенной дробью.

В таблице выше использована строка «АБРАКАДАБРА» длины \(11\). Символы перечислены без повторений, а их частоты в сумме дают \(11\).

Как построить таблицу частот

Есть два распространённых способа. Первый — ручной: выписать различные символы и для каждого посчитать появления. Второй — алгоритмический: завести массив или словарь счётчиков и просмотреть строку слева направо.

1. Определите, какие символы разрешены: например, только заглавные латинские буквы, цифры или все символы строки.
2. Создайте счётчик для каждого разрешённого символа и установите его в ноль.
3. Для каждого символа строки увеличьте соответствующий счётчик на единицу.
4. Выведите символы и ненулевые значения счётчиков.
5. Проверьте результат: сумма счётчиков должна совпадать с длиной строки.

Если алфавит заранее известен, удобно использовать массив. Для английских заглавных букв достаточно массива из \(26\) элементов. Индекс символа можно получить преобразованием в код: например, для символа \(A\) индекс равен \(0\), для \(B\) — \(1\) и так далее. Если набор символов неизвестен, удобнее словарь.

1s = input().strip()
2count = {}
3
4for ch in s:
5    count[ch] = count.get(ch, 0) + 1
6
7for ch in sorted(count):
8    print(ch, count[ch])

Таблица вариантов и подсчёт способов

В экзаменационных задачах таблицу частот часто используют как таблицу вариантов: каждому символу сопоставляют число его появлений. Если нужно выбрать одну позицию строки с заданным символом, число вариантов равно его абсолютной частоте. Если требуется выбрать позицию не с этим символом, используют дополнение: \(n-f(c)\).

Для двух условий количество вариантов зависит от того, независимы ли условия и пересекаются ли соответствующие группы. Например, число позиций с гласной буквой и цифрой одновременно равно нулю, если строка состоит только из букв и цифр. Если группы не пересекаются, их количества складывают; если одна группа является частью другой, применяют разность.

В задачах на перестановки частоты помогают заметить повторяющиеся символы. Например, если нужно определить, сколько различных символов есть в строке, надо посчитать ненулевые частоты, а не складывать сами символы. Такая задача связана со страницей подсчёт различных символов.

Разобранный пример

Ответ: чаще всего встречается \(A\), таких позиций \(4\); относительная частота \(C\) равна \(1/9\), или примерно \(11{,}1\%\). Если вопрос просит число символов, которые встречаются ровно один раз, ответ равен \(2\): это \(C\) и \(D\).

1s = "ABBAACDAB"
2count = {}
3for ch in s:
4    count[ch] = count.get(ch, 0) + 1
5
6most = max(count.values())
7print(count)
8print(most)
9print(count["C"] / len(s))

Типичные формулировки и алгоритмы

• «Какой символ встречается чаще всего?» — найти максимальное значение частоты.
• «Сколько различных символов?» — посчитать количество символов с ненулевой частотой.
• «Сколько символов встречается ровно \(k\) раз?» — подсчитать частоты, равные \(k\).
• «Сколько позиций не занято символом \(c\)?» — вычислить \(n-f(c)\).
• «Какова доля символа?» — разделить его абсолютную частоту на длину строки.
• «Какой символ встречается первым среди имеющих максимальную частоту?» — просматривать строку слева направо и обновлять ответ только при строго большем счётчике.

Связь с другими задачами по строкам

Таблица частот является базовым инструментом для проверки анаграмм: две строки являются анаграммами, если частоты всех символов в них совпадают. При проверке вхождения символа достаточно найти его частоту и проверить, что она ненулевая. В задачах на сравнение строк частоты не заменяют посимвольное сравнение, потому что одинаковые таблицы ещё не гарантируют одинаковый порядок символов.

Для более длинных условий обработки сначала строят таблицу частот, а затем выполняют дополнительные действия. Такие задачи относятся к сложной обработке строк.