Нахождение регулярного выражения для последовательностей

[vladimir-vg]

Имею алфавит, где-то 20 знаков.
Имею набор последовательностей (около сотни), в которых используются символы из алфавита.
Длина последовательности может достигать тысячи символов.

Как обработать последовательности, и получить регулярное выражение (или что-то похожее на него) для этих последовательностей?

Т.е. есть это:

assssbsssbcasssbsssbsssb
sssb
sssbssssb
fssssbcasssb

И получить что-нибудь вроде

f?((a?s{3,4}b)c?)+

Само регулярное выражение мне не нужно, нужна какая-то выходная структура (граф?) после обработки, гуляя по которой можно понять приблизительно из каких частей состоит последовательность.

Подскажите какие-нибудь ключевые слова, темы, которые могут быть связаны с решением такой задачи.

[slavav]

Есть тривиальный способ: все строки объединить в одно регулярное выражение через '|'. Думаю что вам оно не подходит. Вы ведь хотите не слишком длинное регулярное выражение? Могу предложить '.*'. Но и оно вам не подойдёт. Слишком много ложных срабатываний.
Уточните, пожалуйста, задачу, чтобы исключить эти два крайних случая.

[iifat]

Помнится, среди систем автоматической генерации алгоритмов было направление обучения на примерах. То бишь, на входе несколько примеров вычисления, на выходе — алгоритм с циклами, условными операторами и т.д. Увы, никаких ключевых слов и названий не знаю.

[arseniiv]

Можно попытаться построить конечный автомат (из которого потом получают регулярное выражение, но раз оно не нужно, можно дальше и не идти). Но дальше всё равно применимо то, что отметил slavav — с конечным автоматом никакой разницы, можно нарисовать сразу принимающий что угодно, а можно опять же сразу же нарисовать такой, который принимает только то, что есть. Хотя потом его можно попытаться упростить… (и делать это вроде бы проще, чем с регэксом). В любом случае упрощение может дать не то, что хотелось бы, из-за возможного оверфиттинга (даны не все строки интересующего языка).

[vladimir-vg]

arseniiv в сообщении #1207934 писал(а):

Можно попытаться построить конечный автомат (из которого потом получают регулярное выражение

А как именно его построить? На вход подаётся сотня достаточно длинных строк с непредсказуемым содержимым. Как выявить общие части, организовать их в автомат?

Нашёл что-то похожее тут, но всё равно пока непонятно до конца: http://www.cs.rhul.ac.uk/home/alexc/sli ... aTrier.pdf
А соседние статьи того же автора пока не осилил, не хватает мозгов понять, решают они мою проблему или нет.

[arseniiv]

vladimir-vg в сообщении #1208026 писал(а):

А как именно его построить?

Недетерминированный очень просто — это будет аналог вот этого:

slavav в сообщении #1207825 писал(а):

все строки объединить в одно регулярное выражение через '|'

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

Однако «упрощать» автомат на самом деле можно по-разному в зависимости от того, что надо. Минимизация числа состояний, например, не факт что вам нужна. Потом, одно дело — НКА, а другое — ДКА.

-- Вс апр 09, 2017 22:44:51 --

Вы лучше всё-таки поделитесь тем, полностью задаётся данным набором строк интересующий язык или нет, ну и было бы неплохо, если можно было бы получить представление о том, какая возможная структура в последовательностях ищется.

[vladimir-vg]

У меня пока нет конкретных примеров данных.

[realeugene]

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

[wrest]

vladimir-vg в сообщении #1208026 писал(а):

На вход подаётся сотня достаточно длинных строк с непредсказуемым содержимым. Как выявить общие части, организовать их в автомат?

Ровно этим занимаются программы-архиваторы (zip tar rar и т.п.), с тем или иным успехом.
Ищут повторяющиеся части, составляют их (таких частей) словари и т.п.

Соответственно, вам наверное нужен какой-то разборщик формата (.zip .tar и т.п.) который покажет вам словари, графы и т.п.

Поскольку есть opensource архиваторы, то полагаю что можно подсмотреть там.

[vladimir-vg]

Похоже то что мне нужно называется https://en.wikipedia.org/wiki/Sequential_pattern_mining

[vladimir-vg]

А вот и специалист который на этом собаку съел: http://wwwis.win.tue.nl/~wvdaalst/

[mihailm]

(Оффтоп)

ТС напомнил анекдот:
Мужик ночью в аптеку ломится. После пяти минут стука вылазит аптекарь "Ну что надо?" - "Скрепки есть?" - "Какие скрепки? Нет конечно!".
Через час вновь стук - "Держите, я вам скрепки принес!"