реклама на сайте
подробности

 
 
> Алгоритм поиска минимальноого периода строки
Diusha
сообщение Dec 31 2010, 12:07
Сообщение #1


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Знаю, что такие есть, знаю, что это одна из стандартных задач на олимпиадах по программированию. Но найти не могу. Гугл не захотел помочь.
Может кто чем поможет? Хотя бы название или фамилию автора.
Алгоритмы с хешированием не подойдут, т.к. подстрока может повторяться не точно
Go to the top of the page
 
+Quote Post
2 страниц V   1 2 >  
Start new topic
Ответов (1 - 20)
Арташес
сообщение Jan 1 2011, 03:31
Сообщение #2


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Цитата(Diusha @ Dec 31 2010, 19:07) *
Может кто чем поможет?


Вот здесь посмотрите: Точный поиск подстроки в строке.

Ну и весь раздел тоже интересен - Поиск в строках, массивах, последовательностях.

Кстати, с Новым годом! beer.gif

Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 1 2011, 11:45
Сообщение #3


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Арташес @ Jan 1 2011, 09:31) *
Кстати, с Новым годом! beer.gif

Новым годом! beer.gif

Цитата(Арташес @ Jan 1 2011, 09:31) *
Вот здесь посмотрите:
Ну и весь раздел тоже интересен -

Я там уже был. Это не то. Там речь о поиске в строке известного образца
Go to the top of the page
 
+Quote Post
ukpyr
сообщение Jan 1 2011, 12:34
Сообщение #4


Профессионал
*****

Группа: Участник
Сообщений: 1 264
Регистрация: 17-06-08
Из: бандустан
Пользователь №: 38 347



http://algolist.manual.ru/search/lrs/index.php
http://kladovka.net.ru/delphibase/?action=...ch&id=10749
http://www.rsdn.ru/forum/alg/752184.flat.aspx
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 1 2011, 14:09
Сообщение #5


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



К сожалению, опять не то.
Требуется вот что:
Есть строка ABCABCABCABC
Из нее нужно выделить минимальный период: ABC (ABCABC тоже период, но уже не минимальный)
Есть строка ABCxABCyABCzABC.
У этой строки периода нет
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 2 2011, 10:13
Сообщение #6


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



А на сайте Олимпиады по программированию смотрели?

Там в библиотеке, в разделе "Алгоритмы на строках" есть две интересные публикации:
  1. "Suffix arrays: A new method for on-line string searches" - Udi Manber, Gene Myers (1991)
    Статья на английском. В ней описан такой мощный инструмент , как суффиксные массивы. Даётся метод с быстродействием O(N * log N) на построение и O(M + log N) на поиск(N - длина строки, в которой ищется подстрока длины М). Алгоритмы которые работают с суффиксными деревьями быстрее, но, как правило, сложнее.
  2. "Лекции по информатике" - Дмитрий Павлов (2003)
    Конспект лекций двукратного чемпиона мира по программированию ACM ICPC, проведенных в рамках подготовки школьников Санкт-Петербурга к всероссийским олимпиадам по информатике. Сделана попытка изложить темы и алгоритмы, которые активно применяются в олимпиадах и которые недостаточно хорошо освещены в доступной литературе по информатике: структуры данных (особенно, деревья Фенвика и отрезков), динамическое программирование, поиск подстроки в строке, проективная геометрия, практические замечания и др.


Эти статьи я, на всякий случай, прилагаю.
Прикрепленные файлы
Прикрепленный файл  sfx_array.zip ( 88.65 килобайт ) Кол-во скачиваний: 72
Прикрепленный файл  informatics_lection.ps ( 961.5 килобайт ) Кол-во скачиваний: 25
 
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 3 2011, 03:33
Сообщение #7


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Арташес @ Jan 2 2011, 16:13) *
  1. "Suffix arrays:
  2. "Лекции по информатике" - Дмитрий Павлов (2003)

