Кодоход: Генерация произвольного текста: алгоритм Маркова

Полное состояние таблицы цепочек состоит из самой таблицы и длины слов префиксов. Структура Chain хранит эти данные.

Структура Chain имеет два неэкспортируемых поля (те, которые не начинаются с заглавной буквы), поэтому мы пишем функцию-конструктор NewChain, которая инициализирует карту chain с помощью make и устанавливает поле prefixLen.

Эта функция-конструктор не является строго необходимой, поскольку вся программа находится в одном пакете (main), и, следовательно, практически нет разницы между экспортируемыми и неэкспортируемыми полями. Можно было бы просто написать содержимое этой функции при необходимости создания новой цепочки. Однако использование этих неэкспортируемых полей является хорошей практикой; это ясно показывает, что только методы типа Chain и его функция-конструктор должны обращаться к этим полям. Кроме того, структурирование Chain в таком виде позволяет легко переместить его в собственный пакет в будущем.

Поскольку мы часто будем работать с префиксами, мы определим тип Prefix с конкретным типом []string. Определение именованного типа позволяет нам быть явными, когда мы работаем с префиксом вместо просто []string. Кроме того, в Go можно определять методы для любого именованного типа (не только для структур), поэтому мы можем добавить методы, работающие с Prefix, если это понадобится.

Первый метод, который мы определяем на Prefix, это String. Он возвращает string-представление Prefix, объединяя элементы среза с помощью пробелов. Мы будем использовать этот метод для генерации ключей при работе с цепной картой.

Метод Build читает текст из io.Reader и разбирает его на префиксы и суффиксы, которые хранятся в Chain.

io.Reader — это интерфейсный тип, который широко используется стандартной библиотекой и другим Go-кодом. Наш код использует функцию fmt.Fscan, которая читает пробельно-разделённые значения из io.Reader.

Метод Build завершает работу, когда метод Read объекта Reader возвращает io.EOF (конец файла) или другую ошибку чтения.

Эта функция выполняет множество мелких чтений, что может быть неэффективно для некоторых Readers. Для повышения эффективности мы оборачиваем предоставленный io.Reader с помощью bufio.NewReader, чтобы создать новый io.Reader, который обеспечивает буферизацию.

В начале функции мы создаём срез Prefix p, используя поле prefixLen объекта Chain в качестве его длины. Мы будем использовать эту переменную для хранения текущего префикса и изменять её с каждым новым словом, которое встречаем.

В цикле мы читаем слова из Reader fmt.Fscan возвращает ошибку, если она сталкивается с ошибкой чтения (io.EOF, например), или если не может считать запрашиваемое значение (в нашем случае — одиночную строку). В любом из этих случаев мы просто хотим остановить сканирование, поэтому используем break для выхода из цикла.

Слово, хранимое в s, является новым суффиксом. Мы добавляем новую комбинацию префикс/суффикс в карту chain, вычисляя ключ карты с помощью p.String и добавляя суффикс в срез, хранящийся под этим ключом.

Встроенная функция append добавляет элементы в срез и выделяет новое хранилище при необходимости. Когда предоставленный срез равен nil, append выделяет новый срез. Это поведение удобно сочетается с семантикой нашей карты: получение неустановленного ключа возвращает нулевое значение типа значения, и нулевое значение []string равно nil. Когда наша программа встречает новый префикс (что приводит к значению nil в карте), append выделит новый срез.

Для получения дополнительной информации о функции append и срезах в целом см. статью Slices: usage and internals.

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

В этом состоянии

p == Prefix{"I", "am"}
s == "not"

новое значение p будет

p == Prefix{"am", "not"}

Эта операция также требуется во время генерации текста, поэтому мы размещаем код, выполняющий это изменение среза, внутри метода типа Prefix под названием Shift.

Метод Shift использует встроенную функцию copy для копирования последних len(p)-1 элементов p в начало среза, эффективно перемещая элементы на один индекс влево (если считать ноль как самый левый индекс).

p := Prefix{"I", "am"}
copy(p, p[1:])
// p == Prefix{"am", "am"}

Затем присваивается предоставленное значение word последнему индексу среза:

// suffix == "not"
p[len(p)-1] = suffix
// p == Prefix{"am", "not"}

Метод Generate похож на Build, за исключением того, что вместо чтения слов из Reader и хранения их в карте, он читает слова из карты и добавляет их в срез (words).

Generate использует условный цикл for для генерации до n слов.

На каждой итерации цикла мы получаем список потенциальных суффиксов для текущего префикса. Мы обращаемся к карте chain по ключу p.String() и присваиваем её содержимое переменной choices.

Если len(choices) равен нулю, мы выходим из цикла, поскольку для этого префикса нет потенциальных суффиксов. Эта проверка также работает, если ключ вообще отсутствует в карте: в этом случае choices будет nil, а длина nil среза равна нулю.

Для выбора суффикса мы используем функцию rand.Intn. Она возвращает случайное целое число от нуля (включительно) до заданного значения (исключая его). Передача len(choices) даёт нам случайный индекс в пределах длины списка.

Мы используем этот индекс для выбора нового суффикса, присваиваем его переменной next и добавляем в срез words.

Далее мы вызываем метод Shift с новым суффиксом, аналогично тому, как это делалось в методе Build.

Перед возвратом сгенерированного текста в виде строки мы используем функцию strings.Join для объединения элементов среза words, разделённых пробелами.

Чтобы было удобно настраивать длину префикса и длину генерируемого текста, мы используем пакет flag для разбора флагов командной строки.

Вызовы flag.Int регистрируют новые флаги в пакете flag. Аргументы функции Int — это имя флага, его значение по умолчанию и описание. Функция Int возвращает указатель на целое число, которое будет содержать значение, указанное пользователем (или значение по умолчанию, если флаг не был указан в командной строке).

Функция main начинается с разбора флагов командной строки с помощью flag.Parse и инициализации генератора случайных чисел пакета rand текущим временем.

Если флаги командной строки, предоставленные пользователем, являются некорректными, функция flag.Parse выведет информативное сообщение об использовании и завершит работу программы.

Чтобы создать новый Chain, мы вызываем NewChain с значением флага prefix.

Чтобы построить цепочку, мы вызываем Build с os.Stdin (который реализует io.Reader), чтобы он читал входные данные из стандартного ввода.

После построения цепочки мы вызываем метод Generate с заданной длиной генерируемого текста. Этот метод возвращает сгенерированный текст в виде строки.

Чтобы использовать эту программу, сначала соберите её с помощью команды go:

$ go build markov.go

А затем выполните её, передав входной текст через конвейер:

$ echo "a man a plan a canal panama" \
| ./markov -prefix=1
a plan a man a plan a canal panama

Вот транскрипт генерации текста с использованием файла README из дистрибутива Go в качестве исходного материала:

$ ./markov -words=10 < $GOROOT/README
This is the source code repository for the Go source
$ ./markov -prefix=1 -words=10 < $GOROOT/README
This is the go directory (the one containing this README).
$ ./markov -prefix=1 -words=10 < $GOROOT/README
This is the variable if you have just untarred a

Функция Generate выполняет множество выделений памяти при построении среза words. В качестве упражнения измените её, чтобы она принимала io.Writer, в который постепенно записывает сгенерированный текст с помощью Fprint. Помимо повышения эффективности, это делает функцию Generate более симметричной по отношению к функции Build.