Wolfram Research corporate blog
Entertaining tasks
Programming
Algorithms
Mathematics
December 2014 21

Поиск самых длинных цепочек слов в русском языке с помощью языка Wolfram Language (Mathematica)


Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~5 МБ).

Введение


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

Предположим, что у нас есть несколько последовательных метаграмм, скажем:

мнение-мление-тление-трение-прение-поение-роение-рдение-бдение-биение

они образуют цепь метаграмм, или цепочку слов.

Отсюда проистекает игра под названием цепь слов (word ladder), которую придумал в далеком 1879 году Льюис Кэрролл.

Ясно, что далеко не для каждого начального слова может быть составлена такого рода цепь, а некоторые слова, по-видимому, должны порождать довольно длинные цепи.

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

Импорт списка слов русского языка


Для построения и анализа цепочек слов нам потребуется список слов, которые мы можем встретить в русском языке. В данном посте мы не будем делать ограничение на часть речи, которая может быть использована, но при этом будем рассматривать только форму слова, соответствующую именительному падежу в парадигме слова. Мы используем, как и в одном из предыдущих постов (Поиск наилучшей последовательности просмотра списка 250 лучших фильмов с помощью языка Wolfram Language (Mathematica)), морфологический словарь русского языка, созданный академиком Андреем Анатольевичем Зализняком:

In[1]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_2.gif

In[3]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_3.png

Обработаем данные словаря, составив на его основе список слов русского языка russianWords:

In[4]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_4.png

Функция, определяющая звено цепочки слов


Создадим функцию chainLinkQ, которая будут определять, могут ли два слова быть звеном цепочки слов, другими словами, эта функция отвечает на вопрос — являются ли два слова метаграммой.

При этом рассмотрим два варианта:

  • слова отличаются одной буквой (в данном случае достаточно воспользоваться для проверки функцией EditDistance, которая вычисляет расстояние Левенштейна, результат вычисления которой должен равняться 1):

In[5]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_5.png

  • слова отличаются n соседними буквами:

In[6]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_6.png

Функция поиска всех метаграмм слов фиксированной длины


Теперь найдем все звенья цепочек слов (метаграммы).

Для начала, разобьем все слова русского языка в классы эквивалентности, т. е., по сути мы построим фактор-множество слов русского языка по их длине, другими словами, разобьем список всех слов на множества слов из 1-й, 2-х, 3-х, 4-х и т. д. букв.

In[7]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_7.png

Найдем минимальную и максимальную длину слова в русском языке:

In[8]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_8.png

Out[8]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_9.png

Посмотрим на распределение слов русского языка по длине:

In[9]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_10.png

Out[9]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_11.png

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

In[10]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_12.png

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

In[11]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_13.png

Пример результата вычислений:

In[12]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_14.png

Out[12]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_15.png

Графы цепочек слов


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

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

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_16.png

In[13]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_17.png

In[14]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_18.png

Граф цепочек слов русского языка, содержащих 1 букву
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_19.png

Граф цепочек слов русского языка, содержащих 2 буквы
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_20.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_21.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_22.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_23.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_24.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_25.png

Граф цепочек слов русского языка, содержащих 8 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_26.png

Граф цепочек слов русского языка, содержащих 9 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_27.png

Граф цепочек слов русского языка, содержащих 10 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_28.png

Граф цепочек слов русского языка, содержащих 11 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_29.png

Граф цепочек слов русского языка, содержащих 12 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_30.png

Граф цепочек слов русского языка, содержащих 13 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_31.png

Граф цепочек слов русского языка, содержащих 14 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_32.png

Граф цепочек слов русского языка, содержащих 15 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_33.png

Граф цепочек слов русского языка, содержащих 16 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_34.png

Граф цепочек слов русского языка, содержащих 17 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_35.png

Граф цепочек слов русского языка, содержащих 18 букв
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_36.png

Граф цепочек слов русского языка, содержащих 21 букву
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_37.png

