?

Log in

No account? Create an account

Previous Entry | Next Entry

Ранее я уже показывал, как задача поиска разнобуквиц сводится
к задаче ЦЛП - целочисленного линейного программирования.

http://marinol.livejournal.com/165386.html


Чем это хорошо? Тем, что для решения таких задач существуют
эффективные алгоритмы, реализованные в виде работающих, отлаженных
пакетов программ.
Те, кто считает, что это представляет чисто теоретический интерес,
могут познакомиться с программой "Комбинаторный Поэт".
В этой программе такой подход реализован практически и позволяет быстро
находить разнобуквицы необходимого качества.

Здесь же мы попробуем применить аналогичный подход к задаче
создания палиндромов. Можно ли свести проблему создания палиндромов
к линейной задаче, для которой, как я уже сказал, имеются эффективные
алгоритмы и отлаженные программы? Ответ на этот вопрос положительный.

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

Глупо утверждать, что этот подход заменит умение и искусство опытных
палиндромистов. Но, наверное, он сможет быть для них каким-то существенным
подспорьем.

Итак, пусть мы имеем словарь слов S[i],i=1:N, N-количество слов в словаре.
И хотим создать палиндром длиной в M букв. В текущем варианте модели я буду
фиксировать длину палиндрома. Идея заключается в том, что мы вводим
целочисленную переменную X[i,j], которая означает, что слово с индексом i,
начинается в палиндроме с (буквенной) позиции j, если эта переменная имеет значение 1.
И 0, если слово S[i] не входит в палиндром с позиции j.

Ясно, что если не вводить никаких ограничений на вхождение слова в палиндром,
то будет хаос - разные слова смогут начинаться (и продолжаться) с одной и той же
позиции. Для того, чтобы прекратить это безобразие мы вводим матрицу структурных
ограничений R[j,k], где j=1,M - индекс строки матрицы, k=1:M*N. Каждой строке
матрицы соответствует позиция палиндрома, поэтому их M. Каждому столбцу матрицы k
соответствует некая переменная X[i,j], поэтому количество столбцов
будет равно ~ N (кол-во слов)*M(кол-во позиций).
Столбец матрицы R формируется следующим образом. Начиная со строки индексом j
в столбце B будет поставлено столько единиц (1), какова длина слова. Во всех остальных
позициях нужно проставить 0. Если мы возьмём и умножим матрицу R на вектор X
то получим вектор B, размером M строк (длина палиндрома). Что он будет означать?
Он будет давать количество слов, чьи буквы находятся на каждой позиции палиндрома.
НО... в палиндроме (да и в любом другом ПРЕДЛОЖЕНИИ) на каждой позиции находится
буква от ОДНОГО слова. Поэтому, если мы имеем вектор B состоящим только из единиц (1),
то задав условие (линейное, это важно) R*X=B, мы гарантируем, что переменные будут
выбираться так, чтобы слова не пересекались, а образовывали одну линейную
последовательность.

Фу, уже легче. Но это не всё. Ведь нам нужен палиндром.
Чем характеризуется палиндром, тем, что на позиции L, L=1:M, находится
та же буква, что и на позиции M-L+1. Например, если L=1 (начало слова), то
такая же буква должна быть на позиции M-1+1 = M, то есть в конце слова.
И так далее со смещением к центру палиндрома.

Для того, что бы это формализовать, вводим матрицу W[j,k], j=1:M, k=1:M*N,
которая полностью аналогична матрице R, но... в ячейках матрицы находятся
не нули или единицы, а числа представляющие собой числовые КОДЫ соответствующих
букв каждого слова. Тогда если мы возьмём произведение матрицы W на вектор
переменную X, то получим вектор P, который ... в чистом виде даёт нам
последовательность слов (точнее букв), включённых в 'палиндром'. Для того,
что я смог убрать кавычки у слова палиндром в предыдущем предложении, мне
нужно лишь правильно задать 'палиндромные' ограничения. Как их задать ?
Очень просто:

P[L]=P[M-L+1], где L=1,M.

Как мы видим все ограничения, которые мы вводили
линейны, то есть для решения задачи вполне можно пользоваться пакетами
решения задач целочисленного линейного программирования.
В качестве критерия (а также дополнительных ограничений) можно задавать
различные выражения, (как в задаче о разнобуквицах). Например можно задать
ограничения, чтобы любое слово не входило более двух раз в палиндром.
Или чтобы в палиндроме было от 4 до 6 существительных. Или, чтобы в палиндроме
обязательно были заданные слова (неважно на каких позициях, или наоборот
в определённых).

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

Аналогичный подход может быть применён для генерации пантограмм.

Comments