1 - поиск ивестной подстроки - не то
Вообще O(N * log N) - больно долго. Видимо, этот алгоритм оправдывает себя в тех случаях, когда в одной строке надо найти кучу образцов (за счет O(M + log N) ). А для разового поиска, по-моему, ничего быстрее КМП не придумали ( O(M+N) на всё - про всё)

2 - пока не сумел посмотреть. Скачал Post Script Viewer, а он .ps не видит wacko.gif
Не пoдскажете, чем .ps смотрите?




Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 3 2011, 06:10
Сообщение #8


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Цитата(Diusha @ Jan 3 2011, 10:33) *
Не пoдскажете, чем .ps смотрите?


Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 4 2011, 14:13
Сообщение #9


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Арташес @ Jan 3 2011, 12:10) *
Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/

Пока вылезают проблема за проблемой. Возможно, я туповат...
Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное?
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 4 2011, 17:22
Сообщение #10


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Цитата(Diusha @ Jan 4 2011, 21:13) *
Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное?

Есть самый прямой вариант - Adobe Acrobat (вернее, Distiller). Но вообще странно, с Ghostscipt'ом, обычно, проблем не возникает.
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 5 2011, 00:21
Сообщение #11


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



У меня проблемы могут быть везде. Вот и сейчас Акробата установить не могу, т.к. CD-ром сдох (Фокситом пользуюсь)
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 5 2011, 01:14
Сообщение #12


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Цитата(Diusha @ Jan 5 2011, 07:21) *
Вот и сейчас Акробата установить не могу...

Ладно, в таком случае я предлагаю воспользоваться онлайн конвертором - PS to PDF - The Online Converter. На всякий случай прилагаю уже обработанный Ghostscipt'ом файл.
Прикрепленные файлы
Прикрепленный файл  informatics.pdf ( 464.04 килобайт ) Кол-во скачиваний: 66
 
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 6 2011, 08:17
Сообщение #13


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Арташес @ Jan 5 2011, 07:14) *
На всякий случай прилагаю уже обработанный Ghostscipt'ом файл.

Спасибо! Лекции интересные, в любом случае пригодятся.
Но ответа на конкретный вопрос я так и не нашел
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 7 2011, 05:59
Сообщение #14


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Цитата(Diusha @ Jan 6 2011, 15:17) *
Но ответа на конкретный вопрос я так и не нашел

На том же сайте есть книжка:
"Программирование: теоремы и задачи." - А.Шень (2004)
Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги - научить основным методам построения корректных и быстрых алгоритмов.
Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, а также в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ.

На всякий случай прилагаю и ее. Кстати, она тоже в PostScript формате.

Вообще, могу посоветовать вспомнить хоть какое-то, именно, для искомого алгоритма специфичное слово или понятие. Будет значительно легче.

Сообщение отредактировал Арташес - Jan 7 2011, 06:00
Прикрепленные файлы
Прикрепленный файл  progbookps.zip ( 735.81 килобайт ) Кол-во скачиваний: 150
 
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 7 2011, 12:03
Сообщение #15


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Вот еще одна интересная публикация:

Анализ строк (String Search) - Graham A. Stephen, October 1992.

Цитата
Хотя этот обзор написан относительно давно, он, судя по всему, еще не потерял актуальности. Перечисленные в нем задачи и методы их решения составляют основу интенсивных исследований. Активные эксперименты с суффиксными деревьями привели к резкому снижений требуемой ими памяти, так что они становятся де-факто стандартом в приложениях, связанных с нестрогим поиском в словарях больших объемов. Список примеров легко продолжить.

Конечно, за прошедшие годы проводились многочисленные новые исследования и появились многочисленные новые статьи, не вошедшие в этот обзор. Вместе с тем, конец «периода полураспада» приведенных в нем результатов еще очень далек. Я надеюсь, вы прочтете этот материал с пользой и удовольствием.
П.Дубнер
Ноябрь 1999


Содержание достаточно заманчивое:
Цитата
Код
1. ВВЕДЕНИЕ
2. ЗАДАЧА
    2.1 Определение задачи
