По словам нейробиолога Майкла Мерзенича, наш мозг изучает языки в двух разных режимах, в зависимости от когда мы их изучаем: родные языки, т. Е. Языки, изученные в детстве, обрабатываются одним и тем же регионом в мозг, в то время как вторые языки, т. е. языки, которые мы изучаем во взрослом возрасте, сопоставляются с другими областями мозга, отличными от области, ответственной за наши родные языки. Другими словами, родные языки разделяют вычислительные ресурсы (то есть нейроны), в то время как вторые языки требуют дополнительного пространства в мозгу (буквально).
Давайте проведем совершенно ненаучную аналогию с формальными языками. Язык является регулярным тогда и только тогда, когда он соответствует регулярному выражению, или, что то же самое, если он принимается конечным автоматом. Таким образом, говорить на обычном языке означает хранить соответствующее регулярное выражение или автомат. Говорить на втором языке означает хранить второе регулярное выражение или автомат… Или нет?
Давайте попробуем выучить обычный язык для наименования животных. Сначала я выучил слово и регулярное выражение cat. Далее я выучу слово dog. Регулярные выражения закрываются объединением, и теперь я говорю на простом животном языке cat|dog. В конце концов, я могу назвать всех животных: animals ≡ cat|dog|horse|.... Теперь давайте узнаем о головных уборах: headgear ≡ cap|hat|scarf|.... Опять же, поскольку регулярные выражения закрыты объединением, теперь я могу говорить о животных и головных уборах: animals|headgear = cat|dog|horse|...|cap|hat|scarf|.... Набросок недетерминированного автомата (NFA), эквивалентного регулярному выражению, показан на скетче выше.
В приведенной выше конструкции каждое новое слово, которое я выучиваю, требует линейно больше места для хранения регулярного выражения или NFA: они просто продолжают расти по мере того, как выучите новые слова. Это аналогично наблюдению Мерзениха в отношении второго языка: вторые языки занимают области мозга, отличные от родного языка. Вы также заметите, что вычислительная сложность (т. Е. Необходимость «говорить» на языке) этой конструкции ужасна; наивная реализация объединения регулярных выражений:
function isAnimalOrHeadgear(word):
for regex in {cat, dog, horse, ..., cap, hat, scarf, ...}:
if regex.matches(word):
return true
return false
Как и человеческий мозг, регулярные выражения могут работать лучше.
Во-первых, мы можем превратить недетерминированный автомат в детерминированный автомат (ДКА), изображенный слева. Вы заметите, что в DFA меньше состояний, и это сокращение достигается за счет совместного использования некоторых состояний DFA (здесь: C, A) в разных словах. С точки зрения аналогии с естественным языком это можно интерпретировать как заданный набор нейронов, распознающих похожие звуки на разных языках.
Во-вторых, мы можем минимизировать DFA, чтобы получить наименьший возможный DFA, о котором говорит animals|headgear. Компромисс вычислительной сложности заключается между временем компиляции (или изучением языка) и временем выполнения (говорением на языке): минимизация NFA (т. Е. Процесс получения списка регулярных выражений и создания минимального DFA) представляет собой сложную задачу даже для приближенных решений, но часто ее можно решить в автономном режиме, что дает более быстрый автомат для сопоставления выражений. Аналогия с естественным языком на данный момент - всего лишь спекуляция ... мне кажется правдоподобным, что то, что сложно для машин Тьюринга (то есть минимизировать NFA), сложно для вычислений на основе нейронов: в модели конкурентной пластичности кажется легче новому языку захватить другую область мозга, чем адаптировать (интенсивно используемую) область родного языка для нового языка? (Интересно, что этот эффект конкурирует с основополагающим утверждением Хебба,« что сгорает вместе, соединяет вместе », подразумевая, что вторые языки предпочли бы совмещаться в картах мозга родных языков, но они просто не могут их превзойти?) < br />
Чтобы проиллюстрировать оптимизацию регулярных выражений на практике, давайте рассмотрим реальный пример. Используя приведенный ниже код (и библиотеку автоматов Андерса), список из 50 регулярных выражений для сопоставления строк журнала etcd компилируется в 50 минимальных DFA с общим 1744 состояниями или в один минимизированный DFA с 1079 состояниями.
// List of regular expressions to match etcd log lines
(authorized )(.+)(, token is )(.+)
(user )(.+)( is already granted role )(.+)
(failed to unmarshal user struct \(name: )(.+)(\): )(.+)
(failed to unmarshal user struct: )(.+)
(failed to marshal user struct \(name: )(.+)(\): )(.+)
(failed to unmarshal role struct \(name: )(.+)(\): )(.+)
(failed to unmarshal role struct: )(.+)
(failed to marshal role struct \(name: )(.+)(\): )(.+)
(Use default bcrypt-cost )(.+)( instead of the invalid value )(.+)
(ignoring common name in gRPC-gateway proxy request )(.+)
(found common name )(.+)
(invalid auth token: )(.+)
(simple token is not cryptographically signed)
(tried to check user )(.+)( has role )(.+)(, but user )(.+)( doesn't exist)
(token )(.+)( is already used)
(deleting token )(.+)( for user )(.+)
(unknown auth type: )(.+)
(unknown auth type: )(.+)
(failed to parse jwt token: )(.+)
(invalid jwt token: )(.+)
(failed to sign jwt token: )(.+)
(jwt token: )(.+)
(unknown JWT options: )(.+)
(rejected connection from )(.+)( \(error )(.+)(, ServerName )(.+)(, IPAddresses )(.+)(, DNSNames )(.+)(\))
(rejected connection from )(.+)( \(error )(.+)(, ServerName )(.+)(\))
(ignoring client auto TLS since certs given)
(ignoring peer auto TLS since certs given)
(couldn't parse log level string: )(.+)(, continuing with default levels)
(serving client requests on )(.+)
(rejecting HTTP request from )(.+)( to prevent DNS rebinding attacks)
(path )(.+)( already registered by user handler)
(name = )(.+)
(force new cluster)
(data dir = )(.+)
(member dir = )(.+)
(dedicated WAL dir = )(.+)
(heartbeat = )(.+)(ms)
(election = )(.+)(ms)
(snapshot count = )(.+)
(discovery URL= )(.+)
(discovery proxy = )(.+)
(advertise client URLs = )(.+)
(initial advertise peer URLs = )(.+)
(initial cluster = )(.+)
(could not get certs \()(.+)(\))
(peerTLS: )(.+)
(The scheme of peer url )(.+)( is HTTP while peer key/cert files are presented\. Ignored peer key/cert files\.)
(The scheme of peer url )(.+)( is HTTP while client cert auth \(--peer-client-cert-auth\) is enabled\. Ignored client cert auth for this url\.)
(could not get certs \()(.+)(\))
(pprof is enabled under )(.+)
public class Main {
public static void main(String[] args) {
Path file = Paths.get("regexes.txt");
// Library: https://www.brics.dk/automaton/
Automaton combined = new Automaton();
int sumOfStates = 0;
String line = "";
try (BufferedReader reader = Files.newBufferedReader(file)) {
while ((line = reader.readLine()) != null) {
Automaton automaton = new RegExp(line).toAutomaton();
sumOfStates += automaton.getNumberOfStates();
combined = combined.union(automaton);
}
} catch (Exception e) {
System.out.println("Failed: " + line + " : " + e);
System.exit(0);
}
System.out.println("Sum of the number of states of the per-regex automata: " + sumOfStates);
combined.minimize();
System.out.println("Number of states of the combined and minimized automaton: " + combined.getNumberOfStates());
}
}
