PrepBro
← Назад к вопросам

Частотная тройка слов

2.3 Middle🔥 81 комментариев
#Python Core

Условие

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

Пример

Текст: "abba com mother bill mother com abba dog abba mother com"

Тройки: (abba, com, mother) встречается 3 раза

Ответ: (abba, com, mother)

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Частотная тройка слов

Эта задача требует подсчёта частоты встречаемости групп из трёх слов в тексте. Поскольку порядок слов не имеет значения, нужно использовать нормализованные наборы (кортежи) для подсчёта.

Алгоритм

  1. Разбиваем текст на слова
  2. Проходим скользящим окном размером 3
  3. Сортируем каждую тройку, чтобы получить уникальный ключ (порядок не имеет значения)
  4. Подсчитываем частотность каждой тройки
  5. Возвращаем тройку с максимальной частотой

Решение 1: Простое (O(n) временная сложность)

from collections import Counter
from typing import Tuple, Optional

def find_most_frequent_triple(text: str) -> Optional[Tuple[str, str, str]]:
    """Находит тройку слов, встречаемую чаще всего.
    
    Args:
        text: str - исходный текст со словами
    
    Returns:
        Tuple[str, str, str] - наиболее частая тройка или None
    """
    words = text.split()
    
    # Если слов меньше чем 3, тройку не составить
    if len(words) < 3:
        return None
    
    # Подсчитываем частотность троек
    triple_counts = Counter()
    
    # Проходим скользящим окном
    for i in range(len(words) - 2):
        # Берём тройку и сортируем её
        triple = tuple(sorted([words[i], words[i+1], words[i+2]]))
        triple_counts[triple] += 1
    
    # Находим наиболее частую тройку
    if triple_counts:
        return triple_counts.most_common(1)[0][0]
    
    return None

# Пример использования
text = "abba com mother bill mother com abba dog abba mother com"
result = find_most_frequent_triple(text)
print(result)  # (abba, com, mother)

Решение 2: С детализацией результатов

def find_top_k_triples(text: str, k: int = 5) -> list:
    """Находит k наиболее частых троек с их частотами.
    
    Args:
        text: str - исходный текст
        k: int - количество результатов
    
    Returns:
        List[Tuple[Tuple[str, str, str], int]] - список троек и их частот
    """
    words = text.split()
    
    if len(words) < 3:
        return []
    
    triple_counts = Counter()
    
    for i in range(len(words) - 2):
        triple = tuple(sorted([words[i], words[i+1], words[i+2]]))
        triple_counts[triple] += 1
    
    # Возвращаем k самых частых
    return triple_counts.most_common(k)

# Пример
text = "abba com mother bill mother com abba dog abba mother com"
result = find_top_k_triples(text, k=3)
for triple, count in result:
    print(f"{triple}: {count}")
    # (abba, com, mother): 3
    # (bill, mother, com): 1
    # ... остальные

Решение 3: Для больших файлов (с потоковой обработкой)

Если файл очень большой и не помещается в памяти:

def find_most_frequent_triple_from_file(
    filepath: str, 
    chunk_size: int = 1000000
) -> Optional[Tuple[str, str, str]]:
    """Обрабатывает большой файл порциями.
    
    Args:
        filepath: str - путь к файлу
        chunk_size: int - размер порции слов
    
    Returns:
        Tuple[str, str, str] - наиболее частая тройка
    """
    triple_counts = Counter()
    words_buffer = []
    
    with open(filepath, r, encoding=utf-8) as f:
        for chunk in iter(lambda: f.read(chunk_size), ):
            words = chunk.split()
            words_buffer.extend(words)
            
            # Обрабатываем полные тройки в буфере
            while len(words_buffer) >= 3:
                triple = tuple(sorted(words_buffer[:3]))
                triple_counts[triple] += 1
                words_buffer.pop(0)
    
    # Обрабатываем оставшиеся слова
    while len(words_buffer) >= 3:
        triple = tuple(sorted(words_buffer[:3]))
        triple_counts[triple] += 1
        words_buffer.pop(0)
    
    return triple_counts.most_common(1)[0][0] if triple_counts else None

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

from collections import defaultdict

def find_most_frequent_triple_dict(text: str):
    """Альтернативный подход с defaultdict."""
    words = text.split()
    
    if len(words) < 3:
        return None
    
    triple_counts = defaultdict(int)
    
    for i in range(len(words) - 2):
        triple = tuple(sorted([words[i], words[i+1], words[i+2]]))
        triple_counts[triple] += 1
    
    # Находим максимум
    most_frequent = max(triple_counts.items(), key=lambda x: x[1])
    return most_frequent[0]

Анализ сложности

  • Временная сложность: O(n) - где n это количество слов

    • Проход по словам: O(n)
    • Сортировка тройки: O(1) так как всегда 3 элемента
    • Counter операции: O(1) в среднем

  • Пространственная сложность: O(m) - где m это количество уникальных троек

    • В худшем случае m = n - 2

Вариации и расширения

1. N-граммы (вместо троек):

def find_most_frequent_ngram(text: str, n: int = 3):
    """Находит наиболее частую n-грамму."""
    words = text.split()
    
    if len(words) < n:
        return None
    
    ngram_counts = Counter()
    
    for i in range(len(words) - n + 1):
        ngram = tuple(sorted(words[i:i+n]))
        ngram_counts[ngram] += 1
    
    return ngram_counts.most_common(1)[0][0]

2. С порядком (не сортируем):

def find_most_frequent_triple_ordered(text: str):
    """Находит тройку с учётом порядка слов."""
    words = text.split()
    
    if len(words) < 3:
        return None
    
    triple_counts = Counter()
    
    for i in range(len(words) - 2):
        # БЕЗ сортировки
        triple = (words[i], words[i+1], words[i+2])
        triple_counts[triple] += 1
    
    return triple_counts.most_common(1)[0][0]

Примеры полного решения

# Тест 1
text1 = "abba com mother bill mother com abba dog abba mother com"
result1 = find_most_frequent_triple(text1)
assert result1 == (abba, com, mother)

# Тест 2: без повторений
text2 = "a b c d e f"
result2 = find_most_frequent_triple(text2)
assert result2 == (a, b, c)  # Первая встреченная

# Тест 3: одна тройка повторяется
text3 = "x y z x y z x y z"
result3 = find_most_frequent_triple(text3)
assert result3 == (x, y, z)  # Встречается 3 раза

Ключевые моменты на интервью

  • Нормализация порядка: Сортировка для получения уникального ключа
  • Граничные случаи: Текст из менее чем 3 слов
  • Масштабируемость: Потоковая обработка для больших файлов
  • Counter vs defaultdict: Выбор инструмента по удобству
  • N-граммы: Обобщение решения для любого размера группы
Частотная тройка слов | PrepBro