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

Следует признать, что такая задача в полном объёме непосильна для нас. Однако проверить длину и разнообразие слов, составляющих палиндром, вполне возможно. В роли меры качества палиндрома можно было бы взять суммарную длину его слов, однако тогда качественными станут палиндромы, состоящие из многократно повторяющихся зеркально-симметричных слов. Лучшим решением была бы сумма длин слов без учёта их повторений. Но эта величина в среднем пропорциональна количеству слов в палиндроме. Чтобы устранить такую зависимость, поделим сумму длин слов без повторов на количество слов в палиндроме (с учётом их кратности).

Наши опыты показали, что палиндромы, имеющие уровень качества порядка пяти или выше, являются хорошими кандидатами для ручного отбора. Расстановка знаков пунктуации, естественно, будет производиться в ручном режиме.

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

Такое использование словаря приводит к следующей объектной модели:

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

Дадим классу, реализующему словарь, предварительное имя Lexicon. Мы намерены реализовать словарь несколькими способами; имена соответствующих классов будут содержать это имя в своей основе.

Наиболее простым для реализации был бы словарь на основе массива. Добавление слов в массив не должно вызвать никаких затруднений — на то имеется встроенная процедура push. Наиболее трудный и часто вызываемый метод — suitableWords — можно запрограммировать с использованием встроенной процедуры grep.

Очевидным недостатком хранения слов в массиве является трудоёмкость поиска подходящих слов: каждый раз при поиске перебираются все без исключения слова из словаря. Для сколько-нибудь больших словарей это обстоятельство замедляет работу программы совершенно ужасно. Для словаря из полутора с лишним миллионов слов поиск подходящего слова занимает несколько секунд. Вряд ли следует рассчитывать на получение даже двухсловных палиндромов для словарей такого объёма за разумное время.

Ещё одна проблема — словарь на основе массива может содержать одно и то же слово в нескольких экземплярах. Можно, конечно, проверять для каждого добавляемого слова, не содержится ли оно уже в словаре. Но тогда по мере роста словаря добавление слов станет всё медленней и медленней, поскольку такая проверка потребует сравнения добавляемого слова с каждым, уже присутствующем в словаре. Мы не станем выполнять такую проверку, полагаясь на то, что источником слов для заполнения словаря будет проверенный файл, не содержащий дубликатов.

Мы реализуем словарь на базе массива — лишь для того, чтобы убедиться в его крайней неэффективности, и чтобы было с чем сравнивать другую, лучшую реализацию. Класс, объектами которого будут словари на базе массива, назовём Lexicon::Array.

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

Напомним, что слово из словаря подходит слева к данной строке, если

Подходящие слова первого рода следует искать среди конкретного перечня кандидатур. Например, для строки стол кандидатами будут с (предлог, наверняка есть в словаре!), ст, сто (числительное, тоже, наверное, есть в словаре!).

Для подходящих слов второго рода уже нет готового списка кандидатур. В нашем большом словаре русских слов и словоформ их нашлось 1008: начиная с самого слова стол и заканчивая странным словом столярящую.

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

Для словаря, состоящего из $n$ слов, двоичный поиск даст примерно ${\log }_{2}n$ этапов. Для словаря из полутора миллиона слов это $21$ этап, или $21$ сравнение. Это совсем немного. При сплошном поиске в худшем случае (когда искомое слово находится в самом конце списка) пришлось бы выполнить все $n$ cравнений (полтора миллиона), а в среднестатистическом случае — вдвое меньше.

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

Подсчитаем, сколько сравнений слов потребуется при составлении упорядоченного списка из $n$ слов. Вставка второго слова протребует одного сравнения ($1={\log }_{2}2$), вставка последующих слов приведёт к ${\log }_{2}3$, ${\log }_{2}4$, ${\log }_{2}5$, $\dots$, ${\log }_{2}n$ сравнений. Всего получится $${\sum }_{i=2}^n{\log }_{2}i={\log }_2\left({\prod }_{i=2}^{n}i\right)={\log }_2\left(n!\right)\text{.}$$

Чтобы оценить полученное число для $n=1500000$, мы, конечно, не будем вычислять $1500000!$ (страшно даже подумать о том, насколько велико это число). Вместо этого применим уже известную асимптотическую формулу Стирлинга $n!\asymp \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$: $${\log }_2\left(n!\right)\asymp {\log }_2\sqrt{2\pi n}+n{\log }_2\frac{n}{e}\text{.}$$ При $n=1500000$ эта формула даёт приближённое значение $\mathrm{28610777,\dots }$ (точное значение, полученное сложением двоичных логарифмов чисел от $2$ до $1500000$, равно $\mathrm{28610765,\dots }$, что позволяет судить о точности формулы Стирлинга при больших $n$).

