Category: it

Category was added automatically. Read all entries about "it".

Список программ и файлов для словесной комбинаторики

Здесь (далее) находится список (пополняемый) полезных программ и файлов данных,
написанных и созданных автором в помощь любителям комбинаторной поэзии,
точнее, словесной комбинаторики.

Приложение для поиска палиндромов в базе данных на смартфоне (планшете) под Android:
https://marinol.livejournal.com/1216997.html

Все авторские анаграммы Рунета одной страницей: https://sites.google.com/view/anagramm/home

Архив комбинаторной литературы: https://drive.google.com/drive/folders/1pNLuI5PzzvBQQjfeuHu5Cio6w134Sw2D?usp=sharing
Зеркало:
https://yadi.sk/d/Dc1-jF4UnWoK_Q

Все (почти) омограммы Рунета (более 17100) по авторам (62), собранные на одной странице (~2.2 мб).
https://sites.google.com/view/omogramm/home
Все (почти) слоговые анаграммы Рунета одной страницей (более 440).
https://sites.google.com/view/sloganagramm/home
Все (почти) слоговые палиндромы Рунета одной страницей (более 1400).
https://sites.google.com/view/slogpalindrom/home
Все разнобуквицы одной страницей Рунета (981).

Анимация анаграмм: https://marinol.livejournal.com/1027746.html
Порядкограммы: https://marinol.livejournal.com/1026724.html

Статья "Конструирование анаграмм": https://drive.google.com/file/d/17_Dc-E_xi7dYzBQbY3hGwPIX2moaChWA/view?usp=sharing

Новая книга анаграмм.

Онлайн база данных анаграмм.
Онлайн база данных равнобуквиц (пантограмм).
Онлайн база данных палиндромов.
Онлайн база данных разнобуквиц.
Онлайн база данных слоговых палиндромов.
Онлайн база данных слоговых анаграмм.
Слоговые анаграммы (простые). (сгенерировано программой)
Слоговые палиндромы в одно слово. (сгенерировано программой)
Слова анаграммы (сгенерировано программой по словарю Зализняка)

Списки слов для начально-концевых тавтограмм: http://www.olegmarin.ru/tavtend/

О длине анаграмм.
http://marinol.livejournal.com/861155.html

Палиндрогены
http://marinol.livejournal.com/791756.html

Новая папка для комбинаторных файлов:
http://marinol.livejournal.com/492012.html

Выложил базу данных палиндромистов и палиндромов.
http://marinol.livejournal.com/276744.html

Новая (диалоговая) версия комбинаторных программ:
http://marinol.livejournal.com/165386.html

Компьютерная палиндромная антология:
http://marinol.livejournal.com/197021.html

Список палиндромистов:
http://marinol.livejournal.com/225541.html

Метод генерации палиндромов с помощью решения задачи ЦЛП:
http://marinol.livejournal.com/196763.html

Способ создания рифмованных анаграмм
http://marinol.livejournal.com/305170.html

Collapse )

***

Обновил Базу Данных анаграмм - всего 15900 текстов от 88 авторов (своих - около 12400). Ссылка на БД в головном посте.

Обновил Базу Данных Палиндромов. Теперь в ней более 90 тысяч текстов от 360 авторов- около
65 тысяч монопалиндромов и остальное - несамостоятельные части полипалиндромов. Ссылка на БД имеется в моём ЖЖ marinol. Рекордсмен по количеству текстов в БД - willich - около 19000 палиндромов.

Обновил Базу Данных омограмм. 16300 текстов от 62 авторов. Ссылка на БД в ЖЖ marinol.

АНАГРИФЫ

Анагриф – это текст, составленный из набора букв, входящих в заданное слово. Вместо слова можно задать и просто произвольный набор букв (каждой по одной). Можно рассмотреть полный анагриф – множество ВСЕХ слов, составленных из данного набора букв. Количество элементов (слов) этого множества – это его мощность. Интересной задачей, по моему мнению, будет определение набора из N разных букв, который даёт полный анагриф максимальной мощности, то есть, дающий максимальное количество слов. Полный анагриф слова ‘мост’ содержит 25 слов. Полный анагриф слова 'свет' – 26 слов, слова 'дом' – 6 слов. А вот, интересно, какой набор из 4-х букв даст максимальное количество слов, которые состоят только из этих букв?

