Словарь и телеграф

Прошлая глава остановилась на полпути. Сколько раз в «Войне и мире» встречается слово «война», Python ответил за долю секунды: 52. А посчитать каждое слово романа не вышло. Два параллельных списка — слова и их счётчики — работали тем медленнее, чем длиннее становился текст: чтобы найти счётчик слова, приходилось перебирать все известные слова с самого начала. На всём романе это больше полуминуты, на библиотеке — часы.

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

ТЧК и ЗПТ — не опечатки. Телеграмму оплачивали по словам, и знаки препинания в ней писали словами: «тчк» — точка, «зпт» — запятая; за них платили, как за любое другое слово. Из-за этой платы и появился телеграфный стиль, где нет ни одного лишнего слова. Ответ на эту телеграмму займёт у нас полглавы. Начнём с того, как устроен сам телеграф, — в его истории словарь появился раньше, чем в Python.

Морристаун, 1838. Словарь, который выбросили

Вейл посчитал буквы, чтобы раздать коды. Мы сделаем то же самое с «Войной и миром» и проверим, достались ли короткие коды частым русским буквам. Но сначала — сама азбука: тот же словарь, только для букв.

Кодовая таблица

Азбука Морзе — это таблица: букве соответствует код. Телеграфисту нужно по букве быстро найти её код. Хранить такую таблицу можно списком пар, как правила ELIZA в прошлой главе, но тогда каждую букву пришлось бы искать перебором. Для таблиц «что чему соответствует» в Python есть отдельная структура:

Фигурные скобки, внутри пары через запятую: слева от двоеточия — что ищем, справа — что найдём. Такая структура называется словарём, левая часть пары — ключом, правая — значением. Обращение code["о"] похоже на индекс списка, только в квадратных скобках вместо номера места стоит сам ключ. len считает пары, in спрашивает, есть ли такой ключ. Именно ключ: "---" in code ответит False, значения in не смотрит.

Словарь можно пополнять и исправлять на ходу.

Присваивание по новому ключу добавляет запись, по старому — заменяет значение: двух записей с одним ключом в словаре не бывает. Записи хранятся в том порядке, в каком их добавляли. Обращение к ключу, которого нет, кончается ошибкой KeyError, и трейсбек называет этот ключ. Когда отсутствие ключа — обычное дело, спрашивают методом get: он возвращает значение, если ключ есть, и второй аргумент, если нет.

Вот вся русская азбука и функция, которая переводит телеграмму в точки и тире. Буквы в коде разделены пробелами, слова — косой чертой.

Точки и тире различаются длительностью. Её меряют в тактах: точка звучит один такт, тире — три, пауза между сигналами внутри буквы — один такт, между буквами — три, между словами — семь. Наберите свою телеграмму в аппарате ниже и сравните, во сколько тактов обходятся «е» и «ш».

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

Касса литер

Проверим. Наша касса литер — сам роман: 2,9 миллиона символов. Сначала сделайте ставку.

Считать будем словарём: ключ — буква, значение — сколько раз она встретилась. Вот приём на коротком слове. Нажмите «Шаги» и проследите, как растёт словарь: новая буква получает запись со счётчиком 1, знакомая — прибавку.

Вся работа — в строке counts[ch] = counts.get(ch, 0) + 1. Справа get достаёт старый счётчик буквы или ноль, если буква ещё не встречалась; слева результат кладётся обратно под тот же ключ. Эту строку стоит запомнить: так считают что угодно — буквы, слова, посетителей сайта, ошибки в журнале сервера. Теперь весь роман. Модуль курса cs.texts отдаёт его одной строкой.

Почти два с четвертью миллиона букв примерно за полсекунды. Букву «ё» мы заменили на «е»: в азбуке у них общий код. Осталось расставить буквы по частоте. Словарь сам сортироваться не умеет, но его можно перебрать: метод items() отдаёт пары «ключ — значение», и цикл раскладывает каждую пару на две переменные, как кортеж в главе 6. Сложим пары в список наоборот — сначала число, потом буква, — и отсортируем по убыванию: кортежи сравниваются сначала по первому элементу.

Таблицу MORSE мы спрятали в модуль курса cs.morse, там же функция duration: она считает такты кода, точки по одному, тире по три, и паузы между ними. Сюрприз ждёт в первой же строке таблицы. Самая частая буква русского текста, «о», передаётся тремя тире, это одиннадцать тактов: дольше звучат коды всего шести букв, и каждая из них встречается реже 2 %. «Е» и «т» короткие, как и положено частым. А «о» не повезло. Русскую азбуку 1856 года строили не по частотам: русские буквы получили коды сходных латинских, и «о» досталось длинное латинское O.

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