3. ОБЗОР АЛГОРИТМОВ
    3.1 Сопоставления строк
    3.2 Расстояния между строками
         3.2.1 Обобщенные задачи
    3.3 Нечеткое сопоставление строк
         3.3.1 Специальные устройства
         3.4 Максимальная повторяющаяся подстрока
4. АЛГОРИТМЫ
    4.1 Поиск образцов
         4.1.1 Наивный подход
         4.1.2 Кнут-Моррис-Пратт
         4.1.3 Бойер-Мур
         4.1.4 Бойер-Мур-Хорспул
         4.1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
         4.1.6 Хьюм и Сандей.Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
         4.1.7 Харрисон
         4.1.8 Карп-Рабин
    4.2 Расстояние между строками и самая длинная общая подпоследовательность
         4.2.1 Вагнер-Фишер
         4.2.2 Хиршберг
         4.2.3 Хант-Шиманский
         4.2.4 Машек-Патерсон
         4.2.5 Укконен
         4.2.6 Самая тяжелая общая подпоследовательность
    4.3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК
          4.3.1 k несовпадений - Ландау-Вишкин
          4.3.2 k различий - Ландау-Вишкин
    4.4 Самая длинная повторяющася подстрока
          4.4.1 Наивный подход
          4.4.2 Суффиксные деревья
5. НАЗАД, К ИСХОДНОЙ ЗАДАЧЕ
   5.1 Система
   5.2 Задача
6. ПРИЛОЖЕНИЕ A: АСИМПТОТИЧЕСКАЯ ЗАПИСЬ
7. ЛИТЕРАТУРА


Сообщение отредактировал Арташес - Jan 7 2011, 12:31
Go to the top of the page
 
+Quote Post
Арташес
сообщение Jan 7 2011, 13:12
Сообщение #16


Частый гость
**

Группа: Участник
Сообщений: 153
Регистрация: 16-06-07
Из: Армения
Пользователь №: 28 476



Обнаружил специализированный ресурс - http://www.itman.narod.ru/. Много полезного.

Вот еше:

Fast and Practical Approximate String Matching (1992).

Солодков, А.Ю. Идентификация сложных объектов нечисловой природы в СУБД с наличием ошибок и пропусков данных [Электронный ресурс] / А.Ю. Солодков. - Саратовский государственный технический университет, 2003. Режим доступа: ]http://iu4.bmstu.ru/konf/2003/sbornik/s2_29.doc

Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. – М.: Мир, 1987. – 120 с.:ил.

Ниман, Томас Сортировка и поиск: Рецептурный справочник / Томас Ниман. – М.: Вильямс, 1998. – 62 с.

Смит, Билл Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычислений / Билл Смит. – М.: Вильямс, 2006. - 496 с.:ил.

Гасфилд, Дэн Строки, деревья и последовательности: Пер. с англ. / Дэн Гасфилд. – СПб.: Невский Диалект; БХВ-Петербург, 2003. – 654 с.:ил.

Цыганов, Н.Л. Обзор алгоритмов нечёткого сопоставления записей применительно к задаче исключения дублирования персональных данных [Электронный ресурс]/ Н.Л. Цыганов, М.В. Марковский. - Московский инженерно-физический институт, 2006. – Режим доступа: http://www.library.mephi.ru/data/scientifi.../t15/1-1-25.doc

Сообщение отредактировал Арташес - Jan 7 2011, 14:57
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 8 2011, 03:24
Сообщение #17


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Арташес @ Jan 7 2011, 11:59) *
Вообще, могу посоветовать вспомнить хоть какое-то, именно, для искомого алгоритма специфичное слово или понятие. Будет значительно легче.

Было бы чего вспомнить, вспомнил бы sm.gif

Спасибо, Арташес, много интересного, покопаюсь
Go to the top of the page
 