А теперь разберёмся с подходящими слева словами второго рода. Заметим, что в упорядоченном массиве они встречаются подряд, непрерывным блоком. Каждое из них, $w$, удовлетворяет системе лексикографических неравенств $s\preccurlyeq w\prec s^{\prime }$, где $s$ — строка, к которой подходит слово $w$, а $s^{\prime }$ — строка, получаемая из $s$ заменой последнего символа на следующий за ним по алфавиту. К примеру, если $s=$стол, то $s^{\prime }=$стом, поскольку буква м следует по алфавиту сразу за л.

Осталось найти в упорядоченном массиве индексы строк $s$ и $s^{\prime }$ (или мест для их вставки). Индексы подходящих слов второго рода будут удовлетворять неравенствам $\mathrm{index}s⩽\mathrm{index}w<\mathrm{index}{s}^{\prime }$.

Вспомним, как происходит поиск нужной книги в библиотеке. Начинается он с каталога. Карточка в каталоге содержит, помимо прочей информации, координаты книги — номер стеллажа, полки в нём, и места на полке. Так что найти книгу — это то же самое, что и найти её карточку. Если бы поиск карточки производился путём полного перебора, поиск в большой библиотеке затягивался бы на годы. Но карточки сгруппированы по первым буквам (названия или фамилии автора): разные буквы — разные ящики с карточками.

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

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

Удобно организовать словарь на основе ассоциативного массива. Ключами в нём служат первые буквы. Значением, соответствующим ключу (первой букве) будут ссылки на словари, содержащие слова, получаемые удалением этой первой буквы. Поясним на примере словаря клопа, лёша, на, нашёл, полке. Такой словарь содержит слова, начинающиеся с букв к, л, н (два слова), п. Ключу к будет отвечать ссылка на словарь из одного слова — лопа. В этом словаре единственному ключу л будет отвечать словарь с ключом о, указывающим на словарь с ключом п, указывающим на словарь с ключом а, указывающим на… На что же будет указывать этот ключ? На словарь, состоящий из единственного пустого слова. Но в пустом слове нет первой буквы. Договоримся представлять словарь, состоящий из пустого слова, как ассоциативный массив, единственным ключом в котором служит пустая строка, а соответствующим значением — неважно что… Пусть это значение будет неопределённым. Во всех остальных случаях ключами в словаре будут односимвольные строки, и лишь для словаря, включающего одну-единственную пустую строку, ключом станет эта самая пустая строка в знак того, что этот словарь последний в древовидной иерархии словарей. Итак, слову клопа (единственному, начинающемуся с буквы к), будет соответствовать такая ветвь дерева:

Perl
'к'=>{ 'л'=>{ 'о'=>{ 'п'=>{ 'а'=>{ ''=>undef } } } } }

Подобным же образом будут устроены и ветви для слов лёша, полке:

Perl
'л'=>{ 'ё'=>{ 'ш'=>{ 'а'=>{ ''=>undef } } } },
'п'=>{ 'о'=>{ 'л'=>{ 'к'=>{ 'е'=>{ ''=>undef } } } } }

Для слов на, нашёл (у них общая начальная буква, и вторая, кстати, тоже) ветвь устроена интересней:

Perl
'н'=>{ 'а'=>{ ''=>undef, 'ш'=>{ 'ё'=>{ 'л'=>{ ''=>undef } } } } }

А вот и полная структура словаря:

Perl
{
	'к'=>{ 'л'=>{ 'о'=>{ 'п'=>{ 'а'=>{ ''=>undef } } } } },
	'л'=>{ 'ё'=>{ 'ш'=>{ 'а'=>{ ''=>undef } } } },
	'н'=>
	{
		'а'=>
		{
			''=>undef,
			'ш'=>{ 'ё'=>{ 'л'=>{ ''=>undef } } }
		}
	},
	'п'=>{ 'о'=>{ 'л'=>{ 'к'=>{ 'е'=>{ ''=>undef } } } } }
}

Для словаря бодро, бредил, гордо, лидер получится следующее:

Perl
{
	'б'=>
	{
		'о'=>{ 'д'=>{ 'р'=>{ 'о'=>{ ''=>undef } } } },
		'р'=>{ 'е'=>{ 'д'=>{ 'и'=>{ 'л'=>{ ''=>undef } } } } }
	},
	'г'=>{ 'о'=>{ 'р'=>{ 'д'=>{ 'о'=>{ ''=>undef } } } } },
	'л'=>{ 'и'=>{ 'д'=>{ 'е'=>{ 'р'=>{ ''=>undef } } } } }
}

Не зря в описании конструкции словаря мы использовали слово «древовидный». Такую структуру можно наглядно представить в виде дерева, в котором буквы служат узлами, а ссылки — нисходящими ветвями. Особые, терминальные узлы, то есть такие, из которых ветви уже не выходят, обозначены на рисунке знаком заземления. Их ровно столько, сколько слов содержит словарь. Терминальным узлам соответствуют фрагменты ''=>undef. На вершине этой иерархии находится особый узел (зелёный) — сам словарь.