Метод values() отдаёт одни значения словаря, без ключей; его брат keys() — одни ключи. В f-строке :, разбивает число на тройки цифр, :.0% показывает дробь в процентах.

Те же 32 кода, розданные по правилу Вейла, передали бы роман на 10 % быстрее. Вернитесь к аппарату, включите переключатель «по частотам» и наберите свою телеграмму ещё раз. Самый выгодный код по частотам строит с нуля алгоритм Хаффмана. Его мы построим в главе 23, в главе 47 он станет частью ZIP, а в «Царице наук» есть подробный рассказ о том, почему он лучший из возможных.

Почему словарь быстрый

Мы посчитали почти два с четвертью миллиона букв за полсекунды, а в прошлой главе параллельные списки задыхались на сорока тысячах слов. Разница в том, как ищется счётчик. Представьте двух конторщиков. Первый ведёт книгу учёта: строка за строкой «слово — сколько раз». Чтобы прибавить единицу слову, он ведёт пальцем по книге сверху вниз, пока не найдёт его строку. Второй держит картотеку: на каждое слово свой ящик с надписью, и он открывает нужный ящик сразу. Дайте им один и тот же текст — знаменитое небо Аустерлица.

Картотеке на каждое слово хватает одного взгляда, а книгу приходится просматривать тем дольше, чем больше в ней строк. На отрывке из 116 слов книга требует почти в тридцать раз больше просмотров. На всём романе первый конторщик просмотрел бы 3,2 миллиарда строк — по семь тысяч на каждое слово, — а второй открыл бы 448 тысяч ящиков, по одному на слово. Как словарь узнаёт, где лежит ящик, не перебирая остальные, мы разберём в главе 16: внутри у него хеш-таблица. Пока достаточно знать одно: поиск по ключу в словаре почти не зависит от того, сколько в нём записей.

Ответ редакции

Теперь можно ответить на первую телеграмму. Слова романа режет функция из конца прошлой главы — она лежит в модуле курса под именем words: нижний регистр, знаки препинания по краям срезаны.

Сотые доли секунды вместо полуминуты с лишним — тот же приём, что с буквами, только ключи теперь слова. Слово «война» встречается 52 раза, «мир» — 46, а «Наташа» — 826. И ещё один раз в святочной сцене, где Мелюковы встречают ряженых возгласом «А Наташа-то!»: наша функция считает «наташа-то» отдельным словом. Что считать словом — решение программиста, и от него зависят ответы; поисковики, о которых рассказывает глава 48, тратят на этот вопрос немало сил.

Осталось найти самые частые слова. Это уже знакомая сортировка пар.

Наверху — клей языка: «и», «в», «не», «что», «он». Первое слово со смыслом — «сказал», на восемнадцатом месте: роман во многом состоит из разговоров. Пьер на 32-м месте, «князь» — на 33-м, Наташа — на 48-м, а «война» — только в десятой сотне. Точное место у неё условное: ровно по 52 раза в романе встречаются 23 слова — среди них «дядюшка», «поцеловал» и «утром», — и порядок среди равных определяет сортировка. Последний цикл ищет место слова перебором списка. Для пяти слов это терпимо; для тысячи разумнее завести ещё один словарь: слово → место.

Закон Ципфа

Прежде чем отвечать, присмотритесь к числам в ответе № 1. «И» встречается 21 075 раз, «в» — 10 880: почти вдвое реже. «Не» — 8516, в два с половиной раза реже. Похоже, что слово на месте $r$ встречается примерно в $r$ раз реже первого. Такую закономерность заметил французский стенограф Жан-Батист Эсту ещё в начале XX века, а прославил американский лингвист Джордж Кингсли Ципф, который в 1930–40-х годах написал о ней несколько книг. Её называют законом Ципфа: частота слова примерно обратно пропорциональна его месту,

Проверить закон глазами проще всего на графике с логарифмическими шкалами: на них степенная зависимость $C/r$ превращается в прямую с наклоном $-1$. Matplotlib рисует такой график на сервере.

Пятьдесят тысяч слов легли почти на прямую — от сотого места до десятитысячного, через два порядка. Самые первые места лежат ниже прямой — «и» встречается вдвое реже, чем обещает пунктир, — а хвост превращается в ступеньки: частоты там маленькие целые числа, 3, 2, 1. Пунктир — это $45\,000 / r$; запись [45000 / r for r in ranks] строит список из выражения для каждого $r$ — такие списковые выражения мы разберём в главе 10.

