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

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


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

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


27/04/09
28128
Можно попытаться построить конечный автомат (из которого потом получают регулярное выражение, но раз оно не нужно, можно дальше и не идти). Но дальше всё равно применимо то, что отметил 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
28128
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
9426
Вот только конечный автомат должен быть без циклов, так как длины всех строк в множестве конечны. То есть, это должен быть недетерминированный направленный ациклический граф. Очевидно, его можно построить, добавляя принимаемые автоматом цепочки по одной путём довешивания простой цепи между какими-то парами вершин в существующем графе, соответствующих префиксу и суффиксу добавляемой новой цепочки, без потери графом свойства ацикличности. Возможно, даже, что если строить от более длинных цепочек к более коротким и довешивать всегда самую короткую промежуточную цепочку, то построенный граф окажется единственным и оптимальным по какому-нибудь критерию. Но исследовать эту задачу глубоко мне сейчас лень.

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


05/09/16
11461
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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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