Алгоритм поиска повторяющихся подпоследовательностей
ты хочешь делать это в рантайме, или по в трассе пробного погона выделить циклы и убрать их в будущем?
Задача непростая. Например, алгоритмы lossless-компресии это делают, когда словарь строят.
думаю, решать задачу в общем виде смысла нет
могу порекомендовать что-то типа такого: http://www.unix.com/unix-dummies-questions-answers/10617-cou...
то есть отсортировать строки файла, затем найти дубликаты и их кол-во. те строки, которые повторяются огромное число раз можно фильтрануть
далее исключать некоторые строки из логов по паттерну
зы: я так понял, что речь об огромных логах.
могу порекомендовать что-то типа такого: http://www.unix.com/unix-dummies-questions-answers/10617-cou...
то есть отсортировать строки файла, затем найти дубликаты и их кол-во. те строки, которые повторяются огромное число раз можно фильтрануть
далее исключать некоторые строки из логов по паттерну
зы: я так понял, что речь об огромных логах.
суффиксные деревья же (в общем случае). хотя при таких объемах логов надо смотреть на суть данных
а че покупка терабайтничка не спасает ситуацию? ну попробуйте экономнее в логи срать
а че покупка терабайтничка не спасает ситуацию? ну попробуйте экономнее в логи срать
а че покупка терабайтничка не спасает ситуацию? ну попробуйте экономнее в логи сратьписать лог на диск через gzip например
думаю, решать задачу в общем виде смысла нетКонечно нет, т.к. она уже решена. Нужно использовать программы сжатия данных. Вариантов разных по скорости работы/степени сжатия много. Начать можно с сравнения: lzo, gzip, xz.
писать лог на диск через /dev/null например
Нужно использовать программы сжатия данныхэто, конечно, решение, но не ясно какой задачи
в общем, телепатией пробуем набросать варианты
Почему не ясно? Сжать архиватором, а потом просмотреть его словарь.
Сжать архиватором, а потом просмотреть его словарь.ах вот оно что
я подумал, что логи через стримовый архиватор надо прогонять и так сохранять в сжатом виде
я подумал, что логи через стримовый архиватор надо прогонять и так сохранять в сжатом видеНу я вообще-то так и имел в виду. Программа сжатия хорошо справится с задачей "устранения" часто повторяющихся циклов.
а какая глубина обычно у словаря может быть? что если повторение - это многомегабайтный паттерн?
решать надо в реалтайме.
данные плодятся быстро. выводить в хранилище надо не все данные, потому как даже если все данные выводить - на напасёшься и десяти терабайтников.
попробую конкретизировать нашу задачу:
имеется программа, после каждой фигурной скобки (условно) вставлена конструкция вида: F(NNN);
здесь NNN - уникальное число для каждого места вставки.
сейчас функция F(x) это (условно) printf("%d\n",X); (опуская всевозможные оптимизации и пр.).
программа - большая. таких F вставлено ~5млн.
задача - выделить существенно различные последовательности вызовов F.
боюсь, курсив формализовать будет сложно.
понятно, что есть фрагменты, выполняющиеся довольно часто (например, в общеиспользуемых "библиотечных" функциях). хотелось бы исключить их из сохранения после срабатывания. т.е. на диск отправлять только первый вызов такой функци. В дальнейшем - просто записывать, что де вызов будет осуществлён по такому-то маршруту, сохранённому ранее.
Задача в принципе очень похожа на построение словаря.
данные плодятся быстро. выводить в хранилище надо не все данные, потому как даже если все данные выводить - на напасёшься и десяти терабайтников.
попробую конкретизировать нашу задачу:
имеется программа, после каждой фигурной скобки (условно) вставлена конструкция вида: F(NNN);
здесь NNN - уникальное число для каждого места вставки.
сейчас функция F(x) это (условно) printf("%d\n",X); (опуская всевозможные оптимизации и пр.).
программа - большая. таких F вставлено ~5млн.
задача - выделить существенно различные последовательности вызовов F.
боюсь, курсив формализовать будет сложно.
понятно, что есть фрагменты, выполняющиеся довольно часто (например, в общеиспользуемых "библиотечных" функциях). хотелось бы исключить их из сохранения после срабатывания. т.е. на диск отправлять только первый вызов такой функци. В дальнейшем - просто записывать, что де вызов будет осуществлён по такому-то маршруту, сохранённому ранее.
Задача в принципе очень похожа на построение словаря.
программа однопоточная или многопоточная?
можно ли программу считать чисто функциональной? внутренняя работа функции зависит только (или в основном только) от входных параметров функции
на сишарпе.
для простоты будем считать, что однопоточная
для простоты будем считать, что однопоточная
а какая глубина обычно у словаря может быть? что если повторение - это многомегабайтный паттерн?Для больших файлов есть rzip, lrzip. Правда первый в потоковом режиме работать не умеет. Хотя про размер повторений не уверен. Но тут вроде собираются свой велосипед делать, поэтому суть здесь в алгоритмах в основном.
задача - выделить существенно различные последовательности вызовов F.Нука падажжи на.
боюсь, курсив формализовать будет сложно.
Ты таки чего именно хочешь? Тулзу для эффективного архивирования данных Особого Вида (множество _длинных_ повторяющихся подпоследовательностей или всё же тулзу для датамайнинга логов, чтобы смотреть на них сквозь неё?
Если первое, то прозреваю что нормальные архиваторы и так довольно хорошо будут жать такие данные, особенно если поиграться с настройками. И им будет глубоко пофиг на твоё типа-неформализуемое "а вот тут у нас число которое нас не интересует", они пожмут последовательность до него и последовательность после него отдельно.
Если второе, то ищи в гугле тулзы для этого, они существуют!
сжатие не факт, что поможет.
например, следующие последовательности вызовов с точки зрения ТС скорее всего одинаковые (т.к. это просто разная длина последовательности внутри F1 а для архиватора это разные последовательности
например, следующие последовательности вызовов с точки зрения ТС скорее всего одинаковые (т.к. это просто разная длина последовательности внутри F1 а для архиватора это разные последовательности
F1
F2
F2
F1
F2
F2
F2
F2
F2
F1
F2
F2
F2
ну пускай индентацию не пишут, а пишут вход-выход из блока.
блин, мне кажется, я не понял твою идею 
смысл в том, что с точки зрения архиватора это ужимается максимум до:
а с точки зрения логики ТС до:
ps
индентация вместо входа/выхода чисто для удобства визуализации
F1
F2{2}
F1
F2{5}
F1
F2{3}
а с точки зрения логики ТС до:
F1
F2
F2
//остальное выкидывается, как похожее на уже записанное
ps
индентация вместо входа/выхода чисто для удобства визуализации
смысл в том, что с точки зрения архиватора это ужимается максимум до:Не факт. Там же не RLE используется.
Я думаю тут нужно не гадать, а пример данных засунуть туда и посмотреть сколько выйдет. Я замечал, что на всяких журналах степень сжатия вполне может быть в 20-25 раз.
Программа сжатия хорошо справится с задачей "устранения" часто повторяющихся циклов.
Типичные архиваторы семейства LZ (zip, lzma в 7z) имеют скользящее окно, в котором ищут совпадения, и оно обычно небольшое - меньше мегабайта. Для типичных логов, где повторяются короткие строки, это работает отлично, но тут не факт.
А если взять bzip2, там вообще BWT так данные наизнанку выворачивает, что ничего похожего на повторяющиеся циклы там не увидишь.
Короче, стоит подумать в сторону хитро оптимизированного представления суффиксных деревьев и LZW.
F1 F2 F2 F1 F2 F2 F2 F2 F2 F1 F2 F2 F2Для zip'a это что-то вроде
F1, F2, F2,
{повторить 3 символа от смещения -3},
{повторить 2 символа от смещения -2},
F2,
{повторить 4 символа от смещения -6}.
Причем факт того, что повторяемые в первой и третьей ссылке последовательности совпадают (первые 3 символа из упакованного потока просто так не вычленишь.
Типичные архиваторы семейства LZ (zip, lzma в 7z) имеют скользящее окно, в котором ищут совпадения, и оно обычно небольшое - меньше мегабайта.Ну вроде как LZMA — не только идеи LZ в себе содержит. Вот, например, из мануала по lzip:
Lzip implements a simplified version of the LZMA (Lempel-Ziv-MarkovИ словарь там не такой маленький. Из мануала xz:
chain-Algorithm) algorithm. The high compression of LZMA comes from
combining two basic, well-proven compression ideas: sliding dictionaries
(LZ77/78) and markov models (the thing used by every compression
algorithm that uses a range encoder or similar order-0 entropy coder as
its last stage) with segregation of contexts according to what the bits
are used for.
Preset DictSize CompCPU CompMem DecMemНу и это всё можно отдельно подкрутить.
-0 256 KiB 0 3 MiB 1 MiB
-1 1 MiB 1 9 MiB 2 MiB
-2 2 MiB 2 17 MiB 3 MiB
-3 4 MiB 3 32 MiB 5 MiB
-4 4 MiB 4 48 MiB 5 MiB
-5 8 MiB 5 94 MiB 9 MiB
-6 8 MiB 6 94 MiB 9 MiB
-7 16 MiB 6 186 MiB 17 MiB
-8 32 MiB 6 370 MiB 33 MiB
-9 64 MiB 6 674 MiB 65 MiB
Для типичных логов, где повторяются короткие строки, это работает отлично, но тут не факт.Ну мне неизвестно, насколько у них логи типичные или нет, поэтому и предлагал как раз опробовать сжатие разными вариантами.
А если взять bzip2, там вообще BWT так данные наизнанку выворачивает, что ничего похожего на повторяющиеся циклы там не увидишь.
Для zip'a это что-то вродеесли это обобщить, то видно, что до одинакового вида сжимается только начало подпоследовательностей, а хвост подпоследовательностей переводится в нерегулярную форму.
Если брать трассу с большим кол-вом уровней (а не два, как в примере то это еще будет нагляднее видно.
зы
вообще, для сравнения трасс используется сравнение с потерей информацией (и поэтому требуется сжатие с потерей информацией).
в частности, считается неважным:
кол-во итераций цикла (и соответственно, кол-во вызовов функций из под цикла в целом
кол-во итераций рекурсии
Для того, чтобы это использовать стоит использовать ручное сжатие.
Циклы выкидываются достаточно просто, следующая последовательность
F3
F2
F1
F1
F2
F1
F3
F2
F1
F1
F1
F2
F1
F1
F1
F1
F2
F1
F1
сначала переводится в вид
F3
F2
F1{2}
F2
F1{1}
F3
F2
F1{3}
F2
F1{4}
F2
F1{2}
затем
F3
F2{2}
F3
F2{3}
и в итоге
F3{2}
на каждом шаге, когда принимается решение о слияние сравнивается только название функции (без учета кол-ва ее вызовов).
в данном случае, приведен многопроходный алгоритм - тоже самое можно делать за 1 проход с возратом, что дает сложность в два прохода
в примере, сворачиваются все похожие варианты, включая первый - при реальном применении первый вариант можно оставлять развернутым.
рекурсия сворачивается похожим образом, только вместо связи предыдущий-следующий используется связь родитель-ребенок
The high compression of LZMA comes fromПравильно, это две фазы алгоритма. Ищем повторения, как в LZ, сжимаем информацию о них арифметиком с контекстным моделированием (markov models). В простом zip'е на второй фазе простой хаффман. Отличий, конечно больше, но суть такова, насколько я помню.
combining two basic, well-proven compression ideas: sliding dictionaries
(LZ77/78) and markov models
А вот это хорошо, да.
И словарь там не такой маленький. Из мануала xz:
-9 64 MiB 6 674 MiB 65 MiB
А вот это хорошо, да.Ну и ключом можно ещё больше сделать, как я уже сказал. Так же ещё я упоминал rzip и lrzip — они могут на гораздо большем расстоянии повторения искать. Вот со страницы rzip:
The principal advantage of rzip is that it has an effective history buffer of 900 Mbyte.rzip правда в режиме трубы работать не умеет, хотя lrzip вроде умеет, но он по моим замерам хуже по времени/степени сжатия.
выложи уже наконец кусок своего файла
Оставить комментарий
AE169
Дан большой файл - 5-6 гигабайт. Какой алгоритм можно использовать чтобы оптимально по времени и памяти найти несколько самых повторяющихся подпоследовательностей? Смысл в том, что за время работы программы собирается ее трасса, которая набирает объем в 5-6 гигабайт минут за 10, а ПО надо гонять часами - хочется исключить из трассировки самые повторяющиеся циклы.