Форум: "Прочее";
Текущий архив: 2014.07.13;
Скачать: [xml.tar.bz2];
Вниз
поиск последовательностей Найти похожие ветки
← →
robt5 (2013-12-24 17:30) [40]
> jumping jack (24.12.13 14:02) [34]
да, по всем пунктам кроме вывода
вывод пока неактуален
> не тормоз (24.12.13 14:11) [35]
нет не архиватор, но подобный "словарь" близок к идее (ты реально не тормоз)
← →
не тормоз (2013-12-24 19:06) [41]да я в курсе.
я же медвежонок пятачок.
← →
jumping jack (2013-12-24 19:55) [42]ну вроде не архисложно
с получением каждого нового символа/числа добавляем его не в конец, а в начало буфера и ищем начинающуюся с него последовательность с разными смещениями, наращивая смещение по единичке в цикле, начиная с 2 или заданного минимума и заканчивая половиной размера всего полученного или заданным максимумом
(конечно, новополученное проще добавлять не в начало, а в конец буфера, но тогда искать нужно "задом наперед")
это примитивный алгоритм, для ускорения можно применить Бойера-Мура - описан в первой ссылке в [8]
← →
картман © (2013-12-24 20:47) [43]
> jumping jack (24.12.13 19:55) [42]
>
> ну вроде не архисложно
но архивычислительно
← →
jumping jack (2013-12-24 21:43) [44]тупой алгоритм - да, сложность кубическая
но если 1) применить Бойера-Мура и 2) ограничить глубину поиска и длину искомого, то как бы все степени мы убираем, то есть осталась простая пропорция к длине последовательности, хоть и с большим коэффициентом
архиваторы ведь как-то справляются со сложностью - нет там степеней-то, чистые мегабайты в секунду
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2014.07.13;
Скачать: [xml.tar.bz2];
Память: 0.52 MB
Время: 0.004 c
