ZaMaZaN4iK 29 янв 2016 в 18:23

Алгоритмы для поиска палиндромов

13 мин

163K

Алгоритмы*Программирование*

Из песочницы

Recovery Mode

+39

Комментарии 26

savostin 29 янв 2016 в 21:23

Еще бы алгоритм составления осмысленных палиндромов ;)

ZaMaZaN4iK 29 янв 2016 в 21:35

эххх, хотя бы для начала просто осмысленность научиться программировать :)

savostin 29 янв 2016 в 21:36

Ну, не скажите. Со словарем, имхо, не такая уж сложная задача…

ZaMaZaN4iK 29 янв 2016 в 22:13

может я не совсем понял, что Вы понимаете под «составлением осмысленного палиндрома»? я задачу понял, как генерацию палиндрома-предложения аля «А роза упала на лапу Азора». То есть у нас есть словарь, и мы должны из слов составить предложение, которое является палиндромом. Какие тут трудности могут возникнуть (первое, что приходит в голову):
0) Осмысленность. Просто рандомные слова мы подставлять не можем. Смысла скорее всего не будет, а чекера на «осмысленность» я придумать что-то не могу. В языке есть порядок слов. Но даже если соблюдать порядок, то не все слова сочетаются друг с другом.

Попробуем решить данную проблему. У нас есть пулл слов. Соединим их связями, какие слова с какими могут быть связаны. (пример слова «бить» и «воздух» связаны не будут(что-то не могу я их связать в голове), а вот «бить» и «баклуши» связаны) Можно также ввести вес связи — чем тяжелее, тем лучше подходит слово одно к другому. Можно попробовать ввести показатель, где лучше слову стоять от связанного с ним: слева или справа. Можно много чего ещё…

Но это сложно всё. Да и как соптимизировать это по скорости, я не представляю пока. Может из слов какой граф построить… Не знаю, не знаю.

Griffonn 29 янв 2016 в 23:35

Насчёт весов — обработать какой-нибудь крупный корпус и дать веса парам/тройкам/«n-грамма»-like наборам слов, в духе «что за чем часто идёт». Это, конечно, не покроет все варианты порядка слов в языке, и при генерации палиндромов будут простые самые популярные варианты. Примерно так, судя по всему, работает например Свифткей и другие дополняющие клавиатуры.

ZaMaZaN4iK 29 янв 2016 в 23:51

да, с таким способом я знаком. Может у Вас есть какие идеи по поводу генерации палиндромных строк? Потому что в моём представлении всё это будет работать ужасно медленно.

Griffonn 30 янв 2016 в 00:02

Пока что всё, что приходит в голову с ходу — ужасно медленное :) Для начала — каждое слово развернуть и посмотреть, есть ли в словаре оно развернутое или любая его подстрока (не одна буква конечно, и видимо даже не две, а например с трёх), и — что более проблематично по времени — пересечь все подстроки со всеми словами в словаре и запомнить, с какими словами его можно совмещать в смысле симметрии вокруг центра палиндрома, и что еще более проблематично — с каким набором слов (например, "<что-то, заканчивающееся на -н> упала" — «на лапу»). Радует только, что это всё одноразовый препроцессинг, и вот потом уже из получившейся базы искать популярные словосочетания, начиная с рандомного слова.

ZaMaZaN4iK 30 янв 2016 в 00:10

Это всё ужасно затратно по препроцессингу. и памяти нужно много. и мои подсчёты мне подсказывают, что время на препроцессинг и ресурсов уйдёт уйма :)

greybax 30 янв 2016 в 04:47

Сам недавно реализовывал подобное. Ожидал увидеть тут решение с инвертированием строки и сравнением ее с исходной. Кажется, что это самый простой и очевидный способ.

VEG 30 янв 2016 в 11:04

Здесь решается другая задача — поиск подстрок, которые являются палиндромами. Вы скорее всего просто проверяли, является ли входная строка палиндромом. Очевидное решение вашей задачи — это пробежаться циклом до середины строки, сравнивая первый символ с последним, второй символ с предпоследним и т.д. То решение, что предложили вы, потребует выделения лишней памяти на перевёрнутую версию строки, время на «переворачивание» строки при копировании одной строки в другую, время на последующее сравнение двух строк и освобождение памяти, занимаемой временной строкой. Уж не знаю, как вы решили, что это всё проще одного коротенького цикла.

Areso 30 янв 2016 в 12:28

https://github.com/Areso/Palindrome-searcher/blob/master/unit1.pas вот такая была у меня реализация вашей идеи. Хотя соглашусь с VEG, его вариант выглядит изящнее в плане расхода ресурсов.