( 20 comments — Leave a comment )
willich
Dec. 29th, 2013 09:37 pm (UTC)
Метод генерации палиндромов
хм, а есть ли у Вас крытерии кичества палиндрома или хотя бы просто правильного/неправильного предложения?
marinol
Dec. 29th, 2013 09:57 pm (UTC)
Re: Метод генерации палиндромов
С точки зрения практики я до сих пор только анаграммами
занимался. просто генерил варианты (анаграммный спектр) и отбирал (уже вручную) лучшие варианты.
Автоматическая оценка 'качества' текста (анаграммы, палиндрома, не важно чего) пока на очереди. Так что ответ такой: программы такой у меня нет. Делать строгую программу синтаксического разбора пока не в моих силах (хотя какие-то приближения я конечно буду делать). Да и что она даст - в комбинаторных текстах синтаксис
очень свободен. Конечно, близость к правильному синтаксису может
быть одним из параметров 'качества' (смысла) текста (палиндрома).

В настоящее время я в первую очередь хочу создать БД всех опубликованных палиндромных текстов (плюс всякий сервис типа проверки на правильность и уникальность) и программу интерактивного
помощника составителей палиндромов.

Дальше посмотрим.


Edited at 2013-12-29 09:58 pm (UTC)
willich
Dec. 30th, 2013 12:41 am (UTC)
Re: Метод генерации палиндромов
пынятно, конь еще - того!.. :))
согласно теореме Гёделя о неполноте - понять систему изнутри невозможно. Вы будете смеяться, но палиндромность для составления палиндрома не имеет никакого значения: это неубиваемая аксиома, условие, если хотите, все равно, что нитка крестиком - при вышивке крестиком, или верификация диагноза пневмонии - по рентгену, иначе это - просто не палиндром, вышивка не крестиком и недостоверная диагностика. палиндром - прежде всего правильная фраза, да, именно с правильным синтаксисом, без эклектики, м.б. афоризм, поговорка, поэтизм, худлит короче, а что?
готовы ли Вы к диалогу? для начала - неплохо было бы сузить словарь для палиндромов, ведь, согласитесь, есть слова, которые не палиндромируются: например, объем, подъем или водянистый, а оставшиеся все-таки маркировать по частям речи... а вообще было бы интересно найти все палиндромы типа "Аргентина манит негра!", "Деликатес - все-таки лед!", "Гни скобки, кикбоксинг!", "Мадмуазели - филе за ум дам!", возьметесь?
marinol
Dec. 30th, 2013 08:32 am (UTC)
Re: Метод генерации палиндромов
уж не знаю кто пытается понять палиндромы изнутри, и главное зачем и как это делать.
Палиндромность это для меня ограничение на текст, которое можно проверять, соблюдать, в том числе, частично, и при составлении палиндрома. Даже при проверке есть небольшие проблемки типа синхронизации текста после ошибки. Вот сейчас проверяю гигантскую матрёшку палиндром Гончарова из 20,000 букв. Но программа пока находит ошибки по одной, без синхронизации после нахождения неточности. Впрочем большинство палиндромов не такие большие и это не так страшно.
Проверка синтаксиса стоит только в плане на будущее (для оценки палиндромов и автоматической генерации), поскольку при интерактивном создании (ближайшие планы), автор будет сам это контролировать (наверное как и при полностью ручном создании).
Аналогично созданию анаграмм с помощью программы (правда здесь интерактивность не нужна в общем-то).
Словарь естественно нужно будет 'сужать'. Для генерации разнобуквиц, например, его пришлось сузить с 2.5 миллиона словоформ до ~350 тыс.
Найти все небольшие (2-6 слов) палиндромы определенной (синтаксической) структуры это можно, тупо перебором. Конечно сделаю. Правда у меня аналогичная программа для автоматической генерации анаграмм стала выдавать столько анаграмм (большинство было банальных), что пришлось её временно отложить, до создания удобной настройки допустимой синтаксической структуры. Поскольку даже из 4 слов можно много чего состряпать.
willich
Dec. 30th, 2013 11:23 am (UTC)
Найти все небольшие (2-6 слов) палиндромы
здорово! а алгоритм хотя бы засветить (обсудить) не хотите ли? :)
marinol
Dec. 30th, 2013 01:45 pm (UTC)
Re: Найти все небольшие (2-6 слов) палиндромы
Ну как Вы уже сказали, словарь нужно будет 'сузить',
оставив слова, которые содержать части, потенциально (в сумме с другими) читаемые
в обоих направления. Отдельно, выделив слова которые могут стоять
на концах. На первом этапе можно ограничиться
палиндромами где центр симметрии не проходит через слово
(в крайнем случае через слово-палиндром), то есть палиндромными парными текстами (вроде их ещё челюстями кличут).
Ну а дальше 'грубая сила', перебор с какими-то ещё разумными ограничениями - типа начальная часть палиндрома резко ограничивает возможное следующее слово, причём ограничение будет проистекать из возможностей как прямого так и обратного прочтений. Честно говоря,
я пока не думал детально. Наверняка какие-то мысли еще будут.
Постараюсь после Нового Года выложить какой-нибудь
продуманный вариант. Я думаю, это должен быть алгоритм, похожий на тот, что используется палиндромистами 'вручную'.
И программа просто 'перебирает' ВСЕ варианты, которые бы смог
предложить 'интерактивный' помощник на данном шаге сборки.