Для решения это задачи предлагается следующая модель целочисленного линейного программирования.
Имеется словарь, состоящий из слов S[i], i=1…N, где N – количество слов в словаре.
Для каждого слова введём бинарную переменную X[i], которая равна 1, если слово входит во множество F (полный анагриф) и 0, если не входит. Для каждого слова S[i] имеется вектор букв, которые входят в это слово: A[j,i] = 1, если буква с номером j входит в слово S[i], и 0 – в противном случае. Эти вектора составляют матрицу A. Если мы умножим матрицу A на вектор X, то получим вектор В, размером в 33 числа (по числу букв алфавита), который показывает - сколько в словах множества F содержится вхождений каждой буквы. Зададим на него условие, что
B <= R*M, где M – число (слов в словаре), а R – бинарный вектор. R[i] = 0 или 1. И добавим условие на него – сумма его компонент равна L (3,4,5,6...). Что это означает? Если R[i] = 0, то соответствующая ему буква (i – её порядковый номер) не будет входить в слова множества F – согласно неравенству. А если равна 1, то буква как может входить, так может и не входить в слова множества F. Тогда сумма компонент вектора R – это точное число (разных) букв, которые содержатся в словах множества F.
Теперь добавим критерий – будет максимизировать число слов во множестве F. Для этого просто возьмём сумму компонент вектора X и устремим её к максимуму.

Что получается. Мы имеем задачу линейного целочисленного программирования, которая хорошо исследована и имеет отличные пакеты оптимизации для решения (CPLEX, GUROBU, на худой конец - LPSOLVE). Аналогичный подход я применял для нахождения разнобуквиц и он отлично работает (с бесплатным LPSOLVE). В ближайшее время я постараюсь провести численные расчёты и ответить на вопросы –
Какие наборы и 3,4,5,6,7… букв дают возможность составить максимальное количество слов, то есть получить анагриф максимальной мощности. Их (эти анагрифы) наверное можно использовать для составления неплохих рассказов. Так же как буква 'П', на которую начинается максимальное количество слов, часто используется в тавтограммах.

РаЗнобуквицы

Навигационная система по раЗнобуквицам:
http://www.olegmarin.ru/raznobase/

новые разнобуквицы (составлены программой):
кот, хряпнешь - блюй, жгуч, в зады эф-съёмщиц!
котяра! НЭП! - вздыбь, жгуч, шлюх фей-съёмщиц!

Из старых материалов.

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

Для каждого такова слова вводится булева переменная, то есть целочисленная переменная, принимающая значения 0 или 1. Единица означает, что данное слово входит в разнобуквицу, ноль – не входит. Для каждой из букв алфавита линейной суммой по всем словам определяется сумма использованных в комбинации букв. В случае разнобуквицы для каждой буквы такая сумма должна давать ровно 1. То есть задача ЦЛП имеет около 347 тысяч переменных и 33 (по числу букв) ограничения. В качестве критерия можно задавать, например, минимум слов, или максимум глаголов и т.д.

Можно также задавать дополнительные ограничения на количества слов, существительных, глаголов и прилагательных (задавать роды, числа, падежи), выискивая нужную синтаксическую схему. Можно 'достраивать' разнобуквицу, задавая её начало. Так были построены разнобуквицы со словами 'коты', 'котяра'.

Для решения задачи ЦЛП применяется open source пакет LP_SOLVE. Типичное время поиска - минута, или несколько минут, если заданы исключения.

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

Комбинаторные базы данных в формате Google Fusion Tables.

Выложил базы данных в удобном для просмотра и поиска формате:

Онлайн база данных анаграмм.
Онлайн база данных палиндромов.
Онлайн база данных разнобуквиц.
Онлайн база данных слоговых палиндромов.

Легко искать и фильтровать по авторам, по словам, которые содержатся в текстах и т.д.

База данных слоговых палиндромов

База данных слоговых палиндромов в виде Excel таблицы:
https://drive.google.com/folderview?id=0Bx5i8aQxfrlefkgxYkVUT3BtWWtfcnhxRmRyRzY5ZV9WdFZ5aG9rRnNMcnAtVVpNVl8zT2s&usp=sharing
ну и, конечно, там же мои первоначальные опыты в этой области.

