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

Question

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

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

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

• 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 #) или распространенные практики?

Спасибо

Обновление У меня есть несколько потрясающих модулей Perl, но я хотел бы получить интерфейсное решениетакже.Это означает, что 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 строит ветвящуюся структуру данных из шаблонов с частями, общими для альтернатив:

 $ 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\."...