Генератор текста на основе триграмм (python)

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

    Сухая теория


    И так, наша задача сгенерировать текст. Это значит, нам нужно взять слова и выстроить их в определенном порядке. Как определить этот порядок? Мы можем пойти следующим образом: построить фразы, наиболее вероятные для русского языка. Но что значит вероятность фразы языка? С точки зрения здравого смысла это бред. Тем не менее, эту вероятность можно задать формально как вероятность возникновения последовательности слов в неком корпусе (наборе текстов). К примеру, вероятность фразы «счастье есть удовольствие без раскаяния» можно вычислить как произведение вероятностей каждого из слов этой фразы:

    P = P(счастье) P(есть|счастье) P(удовольствие|счастье есть) P(без|счастье есть удовольствие) P(раскаяния|счастье есть удовольствие без)


    Рассчитать вероятность P(счастье) дело нехитрое: нужно всего лишь посчитать сколько раз это слово встретилось в тексте и поделить это значение на общее число слов. Но рассчитать вероятность P(раскаяния|счастье есть удовольствие без) уже не так просто. К счастью, мы можем упростить эту задачу. Примем, что вероятность слова в тексте зависит только от предыдущего слова. Тогда наша формула для расчета фразы примет следующий вид:

    P = P(счастье) P(есть|счастье) P(удовольствие|есть) P(без|удовольствие) P(раскаяния|без)


    Уже проще. Рассчитать условную вероятность P(есть|счастье) несложно. Для этого считаем количество пар 'счастье есть' и делим на количество в тексте слова 'счастье':

    P(есть|счастье) = C(счастье есть)/С(счастье)


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

    Хочу отметить, что для нашего алгоритма мы используем не биграммы, а триграммы. Отличие в том, что условная вероятность слова определяется не по одному, а по двум предыдущим словам. То есть вместо P(удовольствие|счастье) мы будем вычислять P(удовольствие|счастье есть). Формула вычисления подобна формуле для биграмм:

    P(удовольствие|счастье есть) = C(счастье есть удовольствие)/С(счастье есть)


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

    * выбираем слово, наиболее вероятное для начала предложения;
    * подбираем наиболее вероятное слово-продолжение в зависимости от двух предыдущих слов;
    * повторяем предыдущий шаг до тех пор, пока не встретим символ конца предложения.

    Практика


    Для начала, нам нужно подготовить корпус, на котором мы будем тренировать свою модель. Я, к примеру, взял выборку из Льва Толстого на сайте lib.ru, и сформировал один текстовый файл (скачать можно здесь).

    Из данного текста выделим необходимую нам последовательность слов.

    import re

    r_alphabet = re.compile(u'[а-яА-Я0-9-]+|[.,:;?!]+')

    def gen_lines(corpus):
        data = open(corpus)
        for line in data:
            yield line.decode('utf-8').lower()

    def gen_tokens(lines):
        for line in lines:
            for token in r_alphabet.findall(line):
                yield token

    lines = gen_lines('tolstoy.txt')
    tokens = gen_tokens(lines)


    Получившийся генератор tokens будет выдавать «очищенную» последовательность слов и знаков препинания. Однако, простая последовательность нам не интересна. Нам интересны тройки токенов (под токеном здесь понимается слово или знак препинания, т.е. некие атомарные элементы текста). Для этого добавим еще один генератор, на выходе которого будем иметь три подряд идущих токена.

    import re

    r_alphabet = re.compile(u'[а-яА-Я0-9-]+|[.,:;?!]+')

    def gen_lines(corpus):
        data = open(corpus)
        for line in data:
            yield line.decode('utf-8').lower()

    def gen_tokens(lines):
        for line in lines:
            for token in r_alphabet.findall(line):
                yield token

    def gen_trigrams(tokens):
        t0, t1 = '$''$'
        for t2 in tokens:
            yield t0, t1, t2
            if t2 in '.!?':
                yield t1, t2, '$'
                yield t2, '$','$'
                t0, t1 = '$''$'
            else:
                t0, t1 = t1, t2

    lines = gen_lines('tolstoy.txt')
    tokens = gen_tokens(lines)
    trigrams = gen_trigrams(tokens)


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

    На входе:
    'Счастье есть удовольствие без раскаяния'

    На выходе:
    итерация токены
    0: $ $ счастье
    1: $ счастье есть
    2: счастье есть удовольствие
    3: есть удовольствие без



    Далее, рассчитаем триграммную модель:

    import re
    from collections import defaultdict

    r_alphabet = re.compile(u'[а-яА-Я0-9-]+|[.,:;?!]+')

    ...

    def train(corpus):
        lines = gen_lines(corpus)
        tokens = gen_tokens(lines)
        trigrams = gen_trigrams(tokens)

        bi, tri = defaultdict(lambda0.0), defaultdict(lambda0.0)

        for t0, t1, t2 in trigrams:
            bi[t0, t1] += 1
            tri[t0, t1, t2] += 1

        model = {}
        for (t0, t1, t2), freq in tri.iteritems():
            if (t0, t1) in model:
                model[t0, t1].append((t2, freq/bi[t0, t1]))
            else:
                model[t0, t1] = [(t2, freq/bi[t0, t1])]
        return model

    model = train('tolstoy.txt')


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

    Теперь у нас все готово для генерации текста. Следующая функция возвращает предложение.

    ...

    model = train('tolstoy.txt')

    def generate_sentence(model):
        phrase = ''
        t0, t1 = '$''$'
        while 1:
            t0, t1 = t1, unirand(model[t0, t1])
            if t1 == '$'break
            if t1 in ('.!?,;:'or t0 == '$':
                phrase += t1
            else:
                phrase += ' ' + t1
        return phrase.capitalize()


    Суть метода в том, что мы последовательно выбираем наиболее вероятные слова или знаки препинания до тех пор, пока не встречаем признак начала следующей фразы (символа $). Первое слово выбирается как наиболее вероятное для начала предложения из набора model['$', '$'].

    Здесь необходимо отметить важный момент. Словарь model для каждой пары слов содержит список пар (слово, вероятность). Нам же необходимо выбрать из этого набора только одно слово. Вариант «в лоб» — выбрать слово с максимальной вероятностью. Но тогда все сгенерированные фразы были бы похожи друг на друга. Более подходящий способ способ — выбирать слова с некой хаотичностью, которая бы зависела от вероятности слова (мы же не хотим чтобы наши фразы состояли из редких сочетаний). Это и делает метод unirand, который возвращает случайное слово с вероятностью, равной вероятности данного слова в зависимости от двух предыдущих.

    Итого, полный код нашего генератора выглядит следующим образом:

    #!/usr/bin/env python
    # -*- coding: utf-8 -*-

    import re
    from random import uniform
    from collections import defaultdict

    r_alphabet = re.compile(u'[а-яА-Я0-9-]+|[.,:;?!]+')

    def gen_lines(corpus):
        data = open(corpus)
        for line in data:
            yield line.decode('utf-8').lower()

    def gen_tokens(lines):
        for line in lines:
            for token in r_alphabet.findall(line):
                yield token

    def gen_trigrams(tokens):
        t0, t1 = '$''$'
        for t2 in tokens:
            yield t0, t1, t2
            if t2 in '.!?':
                yield t1, t2, '$'
                yield t2, '$','$'
                t0, t1 = '$''$'
            else:
                t0, t1 = t1, t2

    def train(corpus):
        lines = gen_lines(corpus)
        tokens = gen_tokens(lines)
        trigrams = gen_trigrams(tokens)

        bi, tri = defaultdict(lambda0.0), defaultdict(lambda0.0)

        for t0, t1, t2 in trigrams:
            bi[t0, t1] += 1
            tri[t0, t1, t2] += 1

        model = {}
        for (t0, t1, t2), freq in tri.iteritems():
            if (t0, t1) in model:
                model[t0, t1].append((t2, freq/bi[t0, t1]))
            else:
                model[t0, t1] = [(t2, freq/bi[t0, t1])]
        return model

    def generate_sentence(model):
        phrase = ''
        t0, t1 = '$''$'
        while 1:
            t0, t1 = t1, unirand(model[t0, t1])
            if t1 == '$'break
            if t1 in ('.!?,;:'or t0 == '$':
                phrase += t1
            else:
                phrase += ' ' + t1
        return phrase.capitalize()

    def unirand(seq):
        sum_, freq_ = 00
        for item, freq in seq:
            sum_ += freq
        rnd = uniform(0, sum_)
        for token, freq in seq:
            freq_ += freq
            if rnd < freq_:
                return token

    if __name__ == '__main__':
        model = train('tolstoy.txt')
        for i in range(10):
            print generate_sentence(model),


    Отлично, вы добрались до конца. Завидую вашему терпению :).

    Почему триграммы


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

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 35

      +2
      > Биграммы давали бы плохой результата, в то время как 4-граммы требовали бы существенно больше ресурсов.
      Зато, тем качественнее будут тексты поискового спама.
        +2
        Может быть. Я слабо знаком с поисковой оптимизацией. Но есть вероятность что они будут рассматриваться как дубли, так как текст становиться ооочень похож на исходный. В этом случае нужно использовать разные корпуса по разным тематикам.
          +3
          Кстати, у Яндекса есть статья о том, как они с этим борются:

          «Поиск неестественных текстов», Евгений Гречников, Глеб Гусев, Андрей Кустарев, Андрей Райгородский.
            –1
            Ну вообщем-то в Интернете и так сейчас особо искать нечего. Да и зная историю Вы я думаю спрогнозируете
            что будет с княжествами (левыми сайтами) и почему появяться государства (фирменные порталы при универах
            фирмах и т.п.). Явные тому примеры базы знаний при Microsoft, FreeBSD про линукс кстати не знаю есть или нет?
            Одним словом скоро весь интернет перейдет в вид сообществ, социальных сетей и баз знаний… ИМХО!
            +1
            Достойно! Прочитал, попробовал :)
            +2
            Тексты интересные получаются.
            Особенно понравилось: «Сноска 49 философ, сноска 130 княгиня такая-то сноска 131» и «История своим предметом не хотеть принять меня за щеку».
              +2
              Нет желания написать модуль дизамбигуации (разрешения неоднозначности) к морфологическому анализатору pymorphy?)

              Например, в фразе «нет вилки» — «вилки» — это существительное ед.ч., в родительном падеже. А в «Положил вилки на стол» — это существительное во мн.ч. и в винительном падеже.

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

              Несмотря на то, что, по сути, анализатор будет тренироваться сам на себе, думаю, подход должен сработать, т.к. не у всех слов есть те же проблемы с неоднозначностью, что и у слова «вилка» — и тут вполне можно обойтись без синтаксического анализа. Могут быть какие-то тонкости, но по сути — те же биграммы, триграммы и тд.
                +1
                В идеале, конечно, тренировать не на самом себе, а на отдельно размеченном корпусе (http://www.ruscorpora.ru/), но там нет оффлайн-доступа, только ограниченный и неподходящий для таких целей online-поиск, поэтому вряд ли выйдет.
                  +2
                  А на счет ruscorpora.ru, я честно говоря не понимаю смысл проекта. Почему бы не открыть корпус, если таковой имеется. Тем более называется национальным и создается на государственные деньги.
                    +1
                    «Какие-либо оффлайновые версии корпуса пока недоступны, но работа в этом направлении ведётся.»

                    Национальный корпус русского языка
                    © 2003–2010

                    Я думаю, что этим сайтом занимаются очень уважаемые люди, и делают они хорошее дело, но заточен он под нужны лингвистов (не компьютерных), и оффлайн-доступ для этого не так востребован.
                  +1
                  Думаю, снятие неоднозначности не очень подходит для уровня морфологии. Это что-то ближе к синтаксическому анализу, где может уйти большая часть омонимии. К примеру — «краска стекла по стене» и «в машине нет лобового стекла». Здесь выбор виден из контекста. То есть если писать дизамбигуатор только на основе n-граммной статистики, то он будет неточный и очень сильно зависимый от корпуса.

                  Вообще, мне не лень его написать :), но я на вскидку не вижу чем этот модуль будет полезен.
                    +1
                    Хорошая бумага по теме: www.aot.ru/docs/RusCorporaHMM.htm

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

                    Модуль будет полезен хм… везде) Хотя бы отсортировать результаты разбора слова по вероятности, чтобы менее вероятные в данном контексте не учитывать. Сейчас берется первая попавшаяся форма слова, когда нужна только 1 форма (например, для склонятора).
                      +1
                      Может быть обрисуете как вы видите этот модуль, желательно по почте ( at gmail.com)? Может быть что-то придумаем.

                      Вообще, я как-то писал морфологический анализатор, так же на основе словаря аот. Но в основе у меня лежал трансдьюсер (finite state transducer), базу не использовал. У этого подхода есть плюсы, но есть и минусы. Если интересно — могу подробней по почте.
                        0
                        Ага, так и понял, судя по сайту. Поэтому и рискнул предложить) В почту сейчас отпишусь.
                  0
                  Мне кажется или Вы описали реализацию генератора текстов на основе цепей Маркова?
                    0
                    Вобщем, да. Цепь маркова, сеть Байеса, как угодно.
                    Лично мне проще воспринимать подобные модели просто как направленный взвешенный граф, где дуги маркированны вероятностями перехода на следующее состояние.
                    0
                    А какая в вас версия питона?
                    У меня 2.5.2 и в ней не работают конструкции типа
                    sum_, freq_ =,
                    rnd = uniform(, sum_)
                    для переносимости можно поправить на
                    sum_, freq_ = 0, 0
                    rnd = uniform(0, sum_)
                    тогда всё работает на 2.5
                      0
                      Писал все это на 2.5.
                      Но дело похоже в другом: когда «красил» код, похоже, некоторые символы пропали. На этом месте должны были стоять нули:

                      def unirand(seq):
                      sum_, freq_ = 0, 0
                      for item, freq in seq:
                      sum_ += freq
                      rnd = uniform(0, sum_)
                      for token, freq in seq:
                      freq_ += freq
                      if rnd < freq_:
                      return token

                      Ту же статью можно глянуть тут: linguis.ru/art/trigram, там корректно.

                      Кстати, может кто знает, как раскрасить питоновский код на хабре? Встроенными средствами у меня не получилось.
                        +1
                        Тогда уж ещё позанудствую. У вас sum_ в unirand в конце концов всегда равно 1.0 ,-) Это же сумма всех вероятностей.
                          0
                          Вы правы. Рад что внимательно смотрите код :). Сумма тут всегда равна 1. Похоже я взял этот метод из своего кода, который допускает любое значение частоты.
                          Здесь же можно использовать просто рандом.

                          Надо сказать, писал я этот код больше года назад. Сейчас вижу, что функция unirand могла бы быть более прозрачна.
                        0
                        ваше благородие? Ничто, — прибавил он, как казалось ростову. Тоже и они тотчас же притворился изумленным, ошеломленным, выпучил глаза и долго, облокотившись на руку, молодой и красивой, белой кисеи и розовых чубука.

                        Вообще вроде как это называется «цепь Маркова третьего порядка»
                          –3
                          Такие вещи нынче, как то, что можно было назвать «генерирование текста по статистическому анализу биграмм и триграмм слов», что и так уже понятно всем, реализовать в рамках одной лабы второго курса и забыть на след. день, теперь расписывается в целую статью и висит на главной хабра.
                            0
                            Эм… да, алгоритм простой. Висел в личном блоге, получил пару сообщений с рекомендацией перенести сюда. Вот и перенес :).
                              –1
                              Ну раз рекомендуют, видимо хотят это видеть… об этом я с некоторым пренебрежением и писал.
                              А лично вас — автора — не осуждаю )
                            0
                            дорвейщики уже сели за компьютеры )
                              0
                              и усилено учат питон )
                                +2
                                дорвейщики давно уже это проходили ;)
                              0
                              уникальность текста 69%
                                0
                                А правильно ли я понимаю, что подобным образом работают vesna.yandex.ru и другие «loremipsum-генераторы»?
                                  0
                                  Похоже, основа та же. Наврятли там использовалась какая-либо грамматика на правилах.
                                  Но текст относительно «чистый» получается. Скорее всего там еще какие-то хитрые алгоритмы поверх идут.

                                  ps но могу и ошибаться
                                    0
                                    По-моему, на яндексе составленная вручную контекстно-свободная грамматика.
                                    0
                                    Вы Natural Language Toolkit (nltk.org) смотрели?
                                    Рутинные задачи по разбору на слова я бы отдал этой библиотеке, тем более что делать она будет это в терминах предметной области.
                                      0
                                      Да, смотрел. Но nltk здесь — как из пушки по воробьям. В данном случае даже морфология не используется — обычная тренировка на корпусе (даже без сглаживания) и подбор слов по вероятности. Может быть, через время напишу «правильный генератор», где буду использовать и морфологию, и синтаксис и, возможно, какие-то элементы семантики.
                                        0
                                        Задачи имеют тенденцию со временем усложнятся. Для меня плюс nltk что я буду сосредоточен на конечной задаче, а не на низкоуровневых деталях.

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

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