Обнаружил специализированный ресурс - 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

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

Спасибо, Арташес, много интересного, покопаюсь

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

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





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

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


Критерий такой:
1) если вместо "а" в следующем периоде в той же позиции не "а", а где-то между "а" и "b", скажем "а с половиной", то считаем, что совпадение есть. А если "а и 6 десятых", то уже нет.
2) Могут быть лишние буквы. При их доле меньше чем, считаем, что период не нарушен.
На самом деле речь не о строке как таковой, из букв. Вместо букв - пары чисел.
Если бы требовалось найти заданную "подстроку" в "строке" (в смысле последовательности чисел), то алгоритм КМП (Кнута-Морриса-Пратта) можно было бы модифицировать и для моего случая и префикс-функцию считать не как целую, а как вещественную.
Откопав алгоритм поиска периода, может удалось бы и его модифицировать. Но может - нет. Пока не нашел, не знаю.

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

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


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


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

Сообщение отредактировал Diusha - Jan 9 2011, 01:44