Ответ редакции даёт последняя строка: 27 890 слов из 51 787, больше половины словаря романа, встречаются всего по одному разу. Это тоже следствие закона Ципфа: в длинном хвосте каждое слово редкое, но вместе их большинство. Похожий закон находят и вне языка — например, в населении городов: второй по величине город страны нередко примерно вдвое меньше первого, хотя для городов закон выполняется далеко не везде. Почему так получается, единого объяснения нет, а следствие очень практичное: в любом тексте будет много слов, которых вы раньше не видели. Поисковикам, программам сжатия и языковым моделям приходится с этим считаться.

Группировка: анаграммы для кроссворда

Анаграммы — слова из одних и тех же букв: «город» и «дорог», «ясно» и «нося». Проверять каждую пару из пятидесяти тысяч слов — больше миллиарда пар. Есть приём лучше: дать каждому слову ключ, одинаковый у всех анаграмм. Если расставить буквы слова по алфавиту, у анаграмм получится одно и то же: sorted("город") и sorted("дорог") дают список ['г', 'д', 'о', 'о', 'р'], а "".join(...) склеивает его в строку "гдоор". Остаётся завести словарь: ключом будет такая строка, значением — список всех слов с этим ключом.

Это группировка, второй главный приём со словарём после подсчёта. Схема та же: для каждого элемента вычисляем ключ, а потом либо прибавляем к счётчику, либо дописываем в список. Если ключа ещё нет, сначала заводим пустой список. Конструкция set(...) убирает повторы слов; о множествах — чуть ниже. А метод строк isalpha отвечает, состоит ли строка из одних букв.

«Если — силе — сели — лисе», «свалился — славился — сливался», «секта — скате — тесак», а дальше в списке из 98 групп — «желал — лежал — жалел» и «кончено — конечно — окончен»: редакции будет из чего выбрать. Ключ можно придумать и другой — и получится совсем другая группировка. Попробуйте в сортировочной ниже.

Что идёт за словом

Группировать можно не только по свойству самого слова. Сгруппируем каждое слово романа по слову, которое стоит перед ним: получится словарь «слово → список всех слов, которые в романе шли за ним». У «князь» в этом списке 778 раз «андрей», 149 раз «василий» и ещё сотни других. Из такого словаря можно сочинять фразы. Начнём со слова «князь», выберем случайного «преемника» из его списка, потом преемника преемника — и так пятнадцать раз.

Запустите несколько раз. Получается не Толстой, но что-то толстовское: каждые два соседних слова встречались в романе рядом, а смысла целого нет. Функция random.choice выбирает случайный элемент списка, и раз «андрей» лежит в списке 778 раз, он выпадает чаще остальных. Это простейшая языковая модель: она знает только, какое слово за каким шло. Большие языковые модели учитывают тысячи предыдущих слов, а вместо словаря у них обученная сеть — об этом глава 63 и курс «Росток» на этом сайте. Но с идеи «посчитать, что за чем идёт» начинали и они.

Множества

Иногда считать ничего не нужно, достаточно знать, какие слова есть. Для этого в Python есть множество — словарь без значений, одни ключи. Его элементы не повторяются, порядка у них нет, а проверка in мгновенная, как поиск ключа. Множество строится функцией set из любого списка или записывается в фигурных скобках без двоеточий: {"война", "мир"}. Пустое множество — только set(), потому что {} — пустой словарь.

Множества умеют всё то же, что в школьной математике: пересечение a & b (что есть в обоих), объединение a | b (что есть хоть в одном), разность a - b (что есть в первом, но не во втором) и симметрическая разность a ^ b (что есть ровно в одном). Попробуйте их на двух коротких текстах.

Теперь можно ответить редакции: сравним словарь первого тома и эпилога и найдём слова, которых до эпилога во всём романе не было.

Первый том — салоны, войска и Кутузов, которого в эпилоге нет ни разу. Эпилог — семья и философия: «культуры», «астрономии», «правителей», «народами» появляются впервые на последних страницах, а «власть», упомянутая в первом томе пять раз, в эпилоге звучит 64 раза. Вторая часть эпилога — трактат Толстого о том, что движет историей, и частотный словарь это видит, не прочитав ни строчки. Даже первое место в списке новых слов — «воль», родительный падеж множественного числа от «воля»: в трактате Толстой рассуждает о том, как воли миллионов людей складываются в события.

И ещё одна причина любить множества — скорость. Проверка x in список перебирает список, x in множество сразу заглядывает в нужный ящик.

Слова «компьютер» в романе нет, и чтобы в этом убедиться, список проходит все 448 тысяч слов. Множеству хватает одного взгляда — разница в десятки тысяч раз. Как такую разницу считают и записывают формулами — тема главы 13.

Почему ключ не может быть списком

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

Кортеж в роли ключа принят, а на списке Python падает с ошибкой TypeError: unhashable type: 'list'. Причина — изменяемость списков: в главе 6 два имени смотрели на один список, и правка через одно имя была видна через другое. Словарь раскладывает записи по ящикам в зависимости от ключа в момент записи. Если бы ключом мог быть список, его можно было бы потом изменить через другое имя — append, sort, — и запись осталась бы в ящике, подписанном старым ключом: по новому её не найти, по старому тоже. Поэтому ключом может быть только неизменяемое значение: число, строка, кортеж из неизменяемых. По той же причине элементы множества не бывают списками. Что значит слово unhashable и как устроены ящики, расскажет глава 16.

Чаще всего в романе стоят рядом «что он» — 838 раз, а на втором месте «князь андрей», 778. Дальше в восьмёрке снова клей языка — «и не», «то что», «как будто», а «княжна марья», 364 раза, стоит на одиннадцатом месте. Строка for n, (a, b) in top[:8] раскладывает каждый элемент — кортеж из числа и кортежа слов — сразу на три имени; скобки показывают, как вложены части.

Готовые инструменты

Подсчёт и группировка нужны так часто, что в стандартной библиотеке Python для них есть готовые словари с особыми способностями. Они живут в модуле collections.

Counter считает всё, что ему дали, а метод most_common(k) отдаёт k самых частых пар — то же, что мы делали вручную сортировкой. На отсутствующий ключ Counter отвечает нулём там, где обычный словарь выдал бы ошибку. defaultdict — словарь, который сам заводит запись для нового ключа: defaultdict(list) кладёт туда пустой список, defaultdict(int) — ноль. У list в скобках нет собственных скобок: мы передаём не список, а саму функцию, которая умеет его делать, и словарь вызывает её, когда нужно. Функция как аргумент другой функции — тема главы 10.

Ручные версии мы писали не зря: так вы знаете, что происходит внутри, и сумеете написать подсчёт там, где Counter не подходит, — например, когда к счётчику нужно добавлять длину слова вместо единицы.

Словари в словарях

Значением в словаре может быть что угодно: число, строка, список — и другой словарь. Итоги нашей работы удобно собрать в одну вложенную структуру.

report["герои"]["Наташа"] читается слева направо: в отчёте взять героев, у героев — Наташу. Так добираются до любой глубины. Функция json.dumps превращает словарь в текст в формате JSON: ensure_ascii=False оставляет русские буквы русскими, indent=2 расставляет отступы. Вывод почти неотличим от записи словаря в Python. JSON родился в JavaScript, но давно стал общим языком для обмена данными, от сайтов до приложений в телефоне. Когда приложение погоды показывает температуру, оно почти наверняка получило с сервера JSON.

Обратная функция, json.loads, превращает текст JSON в словари и списки Python. Так приходят данные с сайта Геологической службы США, откуда взят каталог землетрясений главы 6. Вот сильнейший толчок той ночи — в том виде, в каком его отдаёт сервер, только сокращённо.

Время в JSON записано числом: миллисекунды с 1 января 1970 года — так компьютеры часто хранят моменты времени. Координаты идут в непривычном порядке: сначала долгота, потом широта. Так условились в формате GeoJSON, и об этом нужно помнить: перепутаете — и программа попробует поставить точку на широте 160°, которой не бывает. Читать незнакомый JSON — обычная работа программиста: смотришь на вложенность и спускаешься по ключам.

Телеграммы на дом

Четыре задачи. Тесты вызывают ваши функции и сравнивают то, что они вернули, с ожидаемым.

Куда дальше

Последняя просьба выглядит простой. Папка — это словарь: имя файла → размер в килобайтах, имя вложенной папки → словарь её содержимого.

На первом уровне цикл, на втором — цикл в цикле, и на третьем мы сдались: «старое» лежит внутри «тома 2», а «ещё старее» — внутри «старого». Чтобы спуститься на любую глубину, пришлось бы заранее знать, сколько циклов вкладывать, а папки на диске, как и JSON с сервера, бывают вложены как угодно глубоко. Но присмотритесь к задаче: размер папки — это сумма размеров файлов плюс размеры вложенных папок. Внутри задачи сидит та же задача, только поменьше. Как решать такие задачи и почему из этой идеи получаются и Ханойская башня, и снежинка, и дерево из главы 0, — глава 9.