О палиндромах и их генерации (отредактированный текст)
Оригинал взят у marinol в О палиндромах и их генерации
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево.
Это определение вроде бы утверждает равенство-тождественность обоих направлений в палиндроме. Но это не совсем так. Возьмем один из самых известных палиндромов “А роза упала на лапу Азора”. Из него видно, что под ‘одинаковым прочтением’ имеется, только одинаковый порядок букв, не более того. Разбиение на слова, определенное в прямом порядке, при обратном прочтении меняется. Точнее берётся таким, каким оно было при прямом прочтении. Хотя конечно бывает, что они совпадают.
Пусть Rev() это функция реверсирования текста, то есть перечисление букв текста в обратном порядке. А Rs() - это функция удаления пробелов (делящих текст на слова). Считаем, что знаки препинания в тексте палиндрома отсутствуют. Тогда формальное определение палиндрома можно записать как :
Т - палиндром, если Rev(Rs(T)) == Rs(T). В принципе ничего нового, только для определённости. Вместо функции удаления пробелов можно было бы использовать функцию конкатенации слов, на которые разбивается текст. В дальнейшем для описания алгоритмов может еще потребоваться функция Len(T) - длина текста T.
Разберемся в существующей классификации линейных (нециклических) палиндромов. При этом не рассматриваются отдельно 'оборотни', как особенная форма палиндрома, так как они прямо приводятся к обычной форме палиндрома. Мы рассматриваем только монопалиндромы, которые представляют собой один палиндром, в отличие от полипалиндромов, которые являются упорядоченным множеством монопалиндромов.
Используемая ниже система обозначения палиндромов необщепринятая, к тому же, скорее всего, неокончательная. Просто она для меня пока удобнее всего.
Простейший палиндром это слово, которое одинаково читается в обоих направлениях. В данном случае 'одинаково читается' это не фигура речи, а точное определение - нет пробелов, слово одно. По терминологии известного палиндромиста willich, это 'монада'. У автора докторской диссертации по палиндромам Бубнова Александра, это палиндром с признаком 'двоичности' равным 1 - п1. Я буду использовать похожее обозначение - w1 (w - word).
Следующими по сложности будут палиндромы из двух слов (‘дидромы’ в терминологии willich). Дидромы, или палиндромы типа W2. Это более сложные образования и из них можно выделять подтипы.
Пусть дидром состоит из слов A и B. Тогда если Len(A) = Len(B), то это палиндром типа
w1|w1 или ‘челюсть’ (в терминологии willich). Здесь цифрой обозначается, как и раньше, количество слов в соответствующей части палиндрома. Главной особенностью таких палиндромов является то, что они могут легко вкладываться в палиндромы из большего количества слов путем вложения друг в друга. В обозначении палиндрома w1|w1 символ точки '|' обозначает условный центр палиндрома, он находится между словами. В центр челюсти можно вставлять не только другую челюсть, но и вообще любой палиндром, например монаду. При этом образуется более длинный палиндром.
Если Len(A) > Len(B), то это, по терминологии willich, ‘хвостик’ - если у первого слова на конце есть остаток (неслово), который ничему не соответствует во втором слове и который будет палиндромом - тип w1.p|w1 Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но палиндром в начале второго слова - w1|p.w1. Здесь p - палиндромный остаток.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять соответствующий непалиндром. Willich указывает на такую возможность - действительно можно вставить непалиндром, но сделанный в точности из палиндрома, с помощью операции перемены слов палиндрома местами.
Таким образом, возникает еще одно свойство палиндромов - разложимость. Палиндром (напомню, речь идет только о монопалиндромах) называется 'разложимым', если он состоит из двух или более палиндромов. Для монопалиндромов, как легко видеть, существует только один способ комбинирования - вложение одного палиндрома в другой, как в матрёшке.
При этом челюсти можно вкладывать друг в друга как есть, а носики или хвостики можно вкладывать друг в друга, если равны между собой их палиндромные остатки, и слова в палиндроме нужно поменять местами.
Поскольку для челюстей остаток пустой, а слова можно менять местами, то фактически способ комбинирования (willich) один - вложить друг в друга два палиндрома (челюсть, носик, хвостик), соответствующие друг другу и поменять слова местами.
Все палиндромы типа W2 будут либо челюстями (w1|w1), либо 'носиками', либо 'хвостиками'.
w1.p|w1 - это 'хвостик'
w1|p.w1 - это 'носик'
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть
w1.p|w2
w1|p.w2,
w2.p|w1,
w2|p.w1,
либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
Палиндромы из 4 слов (W4) могут быть палиндромами типов
w1.p|w3
w1|p.w3
w3.p|w1
w3|p.w1
w1.p(Inv(w1.p|w1))w1
w1(Inv(w1|p.w1))p-w1
w2.p|w2
w2|p.w2
где p - либо пусто, либо палиндромный остаток,
Inv - операция замены порядка слов на обратный.
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1.p(Inv(w1.p|w1))w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.p|w1.
Можно было бы продолжать дальше (по количеству слов), но с точки зрения определения понятий, необходимых для описания сути палиндромов (без внутренней структуры), этого вполне достаточно.
Рассмотрим алгоритмы перечисления палиндромов.
w1 - простой цикл по всем словам словаря с проверкой каждого слова на палиндромность.
w1|w1
Предварительно строится индекс всех слов словаря. Потом делается один проход по словарю с проверкой на присутствие в индексе (очень быстрая операция) реверсированного слова.
w1|w2
Проход по словарю. Каждое слово реверсируется и делается попытка сегментации слова - цикл по длине слова. Сегментация удачная, если оба сегмента являются словами, то есть находятся по индексу слов словаря.
w1|w3
Проход по словарю. Каждое слово реверсируется и делается попытка сегментации слова - два вложенных цикла по длине слова. Сегментация удачная, если все три сегмента являются словами, то есть находятся по индексу слов словаря.
w2|w1
Проход по словарю. Если реверсированный текст находится в словаре, то делается попытка сегментирования начального слова (аналогично w1|w2).
w3|w1
Проход по словарю. Если реверсированный текст находится в словаре, то делается попытка сегментирования начального слова (аналогично w1|w3).
w2
Требует двух вложенных циклов по всем словам, но это несколько триллионов повторений внутренного цикла - вряд ли это допустимо по времени. С целью ограничения перебора в дополнение к прямому индексу стоится ограниченный (скажем тремя буквами) мультииндекс реверсированных слов.
И тогда для цикла по второму слову выбираются не все слова, а только те, которые присутствуют в мультииндексе с ключом равным реверсированным первым трем буквам первого (исходного) слова. Такой прием сильно ограничивает количество повторений второго цикла. И время генерации полного списка w2 получается равным приблизительно паре минут. Заодно при генерации исключаются варианты w1|w1, которые тоже будут встречаться в этом варианте алгоритма.
w2|w2
Начинаются более сложные варианты алгоритмов перечисления, хотя все еще простые и достаточно быстрые.
У нас есть палиндром из четырех слов: S1 S2 S3 S4.
Если Len(S1) == Len(S4), то мы имеем две челюсти w1|w1, вложенные друг в друга. Множество таких палиндромов можно сгенерировать взяв декартово произведение палиндромов типа w1|w1. Этого делать мы не будем, так как генерируем пока только неразложимые палиндромы.
Предположим что Len(S1) > Len(S4). Симметричный случай рассмотрим на следующем шаге.
Тогда S1 разбивается на две части S11 и S12 такие, что
Rev (S11) = S4
и
Rev(S2)+Rev(S12) = S3.
Перечисление будет реализовано в виде двух вложенных циклов. Первый цикл идет по словам S1, но мы берем не все слова. А только те слова, у которых какая-либо из начальных частей (их несколько - разной длины), будучи реверсирована, дает слово словаря (это свойство определяется как и прежде путем поиска по прямому индексу словаря). При этом реверс второй части слова (S12) является концом некоторого слова словаря. Построение множества слов, удовлетворяющих этим свойствам делается очень быстро с помощью предварительного построения полных мультииндексов начальных и конечных частей слов словаря.
Выбор второго слова ограничивается словами, которые будучи целиком реверсированы дают начало некоторого слова словаря - строится предварительно с помощью мульииндекса начал слов словаря.
Если Len(S1) < Len(S4). Тогда S4 разбивается на две части S41 и S42 такие, что
Rev (S42) = S1
и
Rev(S41)+Rev(S3) = S2.
Перечисление будет реализовано в виде двух вложенных циклов. Первый цикл идет по словам S4, но мы берем не все слова. А только те слова, у которых какая-либо из конечных частей (их несколько - разной длины), будучи реверсирована, дает слово словаря (это свойство определяется как и прежде путем поиска по прямому индексу словаря). При этом реверс начальной части слова (S41) является началом некоторого слова словаря. Построение множества слов, удовлетворяющих этим свойствам делается очень быстро с помощью предварительного построения полных мультииндексов начальных и конечных частей слов словаря.
Выбор второго слова (S3) ограничивается словами, которые будучи целиком реверсированы дают конец некоторого слова словаря - строится предварительно с помощью мульииндекса концов слов словаря.
Время работы программы на C++ на основе этого алгоритма (генерация w2|w2) со словарём Хагена объёмом около 4,300,000 словоформ ~ 45 минут. При этом генерируется около 29 миллионов палиндромов.
Следующий шаг - смысловая фильтрация полученных списков.
Текст был существенно исправлен после переписки-обсуждения с willich.
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево.
Это определение вроде бы утверждает равенство-тождественность обоих направлений в палиндроме. Но это не совсем так. Возьмем один из самых известных палиндромов “А роза упала на лапу Азора”. Из него видно, что под ‘одинаковым прочтением’ имеется, только одинаковый порядок букв, не более того. Разбиение на слова, определенное в прямом порядке, при обратном прочтении меняется. Точнее берётся таким, каким оно было при прямом прочтении. Хотя конечно бывает, что они совпадают.
Пусть Rev() это функция реверсирования текста, то есть перечисление букв текста в обратном порядке. А Rs() - это функция удаления пробелов (делящих текст на слова). Считаем, что знаки препинания в тексте палиндрома отсутствуют. Тогда формальное определение палиндрома можно записать как :
Т - палиндром, если Rev(Rs(T)) == Rs(T). В принципе ничего нового, только для определённости. Вместо функции удаления пробелов можно было бы использовать функцию конкатенации слов, на которые разбивается текст. В дальнейшем для описания алгоритмов может еще потребоваться функция Len(T) - длина текста T.
Разберемся в существующей классификации линейных (нециклических) палиндромов. При этом не рассматриваются отдельно 'оборотни', как особенная форма палиндрома, так как они прямо приводятся к обычной форме палиндрома. Мы рассматриваем только монопалиндромы, которые представляют собой один палиндром, в отличие от полипалиндромов, которые являются упорядоченным множеством монопалиндромов.
Используемая ниже система обозначения палиндромов необщепринятая, к тому же, скорее всего, неокончательная. Просто она для меня пока удобнее всего.
Простейший палиндром это слово, которое одинаково читается в обоих направлениях. В данном случае 'одинаково читается' это не фигура речи, а точное определение - нет пробелов, слово одно. По терминологии известного палиндромиста willich, это 'монада'. У автора докторской диссертации по палиндромам Бубнова Александра, это палиндром с признаком 'двоичности' равным 1 - п1. Я буду использовать похожее обозначение - w1 (w - word).
Следующими по сложности будут палиндромы из двух слов (‘дидромы’ в терминологии willich). Дидромы, или палиндромы типа W2. Это более сложные образования и из них можно выделять подтипы.
Пусть дидром состоит из слов A и B. Тогда если Len(A) = Len(B), то это палиндром типа
w1|w1 или ‘челюсть’ (в терминологии willich). Здесь цифрой обозначается, как и раньше, количество слов в соответствующей части палиндрома. Главной особенностью таких палиндромов является то, что они могут легко вкладываться в палиндромы из большего количества слов путем вложения друг в друга. В обозначении палиндрома w1|w1 символ точки '|' обозначает условный центр палиндрома, он находится между словами. В центр челюсти можно вставлять не только другую челюсть, но и вообще любой палиндром, например монаду. При этом образуется более длинный палиндром.
Если Len(A) > Len(B), то это, по терминологии willich, ‘хвостик’ - если у первого слова на конце есть остаток (неслово), который ничему не соответствует во втором слове и который будет палиндромом - тип w1.p|w1 Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но палиндром в начале второго слова - w1|p.w1. Здесь p - палиндромный остаток.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять соответствующий непалиндром. Willich указывает на такую возможность - действительно можно вставить непалиндром, но сделанный в точности из палиндрома, с помощью операции перемены слов палиндрома местами.
Таким образом, возникает еще одно свойство палиндромов - разложимость. Палиндром (напомню, речь идет только о монопалиндромах) называется 'разложимым', если он состоит из двух или более палиндромов. Для монопалиндромов, как легко видеть, существует только один способ комбинирования - вложение одного палиндрома в другой, как в матрёшке.
При этом челюсти можно вкладывать друг в друга как есть, а носики или хвостики можно вкладывать друг в друга, если равны между собой их палиндромные остатки, и слова в палиндроме нужно поменять местами.
Поскольку для челюстей остаток пустой, а слова можно менять местами, то фактически способ комбинирования (willich) один - вложить друг в друга два палиндрома (челюсть, носик, хвостик), соответствующие друг другу и поменять слова местами.
Все палиндромы типа W2 будут либо челюстями (w1|w1), либо 'носиками', либо 'хвостиками'.
w1.p|w1 - это 'хвостик'
w1|p.w1 - это 'носик'
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть
w1.p|w2
w1|p.w2,
w2.p|w1,
w2|p.w1,
либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
Палиндромы из 4 слов (W4) могут быть палиндромами типов
w1.p|w3
w1|p.w3
w3.p|w1
w3|p.w1
w1.p(Inv(w1.p|w1))w1
w1(Inv(w1|p.w1))p-w1
w2.p|w2
w2|p.w2
где p - либо пусто, либо палиндромный остаток,
Inv - операция замены порядка слов на обратный.
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1.p(Inv(w1.p|w1))w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.p|w1.
Можно было бы продолжать дальше (по количеству слов), но с точки зрения определения понятий, необходимых для описания сути палиндромов (без внутренней структуры), этого вполне достаточно.
Рассмотрим алгоритмы перечисления палиндромов.
w1 - простой цикл по всем словам словаря с проверкой каждого слова на палиндромность.
w1|w1
Предварительно строится индекс всех слов словаря. Потом делается один проход по словарю с проверкой на присутствие в индексе (очень быстрая операция) реверсированного слова.
w1|w2
Проход по словарю. Каждое слово реверсируется и делается попытка сегментации слова - цикл по длине слова. Сегментация удачная, если оба сегмента являются словами, то есть находятся по индексу слов словаря.
w1|w3
Проход по словарю. Каждое слово реверсируется и делается попытка сегментации слова - два вложенных цикла по длине слова. Сегментация удачная, если все три сегмента являются словами, то есть находятся по индексу слов словаря.
w2|w1
Проход по словарю. Если реверсированный текст находится в словаре, то делается попытка сегментирования начального слова (аналогично w1|w2).
w3|w1
Проход по словарю. Если реверсированный текст находится в словаре, то делается попытка сегментирования начального слова (аналогично w1|w3).
w2
Требует двух вложенных циклов по всем словам, но это несколько триллионов повторений внутренного цикла - вряд ли это допустимо по времени. С целью ограничения перебора в дополнение к прямому индексу стоится ограниченный (скажем тремя буквами) мультииндекс реверсированных слов.
И тогда для цикла по второму слову выбираются не все слова, а только те, которые присутствуют в мультииндексе с ключом равным реверсированным первым трем буквам первого (исходного) слова. Такой прием сильно ограничивает количество повторений второго цикла. И время генерации полного списка w2 получается равным приблизительно паре минут. Заодно при генерации исключаются варианты w1|w1, которые тоже будут встречаться в этом варианте алгоритма.
w2|w2
Начинаются более сложные варианты алгоритмов перечисления, хотя все еще простые и достаточно быстрые.
У нас есть палиндром из четырех слов: S1 S2 S3 S4.
Если Len(S1) == Len(S4), то мы имеем две челюсти w1|w1, вложенные друг в друга. Множество таких палиндромов можно сгенерировать взяв декартово произведение палиндромов типа w1|w1. Этого делать мы не будем, так как генерируем пока только неразложимые палиндромы.
Предположим что Len(S1) > Len(S4). Симметричный случай рассмотрим на следующем шаге.
Тогда S1 разбивается на две части S11 и S12 такие, что
Rev (S11) = S4
и
Rev(S2)+Rev(S12) = S3.
Перечисление будет реализовано в виде двух вложенных циклов. Первый цикл идет по словам S1, но мы берем не все слова. А только те слова, у которых какая-либо из начальных частей (их несколько - разной длины), будучи реверсирована, дает слово словаря (это свойство определяется как и прежде путем поиска по прямому индексу словаря). При этом реверс второй части слова (S12) является концом некоторого слова словаря. Построение множества слов, удовлетворяющих этим свойствам делается очень быстро с помощью предварительного построения полных мультииндексов начальных и конечных частей слов словаря.
Выбор второго слова ограничивается словами, которые будучи целиком реверсированы дают начало некоторого слова словаря - строится предварительно с помощью мульииндекса начал слов словаря.
Если Len(S1) < Len(S4). Тогда S4 разбивается на две части S41 и S42 такие, что
Rev (S42) = S1
и
Rev(S41)+Rev(S3) = S2.
Перечисление будет реализовано в виде двух вложенных циклов. Первый цикл идет по словам S4, но мы берем не все слова. А только те слова, у которых какая-либо из конечных частей (их несколько - разной длины), будучи реверсирована, дает слово словаря (это свойство определяется как и прежде путем поиска по прямому индексу словаря). При этом реверс начальной части слова (S41) является началом некоторого слова словаря. Построение множества слов, удовлетворяющих этим свойствам делается очень быстро с помощью предварительного построения полных мультииндексов начальных и конечных частей слов словаря.
Выбор второго слова (S3) ограничивается словами, которые будучи целиком реверсированы дают конец некоторого слова словаря - строится предварительно с помощью мульииндекса концов слов словаря.
Время работы программы на C++ на основе этого алгоритма (генерация w2|w2) со словарём Хагена объёмом около 4,300,000 словоформ ~ 45 минут. При этом генерируется около 29 миллионов палиндромов.
Следующий шаг - смысловая фильтрация полученных списков.
Текст был существенно исправлен после переписки-обсуждения с willich.