Страницы

Поиск по вопросам

четверг, 1 ноября 2018 г.

Регулярное выражение различающее из какого набора строка

Есть два набора строк. Белый список:
bhdgffhfa aggjjaaga hbefebhfi dbceeabih ihifdbhhf djacfjbae ibjbeigac jaffigdad aaaaaaaaj dgifecchi dcbhgjaaf eedfbcedb aaaaaaabf beaajbihg aaaaaaaag eacccdjeh aaaaaaaad hehcijfhc aaaaaaaaa aaaaaaabc jfdhdeice
И черный список:
aaaaaaaai ehigcbgjd hgjdeajec aaaaaaabe haebgiggc aaaaaaaba aaaaaaaaf bfjhehbcf diieabefh jhjcaeead ifbjdgibf dddbgcgai bbcafhcif hfjciccbi fdbgidjdj aaaaaaabb jhdibgbfj cfjbaijad bhgjfacgi ehhieihhh abijjabda
Нужно написать регулярное выражение, не длинее 60 символов, способное различать из какого набора взята строка. Например, если на входе программе дано aaaaaaaaa, программа должна решить, что это строка из белого списка.
UPDATE: https://www.hackerrank.com/contests/regular-expresso/challenges/match-maker


Ответ

Возможно получение двух решающих паттернов: по попаданию в белый список (whitelist) и в чёрный список (blacklist).
Паттерн белого списка: /ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa/ Паттерн чёрного списка: /bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf/
Паттерн чёрного списка короче и допускает сжатие до 37 символов: /ai|b[bdg]|cg|ie|j[cdh]|ab[ae]|a{8}f/ Но использование двух паттернов позволяет провести диагностику.
Решающие паттерны набираются из уникальных для соответствующего списка токенов по оптимизированному "жадному" алгоритму.
К рассмотрению приняты двух- и трёхсимвольные токены, а также 9-символьные токены, начинающиеся с "aaaaaaa".
Программа на языке PHP:
$whitelist = " bhdgffhfa aggjjaaga hbefebhfi dbceeabih ihifdbhhf djacfjbae ibjbeigac jaffigdad aaaaaaaaj dgifecchi dcbhgjaaf eedfbcedb aaaaaaabf beaajbihg aaaaaaaag eacccdjeh aaaaaaaad hehcijfhc aaaaaaaaa aaaaaaabc jfdhdeice ";
$blacklist = " aaaaaaaai ehigcbgjd hgjdeajec aaaaaaabe haebgiggc aaaaaaaba aaaaaaaaf bfjhehbcf diieabefh jhjcaeead ifbjdgibf dddbgcgai bbcafhcif hfjciccbi fdbgidjdj aaaaaaabb jhdibgbfj cfjbaijad bhgjfacgi ehhieihhh abijjabda ";
//Генератор решающих токенов function tokens_gen($whitelist, $blacklist){ $white_tokens = []; $black_tokens = []; for($i=-1; $i< 12; $i++){ $c = ($i<0) ? "" : chr(ord("a")+$i); // сначала двухсимвольные токены $c = ($i==10) ? "aaaaaaa" : $c; // последними - токены c "aaaaaaa" for($ord2=ord("a"); $ord2 <= ord("j"); $ord2++){ for($ord3=ord("a"); $ord3 <= ord("j"); $ord3++){ $ccc = $c.chr($ord2).chr($ord3); $pm_white = preg_match("/$ccc/", $whitelist); $pm_black = preg_match("/$ccc/", $blacklist); if(($pm_white==1) && ($pm_black==0)) array_push($white_tokens, $ccc); if(($pm_black==1) && ($pm_white==0)) array_push($black_tokens, $ccc); } } } return [$white_tokens, $black_tokens]; }
// "Жадный" рекурсивный отбор токенов function greedy($tokens, $list, $pat=""){ $tokens_new = []; $ppp_max = ""; foreach($tokens as $ppp){ $p = ($pat=="")? $ppp: "$pat|$ppp"; $sum = 0; foreach($list as $str) $sum += preg_match("/$p/", $str); if($sum > $sum_max){ $ppp_max = $ppp; $sum_max = $sum; } if($sum > 0) array_push($tokens_new, $ppp); } if($ppp_max == "") return $pat; $pat = ($pat=="")? $ppp_max: "$pat|$ppp_max"; $left = 'display: block; float: left; '; printf("Токенов:%d", count($tokens)); printf(" Строк, всего:%d по токену: $sum_max ", count($list)); print("Токен: $ppp_max   Паттерн: $pat
"); $list = preg_grep("/$ppp_max/", $list, PREG_GREP_INVERT); $pat = greedy($tokens_new, $list, $pat); return $pat; }
// Перевод контрольных строк в массивы $white = explode(chr(10), trim($whitelist)); foreach($white as &$w) $w=trim($w); $black = explode(chr(10), trim($blacklist)); foreach($black as &$b) $b=trim($b); $white_black = array_merge($white, $black);
// Получение решающих токенов list($white_tokens, $black_tokens) = tokens_gen($whitelist, $blacklist);
// Получение жадных паттернов print("Жадные паттерны:

