В моей среде Lua 5.1, очевидно, есть сопоставление шаблонов Lua по умолчанию, а также достаточно свежие версии PCRE и LPEG. Честно говоря, мне все равно, какой из них используется; пока моя проблема решается эффективным образом, я счастлив. (Мое личное знание LPEG особенно близко к нулю, но я слышал, что у него есть некоторые очень хорошие качества.)
У меня есть таблица с определенными шаблонами строк в качестве ключей, сопутствующие значения должны использоваться после совпадения ключей... что означает, что они не очень важны в этом вопросе.
Предположим, у вас есть:
tbl = { ["aaa"] = 12, ["aab"] = 452, ["aba"] = -2 }
Теперь моя цель — выяснить, какое из этих совпадений первым встречается в конкретной строке, например "accaccaacaadacaabacdaaba".
На самом деле ключей больше, а строка совпадения значительно длиннее. Это означает, что простое сопоставление со всеми ключами один за другим и сравнение столбца, с которого начинается совпадение, является очень неэффективным решением, которое мне не подходит.
Части совпадающих строк также могут иметь значительные перекрытия. Из теории я знаю, что один конечный автомат на шаблон ключа был бы идеальным в этом отношении; просто выполняйте движения на каждом шаблоне, и в тот момент, когда у вас есть полное совпадение на одном из них, все готово.
Но я был бы сумасшедшим, если бы сам написал что-то подобное, когда в моей среде так много библиотек сопоставления с образцом. Насколько я знаю, единственное, что технически способно, — это PCRE; просто добавьте ключи, такие как "aaa|aab|aba", и вы получите первое возможное совпадение.
Но есть и проблема. Во-первых, я не уверен, насколько разумно составлять такое совпадение. (Я думаю, что сначала он пытается «ааа», полностью раскручивается после сбоя, затем полностью пытается использовать aab, но я не проверял), что было бы не слишком эффективно по сравнению с сопоставлением, например "a(a[ab]|ba)", где сходства разрешаются быстрее.
Кроме того, я хотел бы иметь возможность внести некоторую гибкость («a.ad», где второй символ не имеет значения или соответствует числу... такие базовые вещи). С таким шаблоном в таком аддитивном подходе я не вижу способа восстановить исходный шаблон, который совпал, чтобы я мог использовать значение, которое связано с ним.
(В худшем случае я мог бы просто сгенерировать множество записей в таблице, чтобы они соответствовали всем возможным вариантам подстановочных знаков, и покончить с требованием шаблона, но я, честно говоря, не хочу этого.)
Какая библиотека является подходящим инструментом для работы, и, кроме того, как лучше всего использовать эту библиотеку для достижения вышеуказанных целей, не изобретая велосипед?
