#алгоритм #регулярные_выражения
Есть два набора строк.
Белый список:
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
Ответы
Ответ 1
Возможно получение двух решающих паттернов: по попаданию в белый список (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 Проверка показала, что все паттерны работают. Схема с полным "жадным" перебором дала такие же результаты.Ответ 2
Ответ: /ag|c[de]|dc|fe|g[df]|aa[dj]|ab[cf]|b[aeh]{2}|bjb|cij|a{9}/ Проверка: var W=['bhdgffhfa','aggjjaaga','hbefebhfi','dbceeabih','ihifdbhhf','djacfjbae','ibjbeigac','jaffigdad','aaaaaaaaj','dgifecchi','dcbhgjaaf','eedfbcedb','aaaaaaabf','beaajbihg','aaaaaaaag','eacccdjeh','aaaaaaaad','hehcijfhc','aaaaaaaaa','aaaaaaabc','jfdhdeice'], B=['aaaaaaaai','ehigcbgjd','hgjdeajec','aaaaaaabe','haebgiggc','aaaaaaaba','aaaaaaaaf','bfjhehbcf','diieabefh','jhjcaeead','ifbjdgibf','dddbgcgai','bbcafhcif','hfjciccbi','fdbgidjdj','aaaaaaabb','jhdibgbfj','cfjbaijad','bhgjfacgi','ehhieihhh','abijjabda']; var text="ag|c[de]|dc|fe|g[df]|aa[dj]|ab[cf]|b[aeh]{2}|bjb|cij|a{9}", reg=new RegExp(text); document.write('Длина выражения
С границами - '+reg.toString().length) document.write('
Только символы - '+text.length) document.write('
Тесты
Из белого '+W.filter(e=>reg.test(e)).length+'/'+W.length) document.write('
Из черного '+B.filter(e=>reg.test(e)).length+'/'+B.length) Решение по шагам Первым делом определим алфавит: в задаче используются символы abcdefghij Регулярное выражение будет определять принадлежность по уникальным для списка кускам (токен). Списка два - белый W и черный B, я выбрал белый список, просто он первый. Попробуйте с черным, возможно там есть более короткое решение?). Токены сначала нужно найти. Сгенерируем 2, 3, 4-символьные множества: function set(lev,str){ //set(2) - "aa,ab, ... ,jh,ji,jj", строкой пока компактнее lev--; str=str||""; return "abcdefghij".split('').map(function(e){ return lev>0 ? set(lev,str+e) : str+e; }).join(); } //"aa","ab",...,"jjji","jjjj" - массив sets=[].concat(set(2),set(3),set(4)).join().split(',') Для каждого токена определим, сколько раз он встречается в списках W и B. var freqs=sets.map(function(token){return { t:token, w:W.filter(function(e){return ~e.indexOf(token);}).length, b:B.filter(function(e){return ~e.indexOf(token);}).length };}); Определим список токенов, уникальных для W и не содержащих в себе меньших токенов uniq=freqs.filter(function(e){//берем уникальные для W return e.w>0 && e.b==0; }).filter(function(big,i,arr){//выкидываем избыточные - содержащие других return undefined==arr.find(function(small){//содержу ли другой, меньше и лаконичнее? return big.t.length>small.t.length && ~big.t.indexOf(small.t); }); }); //выводим списком с частотами - что одним выстрелом многих зайцев бьет? uniq.map(x=>x.t+'\t'+x.w).join('\n') //выводим через | для тестов в regex101.com и им подобных сервисах uniq.map(x=>x.t).join('|') Минимизация количества токенов. Берем http://regex101.com, белый и черный списки, полученную регулярку x|y|...|z и по одному пробуем убирать токены из регулярного выражения, следя за тем, чтобы в белом списке в каждом элементе был найден хотя бы один токен. Для особых случаев вписываем токен руками (пример - a{9}) Оптимизация символов. Имеем регулярное выражение, покрывающее белый список, но: Некоторые токены отличаются символами в одной позиции. XX: cd|сe можно превратить в c[de]. Польза = -1|-1c+2[] = 0 (полезна при похожести больше чем 2 токенов) XXX: aad|aaj превращаем в aa[dj]. Польза = -1|-2a+2[] = -1 символ Некоторые токены отличаются символами в двух позициях. XXX: bae|bea|bhh - b[aeh]{2}. Тут мы разширяем список токенов и это опасно. Но нам повезло и токены baa|bee|bah|beh|bha|bhe отсутствуют в черном списке, и эта расширяющая не сломает результат. Польза = -2|-2b-3eah+2[]+3{2} = -2 символа P.S: Теоретически, поиск похожих, формирование замен и проверку списка-антогониста можно бы автоматизировать с помощью алгоритма Левинштейна (как в Word - похожие слова) и кластеризации, но мне было влом и количество токенов не такое уж большое для ручного, творческого процесса
Комментариев нет:
Отправить комментарий