"); $white_pattern = greedy($white_tokens, $white); $black_pattern = greedy($black_tokens, $black); //$black_pattern = 'ai|b[bdg]|cg|ie|j[cdh]|ab[ae]|a{8}f'; print("

white_pattern = $white_pattern
black_pattern = $black_pattern
");
$left = 'display: block; float: left; '; print("
Проверка:
"); foreach($white_black as $str){ $in_white = preg_match("/$white_pattern/",$str); $in_black = preg_match("/$black_pattern/",$str); print("
$str:$in_white $in_black"); }
Результаты:
Жадные паттерны:
Токенов:108 Строк, всего:21 по токену: 3 Токен: ce   Паттерн: ce Токенов:108 Строк, всего:18 по токену: 2 Токен: ag   Паттерн: ce|ag Токенов:88 Строк, всего:16 по токену: 2 Токен: fe   Паттерн: ce|ag|fe Токенов:81 Строк, всего:14 по токену: 2 Токен: ff   Паттерн: ce|ag|fe|ff Токенов:67 Строк, всего:12 по токену: 2 Токен: aaj   Паттерн: ce|ag|fe|ff|aaj Токенов:49 Строк, всего:10 по токену: 1 Токен: cd   Паттерн: ce|ag|fe|ff|aaj|cd Токенов:41 Строк, всего:9 по токену: 1 Токен: dc   Паттерн: ce|ag|fe|ff|aaj|cd|dc Токенов:33 Строк, всего:8 по токену: 1 Токен: aad   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad Токенов:28 Строк, всего:7 по токену: 1 Токен: abc   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc Токенов:26 Строк, всего:6 по токену: 1 Токен: abf   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf Токенов:24 Строк, всего:5 по токену: 1 Токен: acf   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf Токенов:22 Строк, всего:4 по токену: 1 Токен: bei   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei Токенов:18 Строк, всего:3 по токену: 1 Токен: bhh   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh Токенов:11 Строк, всего:2 по токену: 1 Токен: cij   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij Токенов:5 Строк, всего:1 по токену: 1 Токен: aaaaaaaaa   Паттерн: ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa Токенов:118 Строк, всего:21 по токену: 5 Токен: bg   Паттерн: bg Токенов:118 Строк, всего:16 по токену: 2 Токен: ai   Паттерн: bg|ai Токенов:82 Строк, всего:14 по токену: 2 Токен: bb   Паттерн: bg|ai|bb Токенов:75 Строк, всего:12 по токену: 2 Токен: ie   Паттерн: bg|ai|bb|ie Токенов:67 Строк, всего:10 по токену: 2 Токен: jc   Паттерн: bg|ai|bb|ie|jc Токенов:53 Строк, всего:8 по токену: 2 Токен: jd   Паттерн: bg|ai|bb|ie|jc|jd Токенов:37 Строк, всего:6 по токену: 1 Токен: bd   Паттерн: bg|ai|bb|ie|jc|jd|bd Токенов:24 Строк, всего:5 по токену: 1 Токен: cg   Паттерн: bg|ai|bb|ie|jc|jd|bd|cg Токенов:18 Строк, всего:4 по токену: 1 Токен: jh   Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh Токенов:12 Строк, всего:3 по токену: 1 Токен: aba   Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba Токенов:5 Строк, всего:2 по токену: 1 Токен: abe   Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe Токенов:3 Строк, всего:1 по токену: 1 Токен: aaaaaaaaf   Паттерн: bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf
white_pattern = ce|ag|fe|ff|aaj|cd|dc|aad|abc|abf|acf|bei|bhh|cij|aaaaaaaaa black_pattern = bg|ai|bb|ie|jc|jd|bd|cg|jh|aba|abe|aaaaaaaaf
Проверка:
bhdgffhfa:1 0 aggjjaaga:1 0 hbefebhfi:1 0 dbceeabih:1 0 ihifdbhhf:1 0 djacfjbae:1 0 ibjbeigac:1 0 jaffigdad:1 0 aaaaaaaaj:1 0 dgifecchi:1 0 dcbhgjaaf:1 0 eedfbcedb:1 0 aaaaaaabf:1 0 beaajbihg:1 0 aaaaaaaag:1 0 eacccdjeh:1 0 aaaaaaaad:1 0 hehcijfhc:1 0 aaaaaaaaa:1 0 aaaaaaabc:1 0 jfdhdeice:1 0 aaaaaaaai:0 1 ehigcbgjd:0 1 hgjdeajec:0 1 aaaaaaabe:0 1 haebgiggc:0 1 aaaaaaaba:0 1 aaaaaaaaf:0 1 bfjhehbcf:0 1 diieabefh:0 1 jhjcaeead:0 1 ifbjdgibf:0 1 dddbgcgai:0 1 bbcafhcif:0 1 hfjciccbi:0 1 fdbgidjdj:0 1 aaaaaaabb:0 1 jhdibgbfj:0 1 cfjbaijad:0 1 bhgjfacgi:0 1 ehhieihhh:0 1 abijjabda:0 1

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

Комментариев нет:

Отправить комментарий