Поиск самых длинных цепочек слов в русском языке с помощью языка 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
    Wolfram Research 45,76
    Wolfram Language, Mathematica, Wolfram Alpha и др.
    Поделиться публикацией
    Комментарии 24
    • +2
      Сразу вспомнился испорченный телефон, хотя этот вариант более упорядочен.

      А Вы не хотите проделать аналогичный вариант с искусственным языком, каким-нибудь Ифкуилем?
      • +3
        Если сообществу понравится такая идея или же развитие идеи для русского языка, то, думаю, вполне возможно.
      • +25
        Хм, все длиннейшие 6-буквенные цепочки содержат «печаль» и заканчиваются на «грусть»…
      • +4
        По какому алгоритму искались самые длинные цепочки? Очевидно, что диаметр компонента связности не обязательно равен длине максимальной цепочки, скорее надо искать длиннейший путь без самопересечений. Возможно, поэтому приведённая выше цепочка из 19 слов «прищеп-прицеп-...-приход-проход» не является максимальной в своей компоненте, её можно удлинить, добавив в конце «провод».
        • +1
          В свою очередь поиск длиннейшего пути без самопересечений является NP-сложной задачей, поскольку это обобщение NP-полной задачи о поиске Гамильтонова пути. Правда для графов с 1000 вершинами это наверняка не требует очень больших вычислений.
          • 0
            Можно конечно, если чуть поменять условия (добавить возможность повторения слов), найти «путь китайского почтальона», обходящий все вершины компонента связности, скажем, в рассматриваемом вами случае эта последовательность будет:

            просос — прасол — просол — продол — продел — пробел — пробег — пробел — продел — придел — прицел — прицеп — прищеп — прицеп — прицел — придел — предел — продел — продол — прокол — прикол — прокол — прокоп — прокос — прокус — прикус — примус — примас — припас — припай — припой — пропой — пробой — пробор — прибор — призор — призёр — призор — прибор — прибой — пробой — пропой — припой — привой — привоз — провоз — провод — проход — приход — привод — провод — провоз — привоз — привод — привой — кривой — привой — прибой — припой — припай — припас — примас — примат — примаж — примат — примак — примас — примак — примаж — примас — примус — прикус — прикуп — прикус — прокус — крокус — прокус — прокос — прекос — прокос — профос — прокос — прокол — просол — просос — профос — пронос — прокос — просос — пронос — принос — присос

            В данном случае ищутся периферийные вершины графа и пути между ними. Согласен, если усложнить алгоритм, можно в некоторых случаях немного удлиннить некоторые из полученных цепочек. Это может стать развитием данного поста.
            • 0
              Ну, повторения — это не интересно, так можно вообще бесконечные цепочки построить ;)
              украл-...-выпил-...-в тюрьму засел-...-украл-...-выпил-…
          • +14
            Оказывается я русского языка почти и не знаю, столько совершенно незнакомых слов:)
            • +4
              Да, это проблема. Было бы полезно отфильтровать по частотному словарю. Например, оставить только те слова, которые встречаются в национальном корпусе не реже одного раза на миллион слов. Или на сто тысяч. Цепочки бы были не такие длинные, но более интересные.
            • 0
              Я их все-таки нашла, слова из 25 букв: частнопредпринимательский, электронно-вычислительный. Викисловарь предлагает больше, например, программист-злоумышленник. Словарь по ссылке не загрузился (all_forms.txt), брала другой.
              • 0
                Интересная была бы новость. «Программист-злоумышленник вчера...»
                • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                Можно ещё добавить в цепочку «капот» после «капор» — будет 41.
                • +1
                  Можно после фидер, поставить редкое слово сидер и возможно удастся пойти ещё дальше.

                  • +8
                    Косячок в алгоритме получился. Не проверяются слова, в которых буква может измениться в той же позиции, в которой она поменялась только что, чтобы не зациклиться, наверное.

                    Там ещё полно вариантов таких можно найти. -спора-свора-скора-, -куток-курок-кусок-, -ворона-корона-борона-, -тропка-трёпка-тряпка-…
                  • +11
                    Такая большая работа и потрачена впустую! Где решение первостепенной задачи: превращение мухи в слона? Разочарован.
                    • +9
                      МУХА–МУЛА–КУЛА–КИЛА–КИЛТ–КИОТ–КЛОТ–КЛОН-СЛОН
                    • 0
                      А что за цепочка на 21 букву?
                      • +4
                        светочувствительность — цветочувствительность
                      • 0
                        Как насчёт самого длинного цикла?
                        • +1
                          игрался когда-то с чем-то похожим, можно менять одну букву либо добавлять. сохранилась цепочка:
                          ёж -> уж -> буж -> бук -> бок -> блок -> блик -> бзик -> узик -> узник -> ушник -> пушник -> путник -> путаник -> путание -> питание -> писание -> списание -> спивание -> спаивание -> опаивание -> опаливание -> осаливание -> оскаливание -> оскабливание -> поскабливание -> проскабливание
                          • +2
                            Неисчерпаемые запасы для, простите, русского рэпа.
                            • 0
                              Можете подсказать, что это за слово?
                              image

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

                              Самое читаемое