Частота символов в строке

Частота символов в строке

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

Решение 1: С использованием словаря

def char_frequency(s: str) -> dict:
    """
    Подсчитывает частоту каждого символа в строке.
    
    Args:
        s: Входная строка
    
    Returns:
        Словарь {символ: количество}
    
    Временная сложность: O(n)
    Пространственная сложность: O(k), где k - количество уникальных символов
    """
    frequency = {}
    
    for char in s:
        # Если символ уже в словаре, увеличиваем счётчик
        # Иначе, добавляем с начальным значением 1
        frequency[char] = frequency.get(char, 0) + 1
    
    return frequency

# Тестирование
print(char_frequency("hello"))     # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
print(char_frequency("aabbcc"))    # {'a': 2, 'b': 2, 'c': 2}
print(char_frequency("aaa"))       # {'a': 3}
print(char_frequency(""))          # {}

Решение 2: С использованием defaultdict

from collections import defaultdict

def char_frequency_defaultdict(s: str) -> dict:
    """
    Использует defaultdict для упрощения кода.
    """
    frequency = defaultdict(int)
    
    for char in s:
        frequency[char] += 1
    
    # Преобразуем в обычный словарь для вывода
    return dict(frequency)

print(char_frequency_defaultdict("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

Решение 3: С использованием Counter

Самый Pythonic способ:

from collections import Counter

def char_frequency_counter(s: str) -> dict:
    """
    Использует встроенный Counter — оптимальное решение.
    """
    return dict(Counter(s))

print(char_frequency_counter("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

# Counter имеет дополнительные методы
counter = Counter("hello")
print(counter.most_common(2))  # [('l', 2), ('h', 1)]
print(counter['l'])  # 2

Решение 4: С использованием list comprehension и lambda

def char_frequency_lambda(s: str) -> dict:
    """
    Использует lambda и set для уникальных символов.
    """
    return {char: s.count(char) for char in set(s)}

print(char_frequency_lambda("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

Примечание: Этот способ менее эффективен (O(n²)), так как count() проходит по строке для каждого символа.

Решение 5: Игнорирование регистра букв

def char_frequency_case_insensitive(s: str) -> dict:
    """
    Подсчитывает частоту символов, игнорируя регистр.
    """
    s = s.lower()  # Преобразуем в нижний регистр
    
    frequency = {}
    for char in s:
        frequency[char] = frequency.get(char, 0) + 1
    
    return frequency

print(char_frequency_case_insensitive("Hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
print(char_frequency_case_insensitive("HeLLo"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

Решение 6: Исключение пробелов и специальных символов

def char_frequency_alphanumeric(s: str) -> dict:
    """
    Подсчитывает частоту только буквенно-цифровых символов.
    """
    frequency = {}
    
    for char in s:
        # Проверяем, является ли символ буквой или цифрой
        if char.isalnum():
            char = char.lower()
            frequency[char] = frequency.get(char, 0) + 1
    
    return frequency

print(char_frequency_alphanumeric("Hello, World!"))  # {'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}

Решение 7: С отсортированным результатом

def char_frequency_sorted(s: str) -> dict:
    """
    Возвращает отсортированный словарь по частоте (по убыванию).
    """
    from collections import Counter
    
    counter = Counter(s)
    # Сортируем по значению (частоте) в обратном порядке
    sorted_freq = dict(sorted(counter.items(), key=lambda x: x[1], reverse=True))
    
    return sorted_freq

print(char_frequency_sorted("hello"))  # {'l': 2, 'h': 1, 'e': 1, 'o': 1}

Сравнение производительности

import time
from collections import Counter, defaultdict

test_string = "a" * 10000 + "b" * 5000 + "c" * 3000

# Способ 1: Обычный словарь
start = time.time()
for _ in range(1000):
    freq = {}
    for char in test_string:
        freq[char] = freq.get(char, 0) + 1
print(f"Обычный словарь: {time.time() - start:.4f}s")

# Способ 2: defaultdict
start = time.time()
for _ in range(1000):
    freq = defaultdict(int)
    for char in test_string:
        freq[char] += 1
print(f"defaultdict: {time.time() - start:.4f}s")

# Способ 3: Counter
start = time.time()
for _ in range(1000):
    freq = Counter(test_string)
print(f"Counter: {time.time() - start:.4f}s")

# Способ 4: Dict comprehension (неэффективно)
start = time.time()
for _ in range(1000):
    freq = {char: test_string.count(char) for char in set(test_string)}
print(f"Dict comprehension: {time.time() - start:.4f}s")

Полное решение с тестами

from collections import Counter
from typing import Dict

def char_frequency(s: str) -> Dict[str, int]:
    """
    Подсчитывает частоту каждого символа в строке.
    
    Args:
        s: Входная строка
    
    Returns:
        Словарь вида {символ: количество}
    
    Examples:
        >>> char_frequency("hello")
        {'h': 1, 'e': 1, 'l': 2, 'o': 1}
        
        >>> char_frequency("aabbcc")
        {'a': 2, 'b': 2, 'c': 2}
    """
    return dict(Counter(s))

def test_char_frequency():
    # Базовые тесты
    assert char_frequency("hello") == {'h': 1, 'e': 1, 'l': 2, 'o': 1}
    assert char_frequency("aabbcc") == {'a': 2, 'b': 2, 'c': 2}
    assert char_frequency("aaa") == {'a': 3}
    assert char_frequency("") == {}
    assert char_frequency("a") == {'a': 1}
    
    # Тесты с специальными символами
    assert char_frequency("a1a2a3") == {'a': 3, '1': 1, '2': 1, '3': 1}
    assert char_frequency("!!!") == {'!': 3}
    
    # Тесты с пробелами
    freq = char_frequency("a a a")
    assert freq[' '] == 2
    assert freq['a'] == 3
    
    print("✓ Все тесты пройдены!")

test_char_frequency()

Advanced: Фильтрованная частота

def char_frequency_filtered(s: str, min_freq: int = 1) -> dict:
    """
    Возвращает частоту символов, которые встречаются как минимум min_freq раз.
    """
    from collections import Counter
    
    counter = Counter(s)
    return {char: freq for char, freq in counter.items() if freq >= min_freq}

print(char_frequency_filtered("hello", min_freq=2))  # {'l': 2}
print(char_frequency_filtered("aabbcc", min_freq=2))  # {'a': 2, 'b': 2, 'c': 2}

Сложность анализ

где n — длина строки, k — количество уникальных символов

Практическое применение

• Анализ текста — часто встречающиеся символы/слова
• Сжатие данных — алгоритм Хаффмана
• Криптография — анализ частоты для破解 шифров
• Проверка скудности — нет ли неиспользуемых символов
• Оптимизация баз данных — индексирование на часто используемые символы