Как эффективно сопоставить ключи в таблице в Lua?

Question

Очевидно, что в моей среде Lua 5.1 доступно сопоставление с шаблоном Lua по умолчанию, а также относительно недавние версии PCRE и LPEG. Мне, честно говоря, все равно, какой из них используется; пока моя проблема решена эффективно, я счастлив. (Мои личные знания о LPEG особенно близки к тому, что их вообще нет, но я слышал, что у них есть некоторые очень хорошие качества.)

У меня есть таблица с определенными строковыми образцами в качестве ключей, сопровождающие значения должны использоваться, когда ключи совпадают... это означает, что они не очень важны для этого вопроса.

Предположим, у вас есть:

tbl = { ["aaa"] = 12, ["aab"] = 452, ["aba"] = -2 }

Теперь моя цель состоит в том, чтобы выяснить, какое из этих совпадений будет первым в определенной строке, например "accaccaacaadacaabacdaaba",

В действительности, ключи являются более многочисленными, а строка соответствия значительно длиннее. Это означает, что простое сопоставление всех ключей по одному и сравнение столбца, с которого начинается сопоставление, является очень неэффективным решением, которое для меня нецелесообразно.

Части совпадающих строк также могут иметь значительные совпадения. Исходя из теории, я знаю, что в этом отношении идеально подходит один конечный автомат для каждого ключевого шаблона; просто пройдите движения по каждому шаблону, и как только у вас будет полное совпадение с одним из них, все готово.

Но я был бы сумасшедшим, чтобы сам писать что-то подобное, когда в моей среде столько библиотек сопоставления с образцом. Единственный, кого я знаю, технически способен - это PCRE; просто добавь ключи как "aaa|aab|aba" и вы получите первый возможный матч

Но есть и проблема. Во-первых, я не уверен, насколько он умен при составлении подобного совпадения. (Я думаю, что сначала он пытается "aaa", полностью разматывается после сбоя, затем полностью пытается aab, но я не проверял), что было бы не слишком эффективно по сравнению с подобным "a(a[ab]|ba)" где сходство разрешается быстрее.

Кроме того, я хотел бы иметь возможность придать некоторую гибкость ("a.ad", где второй символ не имеет значения, или соответствует числу... основные вещи, как это). С таким шаблоном в таком аддитивном подходе я не вижу способа восстановить исходный шаблон, который соответствует, чтобы я мог использовать значение, которое идет с ним.

(В худшем случае, я мог бы просто сгенерировать много записей в таблице, чтобы соответствовать каждому возможному варианту подстановочного знака и покончить с требованием шаблона, но я, честно говоря, не хочу.)

Какая библиотека является подходящим инструментом для работы и загрузки, как наилучшим образом использовать указанную библиотеку для достижения вышеуказанных целей, не изобретая велосипед?

Answer 1

В комментарии к вашему вопросу упоминается алгоритм Ахо – Корасика.

Если в вашей среде есть доступ к os.execute или же io.popen, ты можешь позвонить fgrep -o -f patterns filename, где patterns - это имя файла, который содержит шаблоны, разделенные символами новой строки, а имя файла - это имя вашего ввода. -oозначает, что будут выводиться только совпадения, по одному в строке. Вы можете заменить filename с участием - так что fgrep читает со стандартного ввода: echo "String to match" | fgrep -o -f patterns.

fgrep реализует алгоритм Ахо – Корасика.

Однако помните, что алгоритм Ахо – Корасика не распознает метасимволы.

Answer 2

Как сказал Александр Машин в ответе, алгоритм Ахо – Корасика - это эффективный алгоритм, который решит вашу проблему. В области Lua cloudflare /lua-aho-corasick - это реализация LuaJIT с использованием FFI. Также существует чистая реализация lua jgrahamc / aho-corasick-lua, которая может быть медленнее.