SemenovVV 30 янв 2016 в 16:00

Мне кажется что задекларированная в статье цель:

Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке

немного не соответствует тексту и обсуждению, т.к. мы получаем множество палиндромов и выводим их количество. В текстах на Си ( я язык Си не знаю ) результатом является cntPalindromes — количество палиндромов в строке. Для расчета количества палиндромов это избыточно.
Если нужно просто подсчитать количество палиндромов в строке, достаточно простейшего цикла по строке, с раздельным подсчетом количества четных и нечетных.
четные добавляются, когда следующий символ = текущему символу
нечетные добавляются, когда следующий символ = предыдущему символу
+
Если анализируется естественный текст, например >А роза упала на лапу Азора<
надо игнорировать пробелы и знаки препинания

ZaMaZaN4iK 30 янв 2016 в 17:49

Эмм, что-то я не совсем понял, как работает Ваш алгоритм. Можете подробнее? :) просто если я правильно понял, то Вы имеете в виду алгоритм под номером 1). Он работает за N^2. Есть алгоритмы быстрее(тот же Манакер, что есть в статье). Или мы говорим о разных вещах?

SemenovVV 1 фев 2016 в 10:05

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

// paliandr project main.go
package main
import (
	"fmt"
)
func main() {
	//	slowo := "banan"
	slowo := "arozaupalanalapyazora"
	slowo = "banan"
	var count_chet, count_nechet int
	for ii := 0; ii < len(slowo); ii++ {
		if ii+1 < len(slowo) {
			if slowo[ii] == slowo[ii+1] {
				count_chet++
			}
			if ii > 0 {
				if slowo[ii-1] == slowo[ii+1] {
					count_nechet++
				}
			}
		}
	}
	fmt.Println(count_chet, count_nechet)
}

ZaMaZaN4iK 1 фев 2016 в 13:39

Вы конечно извините, но Ваш алгоритм неверен, и я Вам это сейчас продемонстрирую. Ваш алгоритм на строке «abacabakar» выводит, что в строке всегго 4 палиндрома, но на самом деле их там 6 (шесть). По крайней мере как минимум столько я их там сходу насчитал. Ваш код на Go я не запускал, запускал вот это (абсолютно идентичный код на C\C++, приведён ниже):

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s = "abacabakar";
    int chet_count = 0, nechet_count = 0;
    for(int i = 0;i < s.length(); ++i)
    {
        if(i + 1 < s.length())
        {
            if(s[i] == s[i+1])
            {
                chet_count++;
            }
            if(i > 0)
            {
                if(s[i-1] == s[i+1])
                {
                    nechet_count++;
                }
            }
        }
    }
    cout << chet_count + nechet_count;
    return 0;
}

Или я что-то протестировал не так? Естессно, палиндромы длины 1 мы не учитываем.

SemenovVV 1 фев 2016 в 14:20

просто вы в строке «abacaba» находите 3 палиндрома aca bacab abacaba
а я один, маленькие порождение, часть большого. Для анализа данных, с моей точки зрения, наибольший интерес представляют наиболее длинные цепочки

ZaMaZaN4iK 1 фев 2016 в 14:27

Э, не, не лукавьте :) Это с Вашей точки зрения. Есть чёткая задача — найти количество палиндромов в строке. (Да, я внёс некоторые слабинки в коде: работаю не с Юникодом, не удаляю пробелы и иные знаки препинания. Но это всё не сказывается на асимптотической сложности алгоритмов. А просто добавляет чуточку времени на препроцессинг строки.)

Вернемся к нашему заданию. Даже не количество различных палиндромов, а просто их общее количество. Чёткое задание, которое решается алгоритмами, приведёнными в статье. Если Вы знаете другие алгоритмы — я с превеликой радостью выслушаю, постараюсь их понять, напишу код на C\C++, выложу на Github и обновлю статью, также оставлю ссылку на Ваше решение.

Вы же решаете какой-то частный случай. Если Ваш алгоритм чуточку модифицировать, чтобы он находил все палиндромы, а не только «наиболее длинные цепочки», то он как раз и выродится в алгоритм за O(N^2). С чем Вы, надесю, согласны :)

SemenovVV 1 фев 2016 в 15:16

Я не лукавлю, но я, например, считаю что текст «А роза упала на лапу Азора» это один палиндром, а не несколько.

ZaMaZaN4iK 1 фев 2016 в 15:36

