О палиндромах и их генерации
Оригинал взят у 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, ‘хвостик’ - у первого слова на конце есть палиндром-остаток (неслово), который ничему не соответствует во втором слове. Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но в начале второго слова.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять непалиндром. С точки зрения комбинирования именно палиндромов, то есть в плане 'разложимости' (как свойства деления палиндромов на палиндромы меньшей сложности) деление на 'хвостики' и 'носики' имеет небольшое значение. Поэтому пока я буду обозначать как w2 (w - строчное) все палиндромы из двух слова, которые не является палиндромами типа w1.w1. ВСЕ палиндромы из 2-х слов буду обозначать как W2 (w - заглавное).
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть либо 'челюстями' : w1.w2 или w2.w1, либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
Палиндромы из 4 слов (W4) могут быть 'челюстями' типов
w1.w3
w3.w1
w1(w1.w1)w1
w2.w2
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1(w1.w1)w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.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 миллионов палиндромов.
Следующий шаг - смысловая фильтрация полученных списков.
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево.
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево. Это определение вроде бы утверждает равенство-тождественность обоих направлений в палиндроме. Но это не совсем так. Возьмем один из самых известных палиндромов “А роза упала на лапу Азора”. Из него видно, что под ‘одинаковым прочтением’ имеется, только одинаковый порядок букв, не более того. Разбиение на слова, определенное в прямом порядке, при обратном прочтении меняется. Точнее берётся таким, каким оно было при прямом прочтении. Хотя конечно бывает, что они совпадают.
Пусть 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, ‘хвостик’ - у первого слова на конце есть палиндром-остаток (неслово), который ничему не соответствует во втором слове. Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но в начале второго слова.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять непалиндром. С точки зрения комбинирования именно палиндромов, то есть в плане 'разложимости' (как свойства деления палиндромов на палиндромы меньшей сложности) деление на 'хвостики' и 'носики' имеет небольшое значение. Поэтому пока я буду обозначать как w2 (w - строчное) все палиндромы из двух слова, которые не является палиндромами типа w1.w1. ВСЕ палиндромы из 2-х слов буду обозначать как W2 (w - заглавное).
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть либо 'челюстями' : w1.w2 или w2.w1, либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
Палиндромы из 4 слов (W4) могут быть 'челюстями' типов
w1.w3
w3.w1
w1(w1.w1)w1
w2.w2
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1(w1.w1)w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.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 миллионов палиндромов.
Следующий шаг - смысловая фильтрация полученных списков.