Упрощение регулярных выражений ИЛИ шаблонов

Question

Меня спросили сегодня, есть ли библиотека, чтобы взять список строк и вычислить наиболее эффективное регулярное выражение для соответствия только этим строкам. Я думаю, что это NP Complete problem сам по себе, но я думаю, что мы можем немного доработать область.

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

Первый шаг очень прост. Из следующего списка;

• appserver1.domain.tld
• appserver2.domain.tld
• appserver3.domain.tld

я могу сцепить и избежать их в

appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\.domain\.tld 

И я знаю, как вручную упростить регулярное выражение до

appserver[123]\.domain\.tld 

Оттуда я могу проверить этот шаблон на весь список хостов и убедиться, что он соответствует только выбранным 3 хостам. Я не знаю, как автоматизировать процесс упрощения. Существуют ли библиотеки (в Perl, Javascript или C#) или обычные методы?

Благодаря

Update я получил некоторые удивительные модули Перла, но я хотел бы передний конец решения, а также. Это означает Javascript. Я искал, но никто не портировал модули perl в JS, и я не смог найти язык для поиска этого типа библиотеки.

Answer 1

Regexp::Assemble::Compressed/Regexp::Assemble знаю гораздо больше трюков, чем PreSuf. R::A поставляется с инструментом командной строки assemble (не установлен по умолчанию), что упрощает создание регулярных выражений.

Answer 2

Модуль Regex::PreSuf предназначен для этого.

Цитирую Сводка:

use Regex::PreSuf; 

my $re = presuf(qw(foobar fooxar foozap)); 

# $re should be now 'foo(?:zap|[bx]ar)' 

Answer 3

Регулярное выражение компилятор Perl строит разветвление TRIE структуру данных из моделей с частями общего по альтернативам:

$ perl -Mre=debug -ce '"whatever" =~ /appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\.domain\.tld/' 
Compiling REx "appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\."... 
Final program: 
    1: EXACT <appserver> (5) 
    5: TRIEC-EXACT[123] (25) 
     <1.domain.tld> 
     <2.domain.tld> 
     <3.domain.tld> 
    25: END (0) 
anchored "appserver" at 0 (checking anchored) minlen 21 
-e syntax OK 
Freeing REx: "appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\."...