Max Home IndustryНедавний мультфильм xkcd положил начало глубокому академическому мышлению. Когда в дело вмешивается эксперт по ИИ Питер Норвиг, вы знаете, что алгоритмы будут работать.
Xkcd — наш любимый комикс, а регулярные выражения-определенно наш любимый способ провести время в ожидании следующей части-так что что может быть лучше, чем мультфильм xkcd на Regex Golf.
Кодовый гольф — достаточно известный вид спорта, в котором пытаются закодировать алгоритм в максимально коротком коде. Regex Golf аналогичен, но в целом цель состоит в том, чтобы создать регулярное выражение, которое принимает строки в одном списке и отклоняет строки во втором списке.
Этого должно было быть достаточно, но ясно, что мы программисты, и нам нравится рекурсия, а регулярное выражение-это строка, в конце концов, и регулярное выражение может обрабатывать строку:
Кредит: xkcd
Да, мой друг, это регулярные выражения на всем пути вниз!
Достаточно умопомрачительно, но наведение курсора на текст, ключевая особенность многих шуток xkcd, — это то, где проблема действительно начинает подниматься и обретать свою собственную жизнь.
Текст дает регулярное выражение, которое соответствует фамилиям избранных президентов США, но не проигравших.
Это заставило Питера Норвига, известного ученого-компьютерщика, директора по исследованиям в Google и владельца ярких рубашек, задуматься над проблемой. Можно ли написать программу, которая создала бы регулярное выражение для решения проблемы xkcd?
Проблема заключается в одном уровне мета, то есть это программа, которая создает регулярное выражение, но это сложная программа, которая нуждается в методах поиска, подобных ИИ.
Основной алгоритм состоит в том, чтобы сначала получить пул регулярных выражений для коротких последовательностей символов в данных, которые соответствуют по крайней мере одному победителю, но не проигравшим. Затем создайте более крупное регулярное выражение, объединив несколько компонентов вместе. Варьируйте выбор до тех пор, пока не получите регулярное выражение, которое соответствует всем победителям, но ни одному из проигравших.
Это эквивалентно задаче покрытия множества и, следовательно, NP трудно.
Чтобы попытаться найти наименьшее регулярное выражение, которое выполняет эту работу, самый простой приблизительный способ-использовать жадный выбор, который сначала выбирает регулярные выражения компонентов, максимально разделяющие два списка.
Отсюда алгоритм может быть улучшен путем добавления набора правил для генерации начального пула регулярных выражений.
Чтобы узнать больше, прочитайте полное описание, включая код Python, в блоге Питера Норвига, который заканчивается вызовом:
«Я надеюсь, что вы нашли это интересным, и, возможно, вы сможете найти способы улучшить мой алгоритм или более интересные списки, чтобы применить его. Я нашел, что с этим было весело играть, и я надеюсь, что эта страница даст вам представление о том, как решать подобные проблемы.»
Или, конечно, вы можете перенести проблему на еще один этап meta, например, meta-meta-regexgolf — программа, которая пишет программы, которые пишут регулярные выражения….
Если вы хотите играть в гольф с регулярными выражениями, с помощью программы или без нее, посетите: http://regex.alf.nu/