В принципе можно вообще не заморачиваться особо и устроить
полный перебор на суженном словаре. Если комп и язык потянет.
Пока я всё делаю на Perl. Но например для генерации полного списка разнобуквиц придётся переписывать на C/C++. Perl не тянет, хотя с анаграммами вполне справляется.

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

Edited at 2013-12-30 02:03 pm (UTC)
willich
Dec. 30th, 2013 08:00 pm (UTC)
конструировать словари
1. а как Вы вообще себе представляете палиндромный словарь? если такой, как у Е. Кацюбы - так это просто никакой: с ним работать невозможно, она даже где-то оправдывалась, что это "как бы словарь", просто форма текста такая.
2. есть ли для Вас понятие "палиндропары" или аверса-реверса, как хотите?
3. что есть концевые характеристики? означает ли это , что слово в словаре должно располагаться по алфавиту, как минимум, на 2 буквы: первую и последнюю согласные?
marinol
Dec. 30th, 2013 08:23 pm (UTC)
Re: конструировать словари
1. как только приступлю к конкретным шагам, я это озвучу.
2. палиндром с точки зрения логики и математики ОЧЕНЬ простой объект (если не добавлять к нему синтаксис и смысл, то есть оставить на стадии 'реверса'). Так что все понятия должны возникнуть у любого человека после некоторого знакомства, даже если он не знает как их назвали, те кто занимался этим до него. Тут самая главная проблема это понять как разные люди называют одинаковые вещи. У Бубнова есть например ПП - палиндромная пара, это то, что приходит в голову в первую же секунду знакомства с палиндромами. Все остальные 'понятия' реверса приходят в голову в следующие 30 секунд. Так что проблема только одна - при общении называть одинаковые вещи одинаковыми словами. Если у Вас уже есть список определений понятий, которыми Вы пользуетесь, то после моего знакомства с ним, мы смогли бы разговаривать на одном языке.
У меня, к сожалению, такого списка определений пока нет.
3. 'концевые характеристики' это моё пока смутное понятие о необходимости сопряжения слов. Уточнение будет когда я начну составлять алгоритм. Я ведь не говорил, что он у меня есть.
willich
Dec. 30th, 2013 08:51 pm (UTC)
Re: конструировать словари
2. сорри, я не о термине, не об определении, еб!, а о его наполнении: структурно РР м.б. разными, например КОТ - ТОК =полный реверс, а ВОТ ЧТО =т.наз. "мигалка", а ВОТ О ="конфетка", а ВОТ ЭТО ВО ="1:2" и т.д. вот Вам типы взаимодействия аверса и реверса. элементарно, Ватсон! :)
3. есть ли у Вас план, мистер Фикс? :) - Да, четыре мешка! :))
marinol
Jan. 3rd, 2014 05:15 pm (UTC)
Re: Метод генерации палиндромов
Насчёт описок в тех Ваших палиндромах, что я нашёл на Палиндромании.
Они типа вот таких:
"я тушу лапал с осла полушутя"
"яви дупу дуре херу дур удивя"
Я их в ЖЖ выкладывать не буду, так как текст объёмный.

Поэтому я вижу два варианта.

1. Вы захотите их поправить. Я высылаю Вам по email текст.
Вы правите, я включаю новые варианты.

