marinol (marinol) wrote,
marinol
marinol

Category:

Палиндрогены

По просьбе 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
Tags: комбинаторная поэзия, палиндромы
Subscribe

  • ***

    Ежедневные Анаграммы (по наводке Александра Бубнова). шестого апреля согреет пошлая, огреет - пошла я с лешего, а я прост - отгорел спеша я, сгорел,…

  • ***

    Специальный выпуск журнала «Гвидеон», посвященный 30-летию Международной Академии Зауми. С моими анаграммами. http://gulliverus.ru/mariin-20.html

  • ***

    Анаграммы. оппозиция жидка - рёв, пиздёж и провокация! *** оппозиция! даёшь! кривда, и провокация да пиздёшь!

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 28 comments

  • ***

    Ежедневные Анаграммы (по наводке Александра Бубнова). шестого апреля согреет пошлая, огреет - пошла я с лешего, а я прост - отгорел спеша я, сгорел,…

  • ***

    Специальный выпуск журнала «Гвидеон», посвященный 30-летию Международной Академии Зауми. С моими анаграммами. http://gulliverus.ru/mariin-20.html

  • ***

    Анаграммы. оппозиция жидка - рёв, пиздёж и провокация! *** оппозиция! даёшь! кривда, и провокация да пиздёшь!