CTAPbIu_MABP's BLOG

Я что-то не особо любил учиться в школе, потом в институте, а сейчас в институте ничему не учат, приходишь два раза в год сдаёшь сессию и не заморачиваешься - заочный в общем. Тяжелее всего мне в школе давалась вышка и физика. Все, кто мне говорил, что вышка нужна для программирования посылались на хуй не задумываясь. Да на хуй вышка нужна быдлокодеру на HTML и PHP?! :D. Но вот не такое уже и большое время назад я понял, что было бы неплохо знать, о чем идет речь, когда читаешь статью о программировании. Все началось наверное когда я прочел об алгоритме сортировки quicksort. Потом мне как-то на глаза попалась заметка Пылесос Kirby не удаляет пыль Фату с ковра Серпинского, естественно полез узнавать что это такое :) Где-то посреди поисков нашел фразу "Пылесос Kirby не удаляет пыль Фату с ковра Серпинского просыпанную из бутылку Клейна", еще один умный термин в копилку. Кстати больше никогда не буду упоминать бутылку Клейна в разговоре, не с моим талантом объяснять людям, что это такое. И одним из последних мне на глаза попался фрактал Мандельброта. Так вот к чему это я так долго веду... К тому что я в рамках собственного ликбеза и наполнения блога статьями по Java написал реализацию цепей Маркова, а все вышесказанное плавно подводило к тому что это граф из высшей математики.

Мне тут уже мягко намекали что реализации этого алгоритма есть уже на всех языках программирования, потому что он используется (использовался?) для генерации дорвеев. Я не спорю, но это была неплохая возможность потренироваться, и добавить контента на сайт. Большую часть времени написания данного чуда составило аж никак не программирование и не высшая математика, а попытки настроить applet так, чтоб эта зараза могла открывать локальные файлы. предупреждение об этом вы видели когда загрузили страницу и согласились, или не согласились, тогда вам нужно нажать ctrl+r.

Описания того как при помощи цепей Маркова генерировать тексты в сети полно, но я рискну повториться. Берем исходный осмысленный текст и раскладываем его на последовательности, для примера я взял скороговорку:

Ехал Грека через реку.
Видит Грека в реке рак.
Сунул в реку руку Грека.
Рак за руку Грека - цап. 

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

{
ехал=[грека],
грека=[через, в], 
через=[реку], 
реку=[видит, руку], 
видит=[грека], 
в=[реке, реку], 
реке=[рак], 
сунул=[грека], 
руку=[греку, рак]
рак=[за],
за=[руку], 
греку=[цап], 
}

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

Грека через реку видит Грека в реке рак за руку Греку цап.

Смысла конечно в предложении не много, и от оригинала не сильно отличается, просто у нас очень короткий исходный текст. Посмотрев на этот набор слов мы удостоверились что все слова по парно стыкуются по падежам, и похожи на реальный текст. Но из 4 строчек много не нагенеришь, я тут давеча взял на lib.ru Войну и Мир (500 кб) и попробовал нагенерить пару страниц оттуда, получаются весьма забавные перлы! Но как правильно заметил один человек в Войну и Мир слово "кондиционер" не впихнешь. А еще, я надеюсь, это все таки он написал статью, о том как отличить текст нагенеренный из 4 строчек 30 килобайт исходного текста до целого мегабайта.

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

package ua.kiev.mabp;


/**
 * Created by IntelliJ IDEA.
 * User: CTAPbIu_MABP
 * Date: 26.01.2009
 * Time: 21:04:28
 */


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;


import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.DataInputStream;
import java.io.BufferedInputStream;


import java.awt.Button;
import java.awt.Dimension;
import java.awt.FileDialog;
import java.awt.Frame;
import java.awt.TextArea;


import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;


import java.applet.Applet;




public class MarkovChainApplet extends Applet implements ActionListener {


    public void init() {
        // Порисуем :)
        setSize(300,150);
        Button btn = new Button("Select file!");
        btn.addActionListener(this);
        add(btn);
        add(new TextArea(5,30));
    }


    public void actionPerformed(ActionEvent event) {


        // Получаем файл
        FileDialog fd = new FileDialog(new Frame(), "Please choose a file:", FileDialog.LOAD);
        fd.setVisible(true);
        File file = new File(fd.getDirectory() + fd.getFile());
        System.out.println("Reading file " + fd.getDirectory() + fd.getFile());


        // Читаем файл
        String filestring = null;
        try {
            DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(file)));


            try {
                byte[] infile = new byte[dis.available()];
                filestring = new String(infile, 0, dis.read(infile));
            } catch (IOException e) {
                System.out.println("File read error...");
                e.printStackTrace();
            }
            // Если нажали на кнопку "Отмена"
        } catch (FileNotFoundException e) {
            System.out.println("File not found...");
            e.printStackTrace();
        }


        // Файл был пустой
        if (filestring != null && filestring.length() > 0) {


            // Причесываем текст
            String text = filestring.toLowerCase()
                    // Переводим все в нижний регистр, убираем цифры, спецсимволы и лишнии пробелы
                    .replaceAll("[\\d\\(\\)\\[\\]\\{\\}'\"\\*$\\\\\\/^~_,:;%@#&|+=—-]", "")
                    .replaceAll("\\s+", " ");


            // Составляем карту
            Map<String, Set<String>> markovMap = new HashMap<String, Set<String>>();
            String[] sentenses = text.split("[\\.\\?!]\\s?");
            for (int i = 0, j = sentenses.length; i < j; i++) {
                String[] words = sentenses[i].split(" ");
                for (int k = 0, l = words.length - 1; k < l; k++) {
                    if (markovMap.containsKey(words[k])) {
                        markovMap.get(words[k]).add(words[k + 1]);
                    } else {
                        markovMap.put(words[k], new HashSet<String>(Arrays.asList(words[k + 1])));
                    }
                }
            }


            // Строим последовательности
            List<LinkedList<String>> prepared = new ArrayList<LinkedList<String>>();
            Random random = new Random();
            // генерируем 10 предложений
            for (int s = 0; s < 10; s++) {
                ArrayList<String> keys = new ArrayList<String>(markovMap.keySet());
                String prev = keys.get(random.nextInt(keys.size()));
                LinkedList<String> sentense = new LinkedList<String>(Arrays.asList(prev));
                for (Set<String> next = markovMap.get(prev);
                     // по 10-20 слов в каждом
                     next != null && !next.isEmpty() && sentense.size() < 10 + random.nextInt(10);
                     next = markovMap.get(prev)) {
                    List list = Arrays.asList(next.toArray());
                    prev = (String) list.get(random.nextInt(list.size()));
                    sentense.add(prev);
                }
                prepared.add(s, sentense);
            }


            // Генерируем из последовательностей текст
            StringBuilder generatedText = new StringBuilder();
            for (LinkedList<String> sentense : prepared) {
                if (sentense.size() > 5) {
                    for (String words : sentense) {
                        generatedText.append(" ").append(words);
                    }
                    generatedText.append(".");
                }
            }


            // Выводим на экран
            ((TextArea) getComponent(1)).setText(generatedText.toString());
        }
    }
}

Я сегодня такой добрый, что даже покажу как это все скомпилить так чтобы не вылазила ошибка? о том что апплет не имеет доступа в файловой системе. Следующий код можно сохранить как *.bat:

javac path/to/your/package/ClassNameApplet.java
jar cf cna.jar path/to/your/package/ClassNameApplet.class
keytool -genkey -keystore YOU_SITE_NAME.YOUR_DOMAIN -keyalg rsa -dname "CN=YOUR_NAME, OU=, O=, L=, ST=, C=" -alias YOUR_NAME -validity 3600 -keypass YOUR_PASSWORD -storepass YOUR_PASSWORD
jarsigner -keystore YOU_SITE_NAME.YOUR_DOMAIN -storepass YOUR_PASSWORD -keypass YOUR_PASSWORD -signedjar ClassNameApplet.jar cna.jar YOUR_NAME 

Ну и конечно же дам поиграться результатом. Еще раз напомню если вы при загрузке страницы нажали на большом алерте с надписью "Do you want to run the application?" кнопку "нет" то сейчас нужно нажать ctrl+r и на повторно вылезшем алерте нажать "да", иначе кина не будет. Если алерт повторно не вылез, то к сожалению, скорее всего придется закрыть браузер и открыть повторно.