+Quote Post
Oldring
сообщение Jan 8 2011, 06:05
Сообщение #18


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Можно уточнить задачу.
Найти алгоритм поиска минимального периода в строке, работающий быстрее (в среднем, в худшем), чем O(L*T), где L - длина строки, T - минимальный период подстроки

И протестировать алгоритм на следующей строке:

Цитата
ababbababbabababbababbab


Цитата(Diusha @ Dec 31 2010, 18:07) *
т.к. подстрока может повторяться не точно


И какой критерий "повторения неточно"?


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 8 2011, 15:03
Сообщение #19


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Oldring @ Jan 8 2011, 12:05) *
Можно уточнить задачу.
Найти алгоритм поиска минимального периода в строке, работающий быстрее (в среднем, в худшем), чем

Само собой, о т.н. наивном поиске речи не идет, "время - деньги"

Цитата(Oldring @ Jan 8 2011, 12:05) *
И какой критерий "повторения неточно"?

Критерий такой:
1) если вместо "а" в следующем периоде в той же позиции не "а", а где-то между "а" и "b", скажем "а с половиной", то считаем, что совпадение есть. А если "а и 6 десятых", то уже нет.
2) Могут быть лишние буквы. При их доле меньше чем, считаем, что период не нарушен.
На самом деле речь не о строке как таковой, из букв. Вместо букв - пары чисел.
Если бы требовалось найти заданную "подстроку" в "строке" (в смысле последовательности чисел), то алгоритм КМП (Кнута-Морриса-Пратта) можно было бы модифицировать и для моего случая и префикс-функцию считать не как целую, а как вещественную.
Откопав алгоритм поиска периода, может удалось бы и его модифицировать. Но может - нет. Пока не нашел, не знаю.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Jan 8 2011, 16:23
Сообщение #20


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Diusha @ Jan 8 2011, 21:03) *
1) если вместо "а" в следующем периоде в той же позиции не "а", а где-то между "а" и "b", скажем "а с половиной", то считаем, что совпадение есть. А если "а и 6 десятых", то уже нет.


"а с половиной" - да, это круто. Это уже не дискретная математика, а матан.
А если в одной строке "а с половиной", а в другой - лишняя "б", то какая лучше?
А если есть период длиной 3 в которой а с половиной, и есть период 10, но точный, то какой лучше?
А может быть вам вообще не нужен точный минимальный период?
И можно сделать ПФ строки, и найти первый пик?
Правильно сформулировать хадачу - это наполовину её решить wink.gif


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Diusha
сообщение Jan 9 2011, 00:15
Сообщение #21


Вечный студент
****

Группа: Участник
Сообщений: 500
Регистрация: 11-09-06
Из: Питер
Пользователь №: 20 262



Цитата(Oldring @ Jan 8 2011, 22:23) *
"а с половиной" - да, это круто.

Да ладно к словам-то цепляться, ведь мысль понятна wink.gif
Я же говорил, что в некоторых случаях изначально сугубо дискретный алгоритм можно подправить под недискретную задачу. Еще раз говорю: пока не нашелся алгоритм, упомянутый в заголовке, неизвестно, можно ли его модифицировать

Цитата(Oldring @ Jan 8 2011, 22:23) *
А если ...
А если ...

Ввести для каждого случая цену отклонения от идеального повторения и выбирать что дешевле: две "а с половинкой" или 3 лишних б.

Цитата(Oldring @ Jan 8 2011, 22:23) *
Правильно сформулировать хадачу - это наполовину её решить wink.gif

Правильно сформулированная задача - в заголовке темы. Вернее, подзадача. Но правильным ли путем я пошел, выбрав именно эту подзадачу (АПМПС), не уверен.
Более глобальную задачу я сформулировал тут

Сообщение отредактировал Diusha - Jan 9 2011, 01:44
Go to the top of the page
 
+Quote Post

2 страниц V   1 2 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 23rd July 2025 - 19:19
Рейтинг@Mail.ru


Страница сгенерированна за 0.01584 секунд с 7
ELECTRONIX ©2004-2016