Так, ещё раз о постановке задачи в данной статье. Я процитирую себя: "… об алгоритмах подсчёта количества палиндромов в строке". Тут нет слов «всех», «общего количества» или каких-то синонимов к ним. Возможно, это моё упущение, что я явно не указал это. Но лично для меня является вполне логичным предполагать, что если я сказал «подсчёта количества палиндромов», то имеется в виду именно всех палиндромов, а не каких-то там сферических в вакууме «наиболее длинных цепочек». Хочу заметить, что далее, в начале статьи, я указал, что не рассматриваю буквы-палиндромы (просто добавлять длину строки к ответу), и, как я уже писал выше, не убираю со строки всякий мусор.

Далее, ещё раз о "… об алгоритмах подсчёта количества палиндромов в строке". Как видите, «в строке». Это значит что, если мне на вход сразу дадут палиндром, мне в ответ единицу выводить?:) А в чём же тогда интерес данной статьи? :)

Ещё раз повторяю: Ваш алгоритм решает частную задачу, которая не рассматривается в данной статье. Да, алгоритм интересен, но это всё частности. Я же рассматриваю общий случай, и для этого общего случая есть алгоритм, который решает эту же задачу, что и Ваш — алгоритм Манакера. Ваш же алгоритм является некоторой его интерпретацией под частный случай. А рассмотреть все частные случаи я, к моему глубокому сожалению, не в силах, так как мало ли, у кого-то будет задача на работе «посчитать количсетво палиндромов с тремя буквами 'ё' на нечётных местах относительно центра исходной строки, смещенной на два индекса влево» :)

SemenovVV 1 фев 2016 в 16:12

Прошу не путать все в кучу.

Алгоритм Манакера позволяет за линейное время найти в строке самый длинный палиндром ...

.
(это я цитирую Вики и пр.).
Целью же вашей статьи является поиск количества палиндромов, а не формирование множества палиндромов.
Я просто пытаюсь до вас довести мысль о том что количество палиндромов можно получить не формируя их множества. Если конечно вы согласны с тем, что в словах казак, шалаш один, а не два палиндрома.
«А роза упала на лапу Азора» все таки один или несколько палиндромов?

ZaMaZaN4iK 1 фев 2016 в 16:25

Разберёмся по порядку. Алгоритм Манакера позволяет как найти количество палиндромов, так и самый длинный: разберитесь в алгоритме и увидите, что это решается одинаково в случае алгоритма Манакера. Так что насчёт этого алгоритма права и Вики, и я (я же учился тоже не от знаний из Вселенной:) ).

Насчёт формирования? Что Вы понимаете под формированием палиндрома? Если Вы имеете ввиду что-то аля «давайте запихнём все палиндромы в вектор». То есть отдельно каждый палиндром представить в виде отдельной строки, то на это уйдет O(N^2) операций. Так а как же Манакер работает? Он просто для каждого центра ищёт радиус самого большого палиндрома с центром в данном элементе (для палиндромов чётной длины происходит некоторая игра с индексами, ничего более). Это и называется поиском самого длинного палиндрома. Но через эту информацию мы также спокойно получаем общее количество палиндромов очевидным способом. Заметьте, что данный алгоритм не формирует множество, он просто считает радиус наибольшего палиндрома с центром в данном элементе, ничего более :) Формирование множества — это уже другая задача. Не храню же я в Манакере сами палиндромы или хотя бы границы КАЖДОГО найденного палиндрома в строке. Я просто храню наибольший радиус для каждого элемента. Ваш алгоритм является интерпретацией Манакера для частного случая (Вы можете заметить сходства между ним и Вашим алгоритмом. По крайней мере я их вижу отчётливо, пусть они и довольно слабы).

Теперь насчёт Ваших примеров. Я отвечу так: слова «казак», «шабаш» являются сами по себе палиндромами и содержат в себе палиндромы. Также как и «а роза упала на лапу азора» — это палиндром, содержащий в себе другие палиндромы. Статья моя о поиске палиндромов в строках. А значит, мне неважно, является исходная строка палиндромом или нет — я должен найти в ней ВСЕ палиндромы(включая саму строку, если она ялвяется палиндромом, естественно. Буквы я за палиндром не считал, но это несложно поправить).

ZaMaZaN4iK 1 фев 2016 в 16:27

И в рамках рассмотренных алгоритмов тот же «казак» раскладывается на 2 палиндрома. Ваша задача сферична и в вакууме, ничего более. Хоть Ваш алгоритм и показывает, как решать такую вот задачу, что похвально. Но я не могу добавить её в статью, так как это всего лишь частный случай.