поиск последовательностей

← →
robt5 (2013-12-21 18:37) [0]

кто знает (где найти) алгоритм поиска последовательностей на паскале ?
например простейший вариант:
есть длиииинный массив чисел\слов, нужно в нем найти все повторяющиеся последовательности чисел\слов

← →
Pavia © (2013-12-21 19:30) [1]

На http://forum.sources.ru/ была тема в рездели Delphi.

← →
MBo © (2013-12-21 20:39) [2]

Задача нечетко сформулирована.
Не исключено, что может помочь суффиксный массив

← →
Германн © (2013-12-21 20:45) [3]

> например простейший вариант:
> есть длиииинный массив чисел\слов, нужно в нем найти все
> повторяющиеся последовательности чисел\слов
>

Ничего себе простейший вариант!

← →
Юрий Зотов © (2013-12-22 00:57) [4]

Что есть последовательность слов? Одно слово - это последовательность?

← →
antonn © (2013-12-22 01:07) [5]

вряд ли одно вхождение элемента в массиве можно считать последовательностью

← →
Юрий Зотов © (2013-12-22 01:33) [6]

> antonn © (22.12.13 01:07) [5]

А два слова - это последовательность?

← →
robt5 (2013-12-22 10:53) [7]

ну пример примитивный одноциферный
5786243465468732583468748123123483465465239147677034823489568402324476976563443465464
жирным выделена повторяющееся последовательность, "растояние" между ними любое, длина тоже любая, минимальную длину\число повторов можно задавать

слова тоже можно представить числами поэтому это неважно, можно считать что речь чисто о числах

← →
jumping jack (2013-12-22 12:25) [8]

об алгоритме говорить нельзя, пока не ясно, что конкретно он должен выдавать в качестве результата

если искать во всем файле все последовательности, т.е. в приведенном примере - начиная с 57, 578, 5785, 57862 и т.д. до половины всего файла - это будет офигительно долго, любым способом!

34, 346, 46, 3465, 465, 34654, 4654, 654, 54 тоже нужны, несмотря на то, что 3465464 их включает?

ускоренный поиск подстроки: http://delphiworld.narod.ru/base/search_text.html
чем-то похожая задача встречается при сжатии, например, в LZ77: http://habrahabr.ru/post/141827/

← →
Smile (2013-12-22 15:56) [9]

> MBo © (21.12.13 20:39) [2]
> Задача нечетко сформулирована.

Разговор и обсуждения исперчены ...

← →
antonn © (2013-12-22 16:02) [10]

>
> А два слова - это последовательность?

не исключено

← →
Юрий Зотов © (2013-12-22 16:31) [11]

> antonn © (22.12.13 16:02) [10]

Замечательно. Осталось только научить компьютер понимать, что означает это самое "не исключено".

← →
antonn © (2013-12-22 16:40) [12]

> Осталось только научить компьютер понимать, что означает
> это самое "не исключено".

это называется "алгоритм".

← →
картман © (2013-12-22 16:41) [13]

> robt5 (22.12.13 10:53) [7]

> слова тоже можно представить числами

не более 10 разных слов?

← →
картман © (2013-12-22 16:43) [14]

хотя, ответ в [2] дан

← →
Юрий Зотов © (2013-12-22 16:43) [15]

> antonn © (22.12.13 16:40) [12]

Нет, это называется не "алгоритм", а "женская логика": Да/Нет/МожетБыть.

← →
antonn © (2013-12-22 16:45) [16]

> Нет, это называется не "алгоритм"

это называется "алгоритм".

← →
Юрий Зотов © (2013-12-22 16:46) [17]

> antonn © (22.12.13 16:45) [16]

У Вас - возможно. Спорить не буду.

← →
картман © (2013-12-22 17:13) [18]

женский алгоритм))

← →
robt5 (2013-12-22 18:46) [19]

> об алгоритме говорить нельзя, пока не ясно, что конкретно
> он должен выдавать в качестве результата

максимально длинная непрерывная последовательность и кол-во повторов (ясен пень от 2х и выше)

> картман © (22.12.13 16:41) [13]

слова? это уже моя проблема и сказано [7] что можно про них забыть

← →
картман © (2013-12-22 18:50) [20]

> robt5 (22.12.13 18:46) [19]

суффиксный массив чем не подошел?

← →
robt5 (2013-12-22 22:54) [21]

> суффиксный массив чем не подошел?

там же блин разбор строки, а у меня числа\слова

← →
Pavia © (2013-12-22 23:13) [22]

> > суффиксный массив чем не подошел?там же блин разбор строки,
> а у меня числа\слова

Теперь точно женская логика.

Считай цифры символами, а числа строками.

← →
картман © (2013-12-23 06:47) [23]

> robt5 (22.12.13 22:54) [21]
>
>
> > суффиксный массив чем не подошел?
>
> там же блин разбор строки, а у меня числа\слова

