Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   www.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 19.08.2014, 13:21   #1
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Поиск повторений

Есть строка (не строка, а по идее sampleData аудио файла), вот я в ней хочу найти повторения. Выгуглил только поиск известных подстрок, а в данном случае мы их не знаем.
Пример:
аллаелапомидорыалаеламидий
На выходе(подстрока и список адресов подстроки):
аллаела - 0,15
мид-9,22
...
...
Т.е ищем максимальные по длине подстроки.

Чую сам не догоню
__________________
Сайт: http://iexpo.ml
(Offline)
 
Ответить с цитированием
Старый 19.08.2014, 15:02   #2
DStalk
Разработчик
 
Аватар для DStalk
 
Регистрация: 26.06.2009
Адрес: Рязань-Москва
Сообщений: 470
Написано 400 полезных сообщений
(для 1,068 пользователей)
Ответ: Поиск повторений

Напишу на пурике - но общий алгоритм думаю понятен. Фиг знает как с производительностью...
Наверно нужно ограничение на длину семпла...

data.s=... ;Исходные данные
max_sample.i=10 ;Ограничение на длину семпла
Structure sample
  List Pos.i()
EndStructure
NewMap Samples.Sample()

;Перебираем все символы - позиция "курсора"
For pos=1 To Len(data)

  ;Перебираем семплы разной длины от данной позиции
  For sample_len=1 to max_sample
    cur_sample.s=Mid(data,pos,sample_len)

    ;Ищем данный семпл в сохраненных
    If FindMapElement(Samples(),cur_sample)=0

      ;Если нет, добавляем
      AddMapElement(Samples(),cur_sample)

      ;Ищем данный семпл в оставшейся части данных, запоминаем позиции
      find_pos=FindString(data,cur_sample,pos)

      Repeat
        AddElement(Samples()\Pos())
        Samples()\Pos()=find_pos
        find_pos=find_pos+Len(cur_sample)
        find_pos=FindString(data,cur_sample,find_pos)
      Until find_pos>0

    EndIf

  Next

Next
В итоге получим кучу записей Samples() со списком позиций в каждой.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
RegIon (20.08.2014)
Старый 20.08.2014, 03:42   #3
RegIon
Элита
 
Аватар для RegIon
 
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений
(для 1,012 пользователей)
Ответ: Поиск повторений

Точно, можно же найти первый подсемпл и потом стандартным алгоритмом его прогнать и найти все вхождения , что-то затупил

А можно, я так подумал, АКФ расчитать и в пиках функции буду совпадения.
http://ru.m.wikipedia.org/wiki/%D0%9...%D0%B8%D1%8 F

Эта штука хороша для аудиоигр, что бы не только в зависимости от спектра была игра
__________________
Сайт: http://iexpo.ml

Последний раз редактировалось RegIon, 20.08.2014 в 05:10.
(Offline)
 
Ответить с цитированием
Старый 21.08.2014, 20:25   #4
genroelgvozo
Нуждающийся
 
Регистрация: 08.05.2008
Сообщений: 87
Написано 9 полезных сообщений
(для 15 пользователей)
Ответ: Поиск повторений

Но если по теме еще нужно, то самый оптимальный алгоритм описан тут
http://e-maxx.ru/algo/string_tandems
Вообще на этом сайте собрано много различных алгоритмов из разных областей, используемых во основном на олимпиадном программировании, там где важна скорость выполнения.
Но предупреждаю что алгоритм далеко не простой, задача не тривиальна.
Хотя для других задач есть удивительно простые но в тоже время удивительно быстрые алгоритмы. Вообщем советую сайт

ИСПРАВЛЕНО: извиняюсь ошибся, по ссылке немного другая задача.
Но можешь вообще по сайту посмотреть, может что полезное будет, благо со строками там не мало алгоритмов
__________________
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +1, время: 02:40.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com