Data mining

google://longest common substring ?

К сожалению, сложность текущего алгоритма растёт пропорционально квадрату строк. Как подобное написать без квадратичной зависимости?

Ты бы хоть детали текущего алгоритма привел для начала.

Да, сейчас ищу через эти них. Проблема в том, чтобы найти вайлдкарды, мне нужно найти LCS для N*N строк, а это очень долго для больших объёмов (22 секунды уже на пятистах строках).

Вот код: http://disarmer.ru/ln/?1E

функция s2r - построение общего вайлдкарда для двух строк

Вкратце, читаю весь stdin в массив, потом прохожу по нему в двойном цикле для нахождения общих вайдкардов(отсюда и квадратичная сложность). Записываю найденные общие строки в ассоциативный массив с количеством повторов. Потом сортирую по количеству повторов и длине вайдкарда и вывожу

На ум приходит введение какой-нибудь метрики на основе расстояния Левенштейна или около того, либо построение radix tree для всех известных строк и анализ его

А такое дерево сможет мне помочь, в чём-то кроме как подсчёте LCS? http://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree

1) по тобой же приведенной ссылке указана оценка сложности алгоритма.

2) если ты анализируешь что то такое как привел, то сохранение кеша мемоизированной функции извлечения общей части строк возможно даст ускорение в заполнении матрицы сравнений

указана оценка сложности алгоритма.

Там же оценка сложности нахождения общей подстроки, у меня задача шире - по этим подстрокам найти наиболее общие. Здесь то и получается квадратичная сложность, потому что кроме как перебора всех со всеми, я не знаю алгоритма.

сохранение кеша мемоизированной функции извлечения общей части строк

Проверил, стало дольше(25 секунд против 22). Оно и понятно - ведь в эту функцию передаются неповторяющиеся аргументы

А такое дерево сможет мне помочь, в чём-то кроме как подсчёте LCS?

Да в нем же все что нужно и будет? Все наиболее длинные подстроки, с количеством вхождений.

Там в статье как-то слишком уж адово изобразили суффиксное дерево, вот здесь http://en.wikipedia.org/wiki/Suffix_tree все нормально описано.

Суффиксные деревья легко программировать, идеи очень простые. Единственная неприятность - они требуют неприлично много памяти. Можно получить дерево порядка на 2 объемнее, чем исходные данные. Ну, если данных сотни килобайт, нормально.

Не знаю, насколько это годится именно для строк, но для майнинга линейных паттернов применяется Apriori algorithm http://en.wikipedia.org/wiki/Apriori_algorithm

его расширения Partitioning, Apriori pruning и масштабируемые алгоритмы Eclat, FPgrowth

Да, подстроки из дерева можно извлечь, я легко смогу найти количество упоминаний например /usr/bin/t*, но как найти вайлдкарды с звёздочкой в середине, вроде /usr/bin/*-config?

Данных обычно немного, до десятка тысяч строк, в крайнем этого хватит для репрезентативной выборки. Ну и tradeoff в сторону памяти выгоднее, время выполнения важнее.

Пока не вижу как применить к этой задаче, разве что учитывать связи между подстроками, но тут надо экспериментировать.

А в machine learning нет никаких готовых утилит для поиска закономерностей в тексте такого типа?

ML это немного другая область. У тебя именно Data mining. Я этим не занимался, посоветовать готовое решение не могу. Но задача типичная, поэтому можно искать так:
frequent Pattern Mining in Web Log Data
frequent pattern mining text/strings
sequential pattern mining

Вот что-то попалось:
http://www.philippe-fournier-viger.com/spmf/
http://stackoverflow.com/questions/19775978/fuzzy-pattern-search-in-a-string-...

Спасибо, spmf интересно выглядит, надо посмотреть

как найти вайлдкарды с звёздочкой в середине, вроде /usr/bin/*-config?

Да, для такого, наверное, суффиксные деревья не помогут.

Тогда более правильная ссылка - http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

А какая конечная цель этого? Что нужно получить?

Я из любопытства сделал руками поиск наибольшей общей подпоследовательности и прогнал так же как и ты попарно названия файлов из /usr/bin/:

$ find /usr/bin/ | wc -l
1703
$ time find /usr/bin/ | ./a.out >/dev/null

real	0m3.720s
user	0m3.720s
sys	0m0.004s

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

Вот код (на С++): https://gist.github.com/vmxdev/a795aa4a9b6d60896b9d/ , там главное это функция wildcard, пытается найти в двух строках максимально похожее и сгенерировать из этого шаблон со звездочками

Спасибо, сишный код намного быстрее работает, но результат странный, попробую настроить вывод до похожего

Longest_common_subsequence_problem

Я посмотрел внутрь модуля, оказывается мой алгоритм как раз последовательности ищет, а не подстроки

А какая конечная цель этого? Что нужно получить?

Попытаться получить наиболее частовстречающиеся шаблоны строк для первичного анализа. Например для анализа более-менее однообразных логов или списков файлов. Отфильтровать незначимые(вроде /usr/bin/*r*e*) можно по длине шаблона

В идеале хочется получить что-то вроде такого, на примере лога nginx:

150   2014/12/* [error] 19460#0: * open() "/*" failed (2: No such file or directory), client: *, server: , request: "HEAD /* HTTP/1.1", host: "disarmer.ru"
40   2014/12/01 [error] 19460#0: * open() "/*" failed (2: No such file or directory), client: *, server: , request: "HEAD /* HTTP/1.1", host: "disarmer.ru"
20    2014/12/* [error] 19460#0: * connect() failed (111: Connection refused) while connecting to upstream, client: *, server: disarmer.ru, request: "GET /* HTTP/1.1", upstream: "http://*",

Один взгляд на результат такого фильтра избавит от десятков выполнения grep

для анализа более-менее однообразных логов или списков файлов. Отфильтровать незначимые(вроде /usr/bin/*r*e*) можно по длине шаблона

А-а. Ну, возможно я неправильно понимаю задачу, но попарным сравнением особо много не увидишь?

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

Да, мне кажется настраивать вывод в одну или другую сторону можно неким коэффициентом сортировки, увеличивающим вес длины строки:

15*length($a)+$pats{$a}

Это не совсем то, конечно, но достаточно близко и без изменения алгоритма