строка - массив символов, текст - массив слов. В чем разница-то? Передвигайся по словам, а не по символам.

А тексты большие?

← →
antonn © (2013-12-23 08:43) [24]

> В чем разница-то?

разница в том, что "слова" это больше чем массив символов, по крайней мере когда их несколько. и если предположить, что "слова" означают группы символов разделенных пробелами, началом/концом строк и некоторыми знаками препинания (в общем что-то типа \b в регулярках), то выполнить поиск повторяющихся слов куда проще и быстрее чем искать последовательности непонятной длины в одном массиве

← →
картман © (2013-12-23 09:29) [25]

> antonn © (23.12.13 08:43) [24]

автору нужно искать

> нужно в нем найти все повторяющиеся последовательности чисел\слов

← →
antonn © (2013-12-23 09:45) [26]

> автору нужно искать

авто, вообще-то, ничего конкретного не сказал

← →
Sha © (2013-12-23 10:03) [27]

robt5, решение задачи может заметно упроститься
при использовании ее особенностей и ограничений.

← →
robt5 (2013-12-23 10:59) [28]

ок, еще раз
нет никаких слов букв и текстов, все забыли про них
есть только некий поток чисел, ну допустим типа integer
у потока нет конца - он непрерывен пока работает сама программа, но может останавливаться на неопределенное время
нужно найти повторяющиеся непрерывные последовательности этих чисел
для оптимизации скорости можно ввести стартовые значения этих последовательностей (первое число), минимальную длину и максимальную теоретическую длину (как бы копируем для вторичной обработки) последовательности, но больше интересен поиск без ограничений
"растояние" между последовательностями непостоянно\нерегулярно, либо его может не быть (идут встык)

результат - определить наличие\отсутствие каких либо последовательностей, вывести их + число повторов

з.ы. это не лаба, не курсовая и не диплом

← →
картман © (2013-12-23 11:06) [29]

> у потока нет конца - он непрерывен пока работает сама программа

хм, алгоритм оракула тоже нужен?

← →
картман © (2013-12-23 11:36) [30]

> robt5 (23.12.13 10:59) [28]

SuffixArray: array of array

0:00:10
MyArray = [0,1,2]

SuffixArray:
0,1,2
1,2
2
SearchLCP()

0:01:00
MyArray.Add(0);
SuffixArray:
0,1,2 + (0)
1,2 + (0)
2 + (0)
0
SearchLCP()

хранить не суффиксы, а индексы.

← →
Pavia © (2013-12-23 12:12) [31]

> результат - определить наличие\отсутствие каких либо последовательностей,
> вывести их + число повторовз.ы. это не лаба, не курсовая
> и не диплом

И не реальная задача. :-P. Чем мы больше знаем о задаче чем лучше её можно оптимизировать.

Ну сделай перебор. Перебираешь все возможные под последовательности и их позиции.

Выбираешь все тройки из своего массива. Сортируешь получаешь число троек.
Для каждой группы троек выбираем четвёрки и так далее.

robt5,

давай рассмотрим твою задачу на примере генератора случайных чисел Delphi. Неясно, какой результат ты хочешь получить.

> повторяющиеся непрерывные последовательности этих чисел

Насколько я понимаю непрерывная последовательность БЕСКОНЕЧНА, значит при бесконечном потоке он и есть искомая последовательность. Я решил, ура!!!

← →
jumping jack (2013-12-24 14:02) [34]

robt5> у потока нет конца...
robt5> нужно найти...

не "найти", а находить? пополняя список найденного после каждого нового полученного числа?
ты понимаешь, что список будет быстро расти?
нужно ли вообще выводить куда-то этот список? как и когда?
может, нужно его сортировать? или отбрасывать лишнее?

← →
не тормоз (2013-12-24 14:11) [35]

да банально словарь данных для самопального архиватора он пишет

>Нет, это называется не "алгоритм", а "женская логика": Да/Нет/МожетБыть.

Седни, это называется новодным словом fuzzy-logic:)
Основатель - Заде.

>Чем мы больше знаем о задаче

Если мы знаем о задаче все - ее и решать не надо:)

А как же? Вместо "Истина"/"Ложь" - степень истинности.

← →
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]

> jumping jack (24.12.13 19:55) [42]
>
> ну вроде не архисложно

но архивычислительно

← →
jumping jack (2013-12-24 21:43) [44]

тупой алгоритм - да, сложность кубическая
но если 1) применить Бойера-Мура и 2) ограничить глубину поиска и длину искомого, то как бы все степени мы убираем, то есть осталась простая пропорция к длине последовательности, хоть и с большим коэффициентом
архиваторы ведь как-то справляются со сложностью - нет там степеней-то, чистые мегабайты в секунду

поиск последовательностей Найти похожие ветки