Из мухи — слона

Александр Пиперски
«Квантик» №2, 2019 и №3, 2019

В повести известного писателя Юрия Трифонова (1925–1981) «Долгое прощание» рассказывается, как герой проводит время в поезде: «Третьи сутки Ребров, лёжа на верхней полке, мучил себя — делал из мухи слона. На листке бумаги писал: муха — мура — кура — кора — корт — торт — торс...».

Правила игры очень просты: надо построить цепочку слов от начального (МУХА) до конечного (СЛОН), на каждом шаге меняя только одну букву. При этом могут использоваться только русские 4-буквенные нарицательные существительные в начальной форме: например, слова БАЗА, НОЧЬ, САНИ допускаются, а слова ЛИТЬ, ХОТЯ, РУКУ, НОЧИ, САНЯ, ОСЛО, АБВГ, ФЦНМ — нет (первые два — не существительные, следующие два — не в начальной форме, следующие два — собственные, а не нарицательные, а два последних вовсе не существуют в языке).

Эта игра под названием «Дублеты» приобрела известность благодаря Льюису Кэрроллу — не только автору книг про Алису, но ещё и замечательному математику. В марте 1879 года он начал раз в неделю публиковать в журнале «Ярмарка тщеславия» по три задания в форме броских фраз: «Turn POOR into RICH» — «Преврати бедного в богатого», «Evolve MAN from APE» — «Выведи человека из обезьяны», «Make TEA HOT» — «Сделай чай горячим». В том же году он выпустил брошюру «Дублеты», подробно описал в ней правила и предложил читателям попрактиковаться на нескольких десятках примеров.

Вот и вам пять пар для тренировки — попробуйте построить для них цепочки. Сразу предупреждаю, что в одном случае, скорее всего, не получится: БОРЩ → ПОСТ; ЛИПА → ЖАРА; КИНО → ВАТА; КЛЕН → ЕЛКА; ПАУК → ЛОСЬ.

Вы наверняка нашли четыре из пяти цепочек, а не смогли построить только одну. Но как доказать, что это действительно невозможно? Может быть, мы просто не придумали способ, а вообще-то он есть. Разобраться нам поможет теория графов.

Первым делом договоримся о том, что именно мы считаем словами, а то может получиться, что я дам вам задание МУХА → СЛОН и вы скажете: «4 хода! МУХА → МУХН → МУОН → МЛОН → СЛОН». Тогда мне придётся со словарями в руках доказывать, что это жульничество, потому что слов МУХН, МУОН и МЛОН не существует. Чтобы избежать этого, мы обратимся к словарю с самого начала и постановим, что будем пользоваться только теми 4-буквенными существительными, которые есть в заранее выбранном источнике. Для этой статьи я взял «Грамматический словарь русского языка» Андрея Зализняка — этот словарь чаще всего применяют в компьютерной лингвистике. Кстати, мысль о том, что очень важно заранее договориться о словаре, пришла в голову ещё Льюису Кэрроллу: 28 из 39 страниц его книги как раз и занимает перечень английских слов, которые можно использовать в игре. Кроме того, условимся, что мы не используем в игре букву Ё и заменяем её на Е.

Всего в «Грамматическом словаре» 1712 четырёхбуквенных существительных. Возьмём, к примеру, существительное ЛОЖЬ и изобразим его точкой. Найдём в словаре все слова, которые отличаются от него на одну букву; их ровно четыре: ЛОЖА, ЛОЖЕ, ЛОСЬ и РОЖЬ. Изобразим их точками, соединёнными со словом ЛОЖЬ; наличие связи означает, что между словами можно перейти за один ход. (Кстати, какую ещё пару слов надо не забыть соединить?) Затем добавим слова, которые за один ход получаются из этих четырёх слов: КОЖА, ЛОЗА, ЛУЖА, ЛЫЖА, РОЖА, РОЛЬ, ЛОСК, — и нарисуем нужные связи.

В итоге у нас получился граф, в котором некоторые из 12 точек (вершин) соединены отрезками (рёбрами). Если нам нужно превратить одно слово в другое, на математическом языке это формулируется так: найти путь между соответствующими вершинами, желательно кратчайший. Так, если нам надо пройти от ЛЫЖА до РОЛЬ, это займёт четыре шага, и пути могут быть разными: ЛЫЖА → ЛОЖА → РОЖА → РОЖЬ → РОЛЬ или ЛЫЖА → ЛОЖА → ЛОЖЬ → РОЖЬ → РОЛЬ. (Докажите, что более короткого пути между словами ЛЫЖА и РОЛЬ нет.)