авторы слоговых палиндромов:
Адрианов Роман
Бубнов Александр
Гринберг Борис и еще
Лукомников Герман
Марьин Олег
Нагорских Павел
Овчинников Пётр
Силиванов Валерий
Федин Сергей
Филимоненков Виктор
Чирказов Дмитрий
Чудасов Иван
PS. В случае отсутствия личных страниц с палиндромами приводятся страниы, где палиндромы цитируются.

Выложил базу данных палиндромистов и палиндромов.

Выложил новую версию программы "Комбинаторный Поэт".

https://sites.google.com/site/mnogoanagramm/home/7-fajly

Она включает в себя базу данных палиндромов.
Около 300 авторов и около 56 тысяч палиндромов.
Имеется возможность поиска по авторам и ключевым словам.
Списки тавтопалиндромов и суперпалиндромов.
Есть функция анализа палиндрома, разложения, поиска
автора (авторов).

Также расширены возможности поиска слов в словаре.
Можно использовать функции
is_pal() - слово палиндром
is_pan() - разнобуквица
is_anag() - анаграмма
is_meta() - метаграмма
а также строковые функции: длина строки, подстрока и другие.

Добавлена возможность поиска анаграмм на английском языке.
Можно также добавить свой (любой, но один) язык, как дополнительный язык.

Компьютерная палиндромная антология

Заканчиваю первую версию компьютерной палиндромной антологии.
Она будет оформлена как часть моей freeware программы "Комбинаторный Поэт"

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

Все палиндромы, включённые в базу данных палиндромов, будут выверены.
В настоящее время проверено и зафиксировано около 100 авторов и 10,000 палиндромов.

О целях именно БД палиндромов.

1. Список ВСЕХ палиндромов, опубликованных, по авторам.
Это именно БАЗА, всего остального. Периодически пополняемая и поэтому
наиболее up to date.

2. Выверка всех палиндромов. Как выясняется процент неточностей 1-2%

3. Возможность проверки новых текстов на палиндромность и на
уникальность (чтобы не изобретали 'велосипеды' или хотя бы были в курсе
того)

4. Вычисление различных статистических параметров (коэффициент Бубнова и
др.) Можно, например, для полипалиндромов определять степень их уникальности
(процент уникальных строк). Некоторые монопалиндромы разлагаются как матрешки
- можно вычислять степень разложимости (чем выше, тем 'легче' палиндром - тем он
'ближе' по трудности сочинения к полипалиндрому).
Можно например совершенно точно найти неразложимый монопалиндром
максимальной длины (среди существующих, опубликованных).
Ну и многое, многое другое. Например, пытаться вычислять степень
осмысленности палиндромов
(используя степень согласованности синтаксиса и словарь пар слов
concordance и/или другие подходы)

5. Готовый исходный материал для исследователей палиндромов.

Для того, чтобы 'шедевры' не потерялись их можно пометить признаком и
показывать отдельно.
Более того, вообще списки палиндромов можно организовывать в виде
отдельных сборников (при желании), аналогично печатным изданиям.
Ну и конечно можно будет сортировать и показывать их по формальным
признакам: первой букве, слову, размеру. коэффициенту Бубнова, другим
коэффициентам.
Можно будет например найти все палиндромы с участием заданного слова
(словоформы или вообще леммы)

Как побочный эффект, например, не составляет труда получить
(бессмысленный), но рекордный (по длине) палиндром используя
перевертни-оборотни как части гигантской матрешки.
Чтобы не выглядеть хило на фоне всяческих английских и польских
рекордных бессмыслиц.

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

В случае успеха я добавлю аналогичную базу данных по анаграммам,
пантограммам.

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

Многие авторы дали явное согласие на публикацию
своих палиндромов в Антологии (Гринберг Борис, Иван Чудасов, Владимир Волынец,
Гончаров Владимир, Валерий Назаров, Елена Павлова и др.).
Буду пытаться испрашивать у всех, с кем удалось законтактировать.

Метод генерации палиндромов с помощью решения задачи ЦЛП

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

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 существительных. Или, чтобы в палиндроме
обязательно были заданные слова (неважно на каких позициях, или наоборот
в определённых).

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

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