Из графов выше видно, как сильно меняется их структура в зависимости от длины слов, из которых он строится, при этом можно наблюдать, что большинство графов имеют более одной компоненты связности.

Из графика, представленного ниже можно видеть зависимость количества компонент связности различной длины среди всех рассмотренных выше графов, из которого следует, что зависимость должна иметь вид Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_38.png, где x — размер компоненты связности, y — число компонент связности.

In[15]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_39.gif

Out[16]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_40.png

Действительно:

In[17]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_41.gif

Out[17]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_42.png

In[19]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_43.png

Out[19]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_44.png

Предположение Дональда Кнута применительно к цепочкам слов в русском языке


Дональд Кнут одним из первых применил компьютер для исследования цепочек английского языка. Он изучал цепочки слов, состоящих из 5 букв, так как полагал, что слова из меньшего числа букв, скажем, 3-х слишком просты для изучения (хотя Льюис Кэрролл составил цепочку из 6 звеньев от слова APE до слова MAN), а слова из большего числа букв не смогут привести к длинным цепочкам, в том числе и потому, что соответствующий граф имеет много компонент связности.

Проверим предположение Кнута для цепочек слов русского языка.

График, представленный ниже, показывает то, как с увеличением числа букв в словах, из которых строятся цепочки меняется положение точки с координатами:

{количество компонент связности графа, количество рёбер графа}.

Верхний левый угол соответствует “идеальному графу” у которого одна компонента связности, при этом у него максимальное число рёбер. Граф, соответствующий наиболее близкой точке рассматриваемой траектории к данной точке, очевидно, может рассматриваться как “наилучший”. Соответствующая точка, найденная автоматически, помечена двумя красными окружностями и соответствует графу цепочек пятибуквенных слов.

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

In[20]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_45.gif

Out[25]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_46.png

Поиск самой длинной цепочки слов в русском языке


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

In[26]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_47.png

Out[26]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_48.png

Итак, мы получили две самые длинные цепочки слов в русском языке, при этом, как и ожидалось, они содержатся в “наилучшем” графе цепочек пятибуквенных слов.

Поиск самых длинных цепочек n-буквенных слов русского языка


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

Давайте теперь посмотрим на самые длинные возможные цепочки n-буквенных слов:

In[27]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_49.png

Цепочки слов русского языка, содержащих 2 буквы, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_50.png

Цепочки слов русского языка, содержащих 3 буквы, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_51.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_52.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_53.png

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_54.png

Цепочки слов русского языка, содержащих 7 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_55.png

Цепочки слов русского языка, содержащих 8 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_56.png

Цепочки слов русского языка, содержащих 9 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_57.png

Цепочки слов русского языка, содержащих 10 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_58.png

Цепочки слов русского языка, содержащих 11 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_59.png

Цепочки слов русского языка, содержащих 12 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_60.png

Цепочки слов русского языка, содержащих 13 букв, с количеством слов не менее 5
Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_61.png

Заключение


Надеюсь, что мой пост смог заинтересовать вас, а некоторые идеи и программы, представленные в нем окажутся вам полезны. Безусловно, можно придумать еще массу интересных исследований русского языка. Скажем, в начале поста была создана функция chainLinkQ, функционал которой позволяет произвести аналогичное исследование для метаграмм, отличающихся двумя буквами — что соответствует, по сути, небольшой модификации правил игры в цепочки слов. Из двух графов, представленных ниже, видно, что граф четырёхбуквенных метаграмм, отличающихся двумя буквами является связным, по сравнению с графом метаграмм, отличающихся только лишь одной буквой. Это говорит о том, что результаты исследования таких графов и цепочек будут совершенно иными.

In[28]:=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_62.png

Out[28]=

Poisk-samyh-dlinnyh-cepochek-slov-v-russkom-jazyke-s-pomoshhju-jazyka-Wolfram-Language-Mathematica_63.png

Ресурсы для изучения Wolfram Language (Mathematica) на русском языке: http://habrahabr.ru/post/244451
+74
38k 169
Support the author
Comments 24
Top of the day