А теперь изобразим так не 12 слов, а все 1712, и посмотрим, как устроен этот граф. Вручную это сделать едва ли возможно, так что понадобится компьютер. Видно, что на графе выделяется большой кусок, где от любого слова можно дойти до любого другого; в теории графов такой подграф называют компонентой связности. Есть ещё несколько таких кусков поменьше и много точек, которые не связаны вообще ни с чем (такие отдельно стоящие точки тоже можно считать компонентами связности). Ясно, что от одного слова можно дойти до другого тогда и только тогда, когда они входят в одну и ту же компоненту связности.

Самая большая компонента связности включает в себя 1361 слово (то есть 79,5% всех слов). Кроме неё есть компонента размером 11 слов, ещё одна — размером 6 слов, 3 — размером 5 слов, 4 — размером 4 слова, 14 — размером 3 слова, 25 — размером 2 слова и ещё 211 отдельно стоящих слов (АЛОЭ, ВДОХ, ДЖАЗ, НЕБО, ОПЫТ, СОЮЗ, ТАЙМ и другие). Слово КЛЕН входит в большую компоненту связности, а слово ЕЛКА — в маленькую, 5-словную; этим и объясняется тот факт, что из слова КЛЕН не получится ЕЛКА.

Всего в нашем графе 3172 ребра, а значит, у слова в среднем $\frac{3172}{1712}·2=\mathrm{3,7}$ соседей. Возвращаясь к самой большой компоненте связности, обратим внимание на то, что из неё торчат «хвосты». Дело в том, что даже в ней у некоторых слов совсем мало соседей. Скажем, от слова ТИГР можно перейти только к слову ТИТР, от него — только к слову ЛИТР, дальше — только к слову ЛИВР (это старинная французская монета, вспомните «Трёх мушкетёров»), дальше — только к слову ЛАВР, а уже от него — к словам МАВР и ЛАВА, после чего возможностей становится резко больше: от слова ЛАВА отходит ещё 5 слов, и мы попадаем в основую гущу вершин.

Таким образом, слово ТИГР — это конец хвоста, и если понадобится пройти из одного такого хвоста в другой, путь может получиться очень длинным, даже если это кратчайший путь между этими двумя вершинами. Самые длинные пути имеют длину 23 — например, от слова ДЖИП до слова ТУЕС (берестяная коробочка) всего 22 шага: ДЖИП → ДЖИН → УЖИН → УДИН → ОДИН → ОВИН → ОВЕН → ОВЕС → СВЕС → СВЕТ → СВАТ → СВАН → СТАН → СТЕН → СТЕК → САЕК → РАЕК → РОЕК → БОЕК → БУЕК → БУЕР → ТУЕР → ТУЕС. Глядя на эту цепочку, вам наверняка хочется пожаловаться: «Я же не знаю половины этих слов!» (признаюсь честно: я тоже не знаю). Но раз мы договорились использовать «Грамматический словарь», то и будем на него опираться, а к борьбе с незнакомыми словами вернёмся чуть позже.

Для 5-буквенных слов английского языка такой граф впервые построил знаменитый американский учёный и автор классических пособий по программированию Дональд Кнут. А почему, кстати, у него 5 букв, а у нас — 4? Есть ли какое-то объяснение тому, что в игру «Из мухи — слона» по-русски обычно играют 4-буквенными словами? Интуитивно кажется, что так интереснее всего. Но попробуем оценить этот интерес и количественно.

Представьте себе, что мы играем однобуквенными словами. В «Грамматическом словаре» ровно 9 однобуквенных существительных: А, Е, И, О, У, Ы, Э, Ю, Я — названия гласных букв (слово Ё мы объединили со словом Е). Из любого слова к любому можно перейти за один ход, и это неинтересно. Если, напротив, играть в 10-буквенные слова, то от большинства слов — как, скажем, от слова БЕЗДЕЛЬНИК, — вообще нельзя никуда перейти. Получается, что игра интересна, когда выполнены два требования: пути между словами длинные и между двумя произвольно взятыми словами путь обычно существует (но не всегда — если успех гарантирован, играть тоже скучно).

