Палиндрогены
По просьбе willich занимался генерацией списка слов, которые могут,
в принципе, быть применены в тексте палиндрома. Такие слова я буду
назвать палиндрогенными или палиндрогенами.
Для того, чтобы построить список таких
слов нужно построить список ВСЕХ палиндромов и из них взять слова.
Для начала мы ограничимся одним шагом.
Определение палиндрогена (первого порядка):
PG = [b,s1,s2,...sN,e],
где s1-sN - реверсированные слова,
то есть rev(s1), rev(s2),... rev(sN) - являются
полными словами,
rev(e) = end(w1), то есть реверсированная строка e является
концом какого-то слова,
rev(b) = beg(w2), то есть реверсированная строка b является
началом какого-то слова.
Если b и e пустые, то
PG s1 s2 ... sN это палиндром типа (1,N).
Палиндрогенами так же будут все слова rev(s1), rev(s2),... rev(sN).
При дальнейшем 'расширении' вполне возможно палиндром не сложится.
Алгоритм поиска таких палиндрогенов (и заодно палидромов (1,N)) просто - рекурсия.
Начиная с конца слова, откусываем последовательно
все больший кусок, реверсируем его и проверяем,
представляет ли он собой полное слово.
Дополнительно, если это первый шаг, то является он концом какого либо слова.
Если это так, то берем остаток слова и вызываем ту же
самую процедуру с усеченным словом (рекурсия).
Если мы дошли до начала слова, то кроме проверки на полное слово,
реверсированный текст дополнительно проверяется на то, является ли
он началом какого-либо слова.
Для проверки на принадлежность словарю, и проверке на начало и конец слова,
предварительно строятся индексы ('map' на C++).
На словаре Зализняка (вариант Хагена) - более 4 миллионов словоформ,
программа работает около 8 минут.
Для обратной раскладки слова, то есть для [rev(e),rev(sN)...rev(s1),rev(b)]
строятся синтаксические ключи, по которым в дальнейшем или сразу можно
отфильтровывать бессмысленные варианты. То есть варианты, не соответствующие
частям правильных предложений, например, где идут подряд несколько предлогов
и т.д. В качестве синтаксического ключа строится строка кодов частей речи слов
раскладки палиндрогена, разделенных символом '_'
(без родов, чисел, падежей и т.д - хотя это можно легко добавить,
если кому понадобится, впрочем это каждый может сделать и сам).
После построения палиндрогенов первого порядка, можно процесс повторить,
но в качестве словаря для проверки на начало и конец слов использовать не
весь словарь, а только словарь палиндрогенов первого порядка.
Сделав несколько подобных циклов можно, наверное, хорошо приблизиться к словарю
'истинных' палиндрогенов:
Pg(N+1) = PalGen(Pg(N)), если Pg(N+1) = Pg(N) (неподвижная точка отображения PalGen), то это и есть множество палиндрогенов.
combiproc.exe - программа (требуются также DLL, которые есть в архиве-дистрибутиве).
hagen.txt - словарь Хагена (Зализняка), в моей кодировке.
palfilter.txt - файл синтаксических фильтров (в качестве фильтров
могут использоваться подстроки синтаксических ключей - примеры - palsyntax.txt).
(в дистрибутиве это файл приведен только для иллюстрации - каждому
нужно строить свой). Если файл отсутствует, то фильтрация не производится.
palgen.bat - командный файл запуска программы.
Просто разархивируем дистрибутив в любую директорию (делаем ее текущей)
и запускаем palgen.bat
Выходные файлы:
palwords.txt - палиндрогены с вариантами раскладки для каждого (около миллиона).
palindroms1N.txt - палиндромы типа (1,N), с указанием N и синтаксического ключа.
palsyntax.txt - все варианты синтаксических ключей,
с примерами палиндрогенов (можно смотреть и выбирать из них фильтры).
Архив с программой находится здесь.
https://drive.google.com/open?id=0Bx5i8aQxfrleZU5XZ0E4Q3g3X0E
в принципе, быть применены в тексте палиндрома. Такие слова я буду
назвать палиндрогенными или палиндрогенами.
Для того, чтобы построить список таких
слов нужно построить список ВСЕХ палиндромов и из них взять слова.
Для начала мы ограничимся одним шагом.
Определение палиндрогена (первого порядка):
PG = [b,s1,s2,...sN,e],
где s1-sN - реверсированные слова,
то есть rev(s1), rev(s2),... rev(sN) - являются
полными словами,
rev(e) = end(w1), то есть реверсированная строка e является
концом какого-то слова,
rev(b) = beg(w2), то есть реверсированная строка b является
началом какого-то слова.
Если b и e пустые, то
PG s1 s2 ... sN это палиндром типа (1,N).
Палиндрогенами так же будут все слова rev(s1), rev(s2),... rev(sN).
При дальнейшем 'расширении' вполне возможно палиндром не сложится.
Алгоритм поиска таких палиндрогенов (и заодно палидромов (1,N)) просто - рекурсия.
Начиная с конца слова, откусываем последовательно
все больший кусок, реверсируем его и проверяем,
представляет ли он собой полное слово.
Дополнительно, если это первый шаг, то является он концом какого либо слова.
Если это так, то берем остаток слова и вызываем ту же
самую процедуру с усеченным словом (рекурсия).
Если мы дошли до начала слова, то кроме проверки на полное слово,
реверсированный текст дополнительно проверяется на то, является ли
он началом какого-либо слова.
Для проверки на принадлежность словарю, и проверке на начало и конец слова,
предварительно строятся индексы ('map' на C++).
На словаре Зализняка (вариант Хагена) - более 4 миллионов словоформ,
программа работает около 8 минут.
Для обратной раскладки слова, то есть для [rev(e),rev(sN)...rev(s1),rev(b)]
строятся синтаксические ключи, по которым в дальнейшем или сразу можно
отфильтровывать бессмысленные варианты. То есть варианты, не соответствующие
частям правильных предложений, например, где идут подряд несколько предлогов
и т.д. В качестве синтаксического ключа строится строка кодов частей речи слов
раскладки палиндрогена, разделенных символом '_'
(без родов, чисел, падежей и т.д - хотя это можно легко добавить,
если кому понадобится, впрочем это каждый может сделать и сам).
После построения палиндрогенов первого порядка, можно процесс повторить,
но в качестве словаря для проверки на начало и конец слов использовать не
весь словарь, а только словарь палиндрогенов первого порядка.
Сделав несколько подобных циклов можно, наверное, хорошо приблизиться к словарю
'истинных' палиндрогенов:
Pg(N+1) = PalGen(Pg(N)), если Pg(N+1) = Pg(N) (неподвижная точка отображения PalGen), то это и есть множество палиндрогенов.
combiproc.exe - программа (требуются также DLL, которые есть в архиве-дистрибутиве).
hagen.txt - словарь Хагена (Зализняка), в моей кодировке.
palfilter.txt - файл синтаксических фильтров (в качестве фильтров
могут использоваться подстроки синтаксических ключей - примеры - palsyntax.txt).
(в дистрибутиве это файл приведен только для иллюстрации - каждому
нужно строить свой). Если файл отсутствует, то фильтрация не производится.
palgen.bat - командный файл запуска программы.
Просто разархивируем дистрибутив в любую директорию (делаем ее текущей)
и запускаем palgen.bat
Выходные файлы:
palwords.txt - палиндрогены с вариантами раскладки для каждого (около миллиона).
palindroms1N.txt - палиндромы типа (1,N), с указанием N и синтаксического ключа.
palsyntax.txt - все варианты синтаксических ключей,
с примерами палиндрогенов (можно смотреть и выбирать из них фильтры).
Архив с программой находится здесь.
https://drive.google.com/open?id=0Bx5i8aQxfrleZU5XZ0E4Q3g3X0E