2. Мы их просто игнорируем (их ~440 из 10.000).
willich
Dec. 30th, 2013 07:50 pm (UTC)
их ещё челюстями кличут
1. ну, "челюсти" - это мой термин :) Б. Гринберг его как раз не любит, хотя и составил, по моей, кстати, просьбе, хороший список таких слов общеупотребительной лексики, типа РОПОТ - ТОПОР, ЗАКОПАН - НАПОКАЗ и т.д. я его даже как-то по частям речи индексировал...
2. зная, что ты хочешь иметь на выходе - можно из этой индексированной БД попробовать составить настоящие палиндромы. но как показывает опыт - их будет раз-два и обчелся! дело в том, что кроме синтаксиса и семантики есть еще логика, короче, лексика должна быть из одной предметной области или онтологии, концепта, дискурса - как это индексировать? есть ли такие БД? а то по SVO будет правильное предложение, но совершенно не логичное и в результате - абсурдное!
3. в челюсти можно вставлять однословы, например: ТОПОР - ТОПОТ, РОПОТ! ЗАКОПАН БОБ НАПОКАЗ! я их называю - челюстно-лицевыми палиндромами, или концевой фрагмент - челюстью, а центральный - пробкой. по-моему неплохой полигон для старта: списки как челюстей, так и однословов - ограничены, индексацию SVO и онтологии тоже в обозримое время можно сделать вручную, далее прописать условия "сборки" палиндрома - "если... то..., иначе..." и т.д.
marinol
Dec. 30th, 2013 08:38 pm (UTC)
Re: их ещё челюстями кличут
Онтологии здесь использовать на мой взгляд преждевременно. Разве что как способ работы с синтаксисом. Для определения смысла они по-моему будут беспомощны пока. Поскольку палиндромы зачастую имеют 'нестандартный' смысл (то есть наверняка части будут из разных онтологий), и именно за это ценимы. То есть они сами и генерят новый 'смысл' (точнее голова интерпретирует). Кроме того, описывать онтологии чрезвычайно муторное дело.
Короче, всему своё время.

Я вижу, что Вы делали или пытались написать что-то для генерации палиндромов. На какой стадии всё это у Вас?
willich
Dec. 30th, 2013 09:01 pm (UTC)
Re: их ещё челюстями кличут
1. я вообще ни разу не программер, алгоритмы - пожалуй...
2. я тут не совсем понимаю тогда конечный смысл Вашей автоматизации: если Вы не хотите, чтобы на выходе получился правильный, осмысленный непротиворечивый палиндром (что есть определение), то что же Вы строите? ИМХО, начинать строить палиндром надо с конца! :)
3. или Вы хотите "утонуть" в статистике и получить что-то типа доказательной медицины на выходе?
marinol
Dec. 30th, 2013 09:14 pm (UTC)
Re: их ещё челюстями кличут
2. для начала, как я говорил, я хочу сделать БД палиндромов.
Это само по себе уже, судя по состоянию 'отрасли',
неплохой результат. Тем более цель добиться чтобы её мог вести
независимо от меня любой непрограммист.

Второе - это интерактивный помощник. И возможно генерация
малословных 'реверсов', в соответствии в том числе с синтаксическими
шаблонами (как простейшего варианта задания синтаксиса).
Отбор по смыслу я на данном этапе не планирую принципиально.
Потому, что как я говорил, по моему мнению, часто палиндромы
этот смысл и генерят. С другой стороны можно применять 'простейшие' варианты задания смысла. Но только когда всё остальное будет работать как часы.
marinol
Dec. 30th, 2013 09:16 pm (UTC)
Re: их ещё челюстями кличут
осмысленные тексты будет отбирать человек, так же как я это делаю сейчас с анаграммами. В любом случае, это лучше и продуктивнее чем делать всё ручками.
willich
Dec. 30th, 2013 10:03 pm (UTC)
осмысленные тексты будет отбирать человек
захлебнетесь пыль глотать! :) не хотите ручками - можно карандашами! :))
marinol
Dec. 30th, 2013 10:12 pm (UTC)
Re: осмысленные тексты будет отбирать человек
ну вообще-то что касается анаграмм, то не захлебнулся.
полианаграмм у меня на порядок больше чем у всех остальных
вместе взятых. палиндромами народ больше занимался, но
тем не менее захлёбываться я точно не буду ))
willich
Dec. 30th, 2013 10:00 pm (UTC)
Re: их ещё челюстями кличут
странно, какой такой "смысл и генерят" палиндромы? палиндромы - только попадают в смысл и это проявляется зачастую только на этапе расстановки знаков препинания, а еще чаще - при прочтении другим читателем, не автором! есть даже закон такой в палиндромии: "Палиндром - умнее автора!" смысл все-таки формируют семы (а это скорее - метафизика) и если палиндром абсурден, то это скорее повод считать его несостоявшимся! опять же - это к соглашению "что - на выходе?".
marinol
Dec. 30th, 2013 10:16 pm (UTC)
Re: их ещё челюстями кличут
"Палиндром - умнее автора!"

я своими словами, но сказал тоже самое - это и есть 'смысл генерят сами палиндромы'
willich
Jan. 10th, 2015 12:48 am (UTC)
Re: их ещё челюстями кличут
там ключевое слово - попадают в смысл, а не производят (генерят) его, и в этом фишка: получился/не получился палиндром, а что?
( 20 comments — Leave a comment )

Latest Month

November 2017
S M T W T F S
   1234
567891011
12131415161718
19202122232425
2627282930  
Powered by LiveJournal.com
Designed by Lilia Ahner