Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 10
Ухх, после прочтения статьи меня тоже "поперло". Спасибо вам за новые идеи и мотивацию. Ни за что бы не понял что это перевод
Важное дополнение от пользователя berez
Приведение слов к лемме затруднит генерацию нового текста, тк слова придется приводить обратно в исходную форму.
Это справедливо, но как тогда сделать значимые взаимосвязи в больших текстах? Или это, всё-таки, не требуется? Буду рада мнениям, как решить эту ситуацию!
Также хочу поблагодарить каждого, и пользователя berez в частности за внимательность к опечаткам. У меня две проблемы — западающие клавиши и «торопыжность». Впредь буду внимательнее!
Приведение слов к лемме затруднит генерацию нового текста, тк слова придется приводить обратно в исходную форму.
Это справедливо, но как тогда сделать значимые взаимосвязи в больших текстах? Или это, всё-таки, не требуется? Буду рада мнениям, как решить эту ситуацию!
Также хочу поблагодарить каждого, и пользователя berez в частности за внимательность к опечаткам. У меня две проблемы — западающие клавиши и «торопыжность». Впредь буду внимательнее!
Спасибо за аккуратную статью и доходчивые объяснения!
Тоже недавно пробегался по теме — но вышло более обзорно и сумбурно, и потому, когда возникла потребность объяснить начинающему, пришлось выискивать материал с более мягким входом. Ваша статья как раз самое то!
Почему-то цепи Маркова любят разбирать на примере цепочки слов, хотя цепочки букв, как мне кажется, разбирать гораздо проще. Заодно при разборе цепей Маркова на буквах отпадают вопросы типа «а не надо ли привести слова к словарной форме?».
Ну и да, в цепях Маркова нет контекста, но есть текущее состояние. А оно вовсе не обязательно ограничивается одним словом или буквой: состояние может содержать и более длинные цепочки. Тогда таблица переходов выглядит примерно так:
Скажем, начальное состояние у нас — «ба». По таблице состояний видно, что из «ба» с вероятностью 0,3 получится «баб», с вероятностями 0,2 — «бак», «бан» или «бая», и с вероятностью 0,1 — «бао». Далее от получившейся цепочки отбрасываем один символ слева, и у нас получается следующее состояние (допустим, выпало у нас «баб» — значит, следующее состояние будет «аб»).
Ну и последнее, что в голову пришло: автор программы схалявил и не стал вычислять правильную таблицу переходов (с нормализованными вероятностями и вот этим всем). Просто запихал все слова в списки, и если одно и то же слово встречается в каком-то состоянии много раз — оно просто много раз повторится в списке. Это, конечно, сильно упрощает программу, но при обработке больших текстов вам никакой памяти не хватит. :)
Ну и да, в цепях Маркова нет контекста, но есть текущее состояние. А оно вовсе не обязательно ограничивается одним словом или буквой: состояние может содержать и более длинные цепочки. Тогда таблица переходов выглядит примерно так:
"аб" -> [ "б": 0.2, "з": 0.2, "о": 0.2, "с": 0.1 ]
"ба" -> [ "б": 0.3, "к": 0.2, "н": 0.2, "о": 0.1, "я": 0.2 ]
Скажем, начальное состояние у нас — «ба». По таблице состояний видно, что из «ба» с вероятностью 0,3 получится «баб», с вероятностями 0,2 — «бак», «бан» или «бая», и с вероятностью 0,1 — «бао». Далее от получившейся цепочки отбрасываем один символ слева, и у нас получается следующее состояние (допустим, выпало у нас «баб» — значит, следующее состояние будет «аб»).
Ну и последнее, что в голову пришло: автор программы схалявил и не стал вычислять правильную таблицу переходов (с нормализованными вероятностями и вот этим всем). Просто запихал все слова в списки, и если одно и то же слово встречается в каком-то состоянии много раз — оно просто много раз повторится в списке. Это, конечно, сильно упрощает программу, но при обработке больших текстов вам никакой памяти не хватит. :)
Спасибо за интересный материал.
В восьмидесятых периодически покупал и читал журнал «в мире науки» (что есть перевод «Scientific American»). И была в нём прекрасная рубрика «занимательный компьютер» (автор рубрики — Дьюдни. Автор «Core War», статей о множествах Мандельброта, клеточных автоматов и многого другого.
Среди прочих интересных статей прочёл там и о программах генерации текстов на основе цепей Маркова. Упоминалось и название программы, если правильно помню «Mark V Chains» (от «цепи Маркова»). Захотелось попробовать реализовать что-то подобное, но в этих математиках я не смыслил, а придуманный мною, с позволения сказать, «алгоритм», реализовать на БК-0010 было просто невозможно. Памяти мало, сохранять промежуточные данные вычислений на МК-60, а потом подгружать когда надо — это то ещё занятие. Да и надвигающийся призыв в армию не располагал к созерцанию искусственных текстов.
После армии, уже сидя на Спектруме, вновь вспомнилась статья. И снова всё упиралось в память, уже начал было контроллер на ВГ93 паять, как вдруг попался мне в руки ноунейм ноутбук на халяву, с жестким диском аж на 60 мегабайт, процессором 386SX16 и целыми двумя мегабайтами оперативки (храниться до сих пор, но разобран). Поиграв в цивилизацию, водрузил Win 3.11 и попавшийся под руки дельфи.
Попробовал написать что-то подобное. И да, на программиста я не учился…
Код был не просто кошмарен — на него смотреть было нельзя. Кнопочки были красивее. Но кое-как всё работало. Насколько я помню, принцип состоял в скармливании txt файла с текстом с последующей выдачей огромного файла, где в простом текстовом формате в каждой строке было слово, за ним через пробел то слово, которое встречалось за первым в исходном тексте и число, показывающее число, которое означало сколько раз пара первое-второе число встречалось в исходном тексте. Посему и исходный текст должен быть большим (чтобы сочетаний было больше одного) и результат обработки был громоздкий.
Вторым шагом выданный файл вновь скармливался той же программе. Все числа суммировались и программа генерировала случайные числа, по которым из второго файла выбиралось пара слов. Затем «второе» слово становилось «первым» и процесс повторялся. Пока программа не падала с ошибками. Как то примерно так.
Жаль что флоппи отказался хранить такой неаккуратный код, может быть вспомнил бы процесс точнее…
Образец сгенераченного текста нашёл в своём архиве:
«У него будет внимательнейшим образом изучено но замерев с моржами да стрелами пехота не унимается».
(Судя по поиску в гугле — это Перумов, «рождение мага». Хотя не помню у него моржов.)
Спасибо за интересную статью.
P.S. Соврал про дельфи. Visual Basic, конечно.
В восьмидесятых периодически покупал и читал журнал «в мире науки» (что есть перевод «Scientific American»). И была в нём прекрасная рубрика «занимательный компьютер» (автор рубрики — Дьюдни. Автор «Core War», статей о множествах Мандельброта, клеточных автоматов и многого другого.
Среди прочих интересных статей прочёл там и о программах генерации текстов на основе цепей Маркова. Упоминалось и название программы, если правильно помню «Mark V Chains» (от «цепи Маркова»). Захотелось попробовать реализовать что-то подобное, но в этих математиках я не смыслил, а придуманный мною, с позволения сказать, «алгоритм», реализовать на БК-0010 было просто невозможно. Памяти мало, сохранять промежуточные данные вычислений на МК-60, а потом подгружать когда надо — это то ещё занятие. Да и надвигающийся призыв в армию не располагал к созерцанию искусственных текстов.
После армии, уже сидя на Спектруме, вновь вспомнилась статья. И снова всё упиралось в память, уже начал было контроллер на ВГ93 паять, как вдруг попался мне в руки ноунейм ноутбук на халяву, с жестким диском аж на 60 мегабайт, процессором 386SX16 и целыми двумя мегабайтами оперативки (храниться до сих пор, но разобран). Поиграв в цивилизацию, водрузил Win 3.11 и попавшийся под руки дельфи.
Попробовал написать что-то подобное. И да, на программиста я не учился…
Код был не просто кошмарен — на него смотреть было нельзя. Кнопочки были красивее. Но кое-как всё работало. Насколько я помню, принцип состоял в скармливании txt файла с текстом с последующей выдачей огромного файла, где в простом текстовом формате в каждой строке было слово, за ним через пробел то слово, которое встречалось за первым в исходном тексте и число, показывающее число, которое означало сколько раз пара первое-второе число встречалось в исходном тексте. Посему и исходный текст должен быть большим (чтобы сочетаний было больше одного) и результат обработки был громоздкий.
Вторым шагом выданный файл вновь скармливался той же программе. Все числа суммировались и программа генерировала случайные числа, по которым из второго файла выбиралось пара слов. Затем «второе» слово становилось «первым» и процесс повторялся. Пока программа не падала с ошибками. Как то примерно так.
Жаль что флоппи отказался хранить такой неаккуратный код, может быть вспомнил бы процесс точнее…
Образец сгенераченного текста нашёл в своём архиве:
«У него будет внимательнейшим образом изучено но замерев с моржами да стрелами пехота не унимается».
(Судя по поиску в гугле — это Перумов, «рождение мага». Хотя не помню у него моржов.)
Спасибо за интересную статью.
P.S. Соврал про дельфи. Visual Basic, конечно.
Сейчас получить начальное представление о подобной текстогенерации можно даже без программирования. Во многих клавиатурах для мобильных ОС есть подсказки слов для начала набора фразы. Понажимав несколько раз, можно получить некоторый осмысленный текст, «натренированный» на конкретно вашем лексиконе.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Цепи Маркова и Пайтон — разбираемся в теории и собираем генератор текстов