Чтобы оценить среднюю длину пути, надо найти самые короткие пути между всеми парами точек, для которых путь есть, и вычислить среднее. Это трудоёмкий процесс, но есть алгоритмы, которые производят такое вычисление достаточно быстро. А сделав его, узнать вероятность успеха совсем просто: у нас есть 1712 4-буквенных слов, а значит, 1712 · 1711 упорядоченных пар (от любого из 1712 слов мы пытаемся пройти к любому из 1711 оставшихся); посчитаем, сколько из них соединены путём, и разделим на 1712 · 1711. Таких пар 1 851 342, а значит, вероятность успеха равна 1 851 342 / (1712 · 1711) ≈ 0,632.

Можно сделать то же самое по-другому, опираясь на знания про размеры компонент связности. Возьмём произвольное начало цепочки; вероятность того, что оно попадёт в большую компоненту связности, составляет 1361/1712; возьмём теперь другое произвольное слово в качестве конца цепочки: в большой компоненте осталось 1360 слов, а всего в словаре — 1711, то есть вероятность того, что оно окажется связанным с началом, составляет 1360/1711. Тогда начало и конец цепочки попадут в большую компоненту с вероятностью 1361 · 1360 / (1712 · 1711). Во вторую по величине компоненту связности они попадут с вероятностью 11 · 10 / (1712 · 1711). Суммируя эти вероятности для всех компонент, получим то же число 0,632. Результаты подсчётов для слов от 1 до 12 букв — в таблице:

Видно, что 4-буквенные слова действительно обеспечивают хорошую, но всё же не стопроцентную вероятность успеха и при этом создают достаточно длинные цепочки. А с 10-буквенными словами всё скучно: даже в тех редких случаях, когда путь есть, он обычно состоит из одного шага (ВОЗМЕЩЕНИЕ → ВОЗМУЩЕНИЕ), редко — из двух или больше. Единственный путь из пяти шагов соединяет слова ПАССИРОВКА и ФАРШИРОВКА: ПАССИРОВКА → МАССИРОВКА → МАСКИРОВКА → МАРКИРОВКА → МАРШИРОВКА → ФАРШИРОВКА.

Эта цепочка напоминает ещё об одной проблеме, с которой надо разобраться: редкие слова. Попробуйте решить такую задачу: ДАЛЬ → ПАРИ. В этих словах совпадает буква А на втором месте, и есть надежда справиться за три шага. Действительно, такой путь есть: ДАЛЬ → ПАЛЬ → ПАЛИ → ПАРИ. Но едва ли он вас порадует: большинство людей не знают ни слова ПАЛЬ (‘выжженный участок в лесу или в степи’), ни слова ПАЛИ (один из древних индийских языков). Но существует и путь из более нормальных слов: ДАЛЬ → ДАНЬ → ДЕНЬ → ТЕНЬ → ТЕНТ →ТЕСТ → ТОСТ → ПОСТ → ПОРТ → ПОРА → ПАРА → ПАРИ. Он длиннее, но в каком-то смысле лучше пути из трёх шагов. Попробуем формализовать эту идею.

Для этого нам понадобится ещё один словарь — частотный (я пользуюсь «Новым частотным словарём русской лексики» О. Ляшевской и С. Шарова). В частотном словаре слова упорядочены по тому, насколько они употребительны в языке: 1-е место занимает союз И, на 2-м месте — предлог В, на 3-м — частица НЕ и т. д. А вот 10 самых частых 4-буквенных существительных с указанием их мест: 65) ДЕЛО, 71) ДЕНЬ, 74) РУКА, 104) ЛИЦО, 106) ДРУГ, 110) ГЛАЗ, 140) СИЛА, 191) ВОДА, 192) ОТЕЦ, 205) НОГА.

Слова типа ДЖИП и ТИТР стоят гораздо ниже: 6616) ДЖИП, 8086) ТИТР. Всего в этом словаре 52 138 слов, из них с «Грамматическим словарём» пересеклось 1140 4-буквенных существительных. А, например, слово ЛИВР (старая французская монета) даже не попало в частотный словарь. Условно присвоим ему и всем другим таким словам номер 100000.

А теперь сделаем наш граф ориентированным и взвешенным. Ориентированный — это значит, что из вершины в вершину будут вести не отрезки, а стрелки, точнее пары стрелок: одна в одну сторону, другая в другую. А взвешенный значит, что каждой стрелке будет приписан вес: по одним стрелкам ходить будет дороже, а по другим дешевле. Веса припишем так: если стрелка ведёт в слово, которое занимает k-е место в частотном словаре, припишем ей вес $\sqrt{k}$ (мы могли бы выбрать и какую-нибудь другую функцию, но квадратный корень даёт результаты, которые кажутся подходящими для наших нужд). Например, все стрелки, ведущие в ДЕЛО, получают вес $\sqrt{\mathrm{65}}\approx \mathrm{8,1}$, все стрелки, ведущие в ТИТР, — $\sqrt{\mathrm{8086}}\approx \mathrm{89,9}$, а все стрелки, ведущие в ЛИВР, — $\sqrt{\mathrm{100000}}\approx \mathrm{316,2}$. Длиной пути теперь будет не количество рёбер, а сумма чисел на стрелках, по которым мы двигались. Проходить редкие слова теперь невыгодно: ведущие в них стрелки весят слишком много.

Попробуем для примера найти оптимальный путь от слова ЛОЖЬ к слову РОЖА. Возьмём подграф, содержащий слова ЛОЖЬ, РОЖЬ, ЛОЖА и РОЖА, и разметим в нём веса.

Окажется, что путь ЛОЖЬ → РОЖЬ → РОЖА стоит 121,6 + 78,6 = 200,2, а путь ЛОЖЬ → ЛОЖА → РОЖА стоит 82,6 + 78,6 = 161,2. Иначе говоря, выгоднее идти через более частое слово ЛОЖА, чем через более редкое РОЖЬ.

Но вернёмся к путям от ДАЛЬ к ПАРИ. Оказывается, более длинный по числу шагов путь выгоднее с точки зрения весов: ДАЛЬ $\stackrel{\text{96,5}}{\to }$ ДАНЬ $\stackrel{\text{8,4}}{\to }$ ДЕНЬ $\stackrel{\text{36,4}}{\to }$ ТЕНЬ $\stackrel{\text{140,9}}{\to }$ ТЕНТ $\stackrel{\text{65,8}}{\to }$ ТЕСТ $\stackrel{\text{81,6}}{\to }$ ТОСТ $\stackrel{\text{38,8}}{\to }$ ПОСТ $\stackrel{\text{58,4}}{\to }$ ПОРТ $\stackrel{\text{16,6}}{\to }$ ПОРА $\stackrel{\text{27,9}}{\to }$ ПАРА $\stackrel{\text{126,2}}{\to }$ ПАРИ (сумма 697,5); ДАЛЬ $\stackrel{\text{316,2}}{\to }$ ПАЛЬ $\stackrel{\text{316,2}}{\to }$ ПАЛИ $\stackrel{\text{126,2}}{\to }$ ПАРИ (сумма 758,6).

Так мы формализовали ощущение, почему длинная цепочка с известными словами лучше, чем короткая с неизвестными. Кстати, для задачи МУХА → СЛОН цепочки без весов и с весами тоже разные. Без весов (10 шагов): МУХА → МУРА → МАРА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТЕН → СТОН → СЛОН; с весами (13 шагов): МУХА → МУКА → ЛУКА → ЛУПА → ЛАПА → ПАПА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТОК → СТОН → СЛОН.

Увы, и в цепочке с весами не удалось обойтись без малоизвестного слова САЕК (точнее, САЁК), которое значит ‘молодой олень’. Но другие решения этой задачи включают в себя ещё и не такое. Самую короткую из известных цепочек придумал Владимир Гончаров; в ней 7 шагов: МУХА → МУЛА → КУЛА → КИЛА →КИЛН → КИОН → СИОН → СЛОН. По нашим правилам она не подходит, потому что в «Грамматическом словаре» из 6 промежуточных слов есть только КИЛА (это разговорное название для грыжи), а если бы они и были, то с весами эта цепочка стоила бы очень дорого, ведь все промежуточные слова в ней редкие — да и разве интересна цепочка, в которой 6 из 6 промежуточных слов нам неизвестны?

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

Художник Мария Усеинова