Варианты структуры данных
На какой размер вводимого текста мы должны рассчитывать? Насколько быстро должна работать программа? Представляется логичным, чтобы программа была в состоянии считать целую книгу, так что нам надо быть готовыми к размеру ввода в n = 100 000 слов и более. Вывод должен составлять сотни, а возможно, и тысячи слов, а работать программа должна несколько секунд, но отнюдь не минут. Имея 100 000 слов вводимого текста, надо признать, что п получается достаточно большим, так что для того, чтобы программа работала действительно быстро, алгоритм придется писать довольно сложный.
Для того чтобы начать генерировать текст, алгоритм markov должен сначала просмотреть весе введенный фрагмент, поэтому исходный текст нам придется каким-то образом сохранять. Первая возможность – ввести полностью исходный текст и сохранить его как длинную строку, но нам явно нужно разбить его на отдельные слова. Если сохранить его как массив указателей на слова, генерация вывода будет происходить просто: для выбора нового слова надо просканировать введенный текст и посмотреть, какие существуют слова-суффиксы для только что введенного префикса, и выбрать из них случайным образом одно. Однако это будет означать сканирование всех 100 000 слов ввода для генерации каждого нового слова; при размере выводимого текста в 1000 слов необходимо осуществить сотни миллионов сравнений строк, а это вовсе не быстро.
Другая возможность – хранить только уникальные слова исходного текста вместе со списком, указывающим, где именно они появлялись в оригинале. В этом случае мы сможем находить устраивающие нас слова более быстро. Мы могли бы использовать хэш-таблицу вроде той, что обсуждалась в главе 2, однако та версия не соответствует специфическим требованиям алгоритма markov, для которого нам надо по заданному префиксу быстро находить все возможные суффиксы.
Нам нужна структура данных, которая бы более успешно представляла префикс и ассоциированные с ним суффиксы. Программа будет работать в два прохода: при проходе ввода будет создаваться структура данных, представляющая фразы, а при проходе вывода эта структура будет использоваться для случайной генерации текста. При обоих проходах нам надо будет отыскивать префикс (причем быстро отыскивать!): при первом – для обновления его суффиксов, а при втором – для случайного выбора одного из связанных с ним суффиксов. Из этих требований логично вырисовывается такой вид хэш-таблицы: ключами ее являются префиксы, а значениями – наборы (множества) суффиксов для соответствующего префикса.
Для целей описания мы зафиксируем длину префикса в два слова, так что каждое выводимое слово будет базироваться на двух предшествующих. Количество слов в префиксе не влияет на проектирование, и программа сможет обрабатывать префиксы с любым количеством слов, но выбрав это число сейчас, мы просто сделаем разговор более конкретным. Префикс и множество всех возможных для него суффиксов мы назовем состоянием (state), что является стандартным термином для алгоритмов, связанных с марковскими цепями.
Для каждого заданного префикса мы должны сохранить все употребляемые после него суффиксы, чтобы потом иметь возможность их использовать. Суффиксы не упорядочены и добавляются по одному зараз. Мы не знаем их количества заранее, поэтому нам потребуется структура данных, которая могла бы увеличиваться легко и эффективно; такими структурами являются список и расширяемый массив. При генерации выходного текста мы должны иметь возможность выбрать случайным 3 образом один суффикс из всего множества суффиксов, возможных для конкретного префикса. Элементы никогда не удаляются.
Что делать, если фраза встречается более одного раза? Например, фраза "может появиться дважды" может появиться дважды, а фраза "может появиться единожды" – только единожды. В таком случае можно поместить слово "дважды" два раза в список суффиксов для префикса "может появиться" или один раз, но при этом установить соответствующий суффиксу счетчик в 2. Мы попробовали и со счетчиками, и без них; без счетчиков проще, поскольку при добавлении суффикса не надо проверять, нет ли его уже в списке. Эксперименты показали, что разница в скорости при обоих способах практически незаметна.
Итак, давайте подведем итоги. Каждое состояние включает в себя префикс и список суффиксов. Эта информация хранится в хэш-таблице, ключами которой являются префиксы. Каждый префикс представляет собой набор слов фиксированного размера. Если суффикс появляется более одного раза после данного префикса, то каждое новое появление отмечается еще одним включением этого суффикса в список.
Теперь следует решить, как представлять сами слова. Простейший способ – хранить их как отдельные строки. Поскольку в большинстве текстов много слов появляется более одного раза, для сохранения места лучше использовать еще одну хэш-таблицу – для отдельных слов, каждое из которых будет храниться лишь единожды. Это ускорит хэширование (помещение в хэш-таблицу) префиксов, поскольку мы сможем сравнивать указатели, а не отдельные символы: уникальные строки будут иметь уникальные адреса. Проектирование этой структуры мы оставим вам для самостоятельных упражнений; пока же строки будут храниться раздельно.