2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 10:25 


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

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

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

Код:
assssbsssbcasssbsssbsssb
sssb
sssbssssb
fssssbcasssb


И получить что-нибудь вроде
Код:
f?((a?s{3,4}b)c?)+


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

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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 11:50 


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 12:55 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 17:58 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 20:30 


09/04/17
5
arseniiv в сообщении #1207934 писал(а):
Можно попытаться построить конечный автомат (из которого потом получают регулярное выражение


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

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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение09.04.2017, 20:38 
Заслуженный участник
Аватара пользователя


27/04/09
21250
Уфа
vladimir-vg в сообщении #1208026 писал(а):
А как именно его построить?
Недетерминированный очень просто — это будет аналог вот этого:
slavav в сообщении #1207825 писал(а):
все строки объединить в одно регулярное выражение через '|'
Из стартового состояния будут ε-переходы к цепочкам состояний, по каждой из которых можно попасть в отдельное принимающее состояние, прочитав строку (и выйти из него куда-нибудь навсегда, если есть символы и дальше).

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

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

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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение10.04.2017, 23:13 


09/04/17
5
У меня пока нет конкретных примеров данных.

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение13.04.2017, 14:43 


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение13.04.2017, 17:29 


05/09/16
2203
vladimir-vg в сообщении #1208026 писал(а):
На вход подаётся сотня достаточно длинных строк с непредсказуемым содержимым. Как выявить общие части, организовать их в автомат?

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

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

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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение16.04.2017, 11:18 


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение16.04.2017, 12:27 


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

 Профиль  
                  
 
 Re: Нахождение регулярного выражения для последовательностей
Сообщение16.04.2017, 13:32 


19/05/10

3940
Россия

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: volchenok


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group