Существует ли известный алгоритм O (nm) -time/O (1) -пространства для сопоставления имен файлов POSIX (fnmatch)?

Изменить: WHOOPS! Большое допущение я испортил определение синтаксиса шаблона ? in fnmatch и, похоже, предложил (и, возможно, решил) гораздо более сложную проблему, когда он ведет себя как .? в регулярных выражениях. Конечно, на самом деле он должен вести себя как . в регулярных выражениях (сопоставление ровно одного символа, а не нуля или одного). Это, в свою очередь, означает, что моя первоначальная работа по сокращению проблем была достаточной для решения (теперь довольно скучной) оригинальной проблемы. Однако решение более сложной проблемы довольно интересно; Я мог бы написать это когда-нибудь.

С положительной стороны это означает, что существует гораздо больший шанс, что что-то вроде факуляции иглы 2way/SMOA может быть применимо к этим шаблонам, что, в свою очередь, может привести к желаемому O(n) или даже производительность.

В заголовке вопроса пусть m - длина рисунка/иглы, а n - длина строки, сопоставляемой с ней.

Этот вопрос представляет интерес для меня, потому что все алгоритмы, которые я видел/использовали, имеют либо патологически плохую производительность, либо возможные переполнения из-за обратного отслеживания или требуемое распределение динамической памяти (например, для подхода DFA или просто избегая выполнения обратного отслеживания в стеке вызовов) и, следовательно, имеют случаи сбоя, которые также могут быть опасны, если программа использует fnmatch для предоставления/запрета доступа к каким-либо правам.

Я готов поверить, что такой алгоритм не существует для соответствия регулярных выражений, но язык шаблонов имен файлов намного проще, чем регулярные выражения. Я уже упростил проблему до такой степени, что можно предположить, что шаблон не использует символ *, и в этой модифицированной задаче вы не согласуете всю строку, но ищете вхождение шаблона в строку ( как проблема соответствия подстроки). Если вы еще больше упростите язык и удалите символ ?, язык будет состоять только из конкатенаций фиксированных строк и выражений скобок, и это можно легко сопоставить в O(mn) времени и O (1) пространстве, что, возможно, может быть улучшено до O(n), если методы факторизации иглы, используемые в поиске подстроки 2way и SMOA, могут быть расширены до таких шаблонов скобок. Однако наивно каждый ? требует испытаний с или без ?, потребляющих символ, в результате чего коэффициент времени 2^q, где q - количество символов ? в шаблоне.

Кто-нибудь знает, была ли эта проблема уже решена или есть идеи для ее решения?

Примечание. При определении пространства O (1) я использую Transdichotomous_model.

Примечание 2: Этот сайт содержит подробную информацию о алгоритмах 2way и SMOA, на которые я ссылался: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Ответ 1

ОК, вот как я решил проблему.

Попытка сопоставить начальную часть шаблона с первым * с строкой. Если это не поможет, выручите. Если это удастся, отбросьте эту начальную часть как шаблона, так и строки; мы закончили с ними. (И если мы нажмем конец шаблона перед нажатием *, у нас есть соответствие iff, мы также достигли конца строки.)
Пропустите весь путь до конца шаблона (все после последнего *, которое может быть шаблоном нулевой длины, если шаблон заканчивается на *). Подсчитайте количество символов, необходимых для его соответствия, и проверьте, что много символов из конца строки. Если они не совпадают, мы закончили. Если они совпадают, отбросьте этот компонент шаблона и строки.
Теперь у нас остается (возможно, пустая) последовательность подшаблонов, все из которых связаны с обеих сторон с помощью *. Мы стараемся последовательно их искать в том, что осталось от строки, беря первое соответствие для каждого и отбрасывая начало строки до конца. Если мы найдем соответствие для каждого компонента таким образом, у нас будет соответствие для всего шаблона. Если какой-либо поиск компонента завершился неудачно, весь шаблон не соответствует.

Этот алогорифм не имеет рекурсии и сохраняет только конечное количество смещений в строке/шаблоне, поэтому в трансдихотомовой модели это O (1) пространство. Шаг 1 был O (m) во времени, шаг 2 был O (n + m) во времени (или O (m), если мы предположим, что длина входной строки уже известна, но я принимаю строку C) и шаг 3 (с использованием наивного алгоритма поиска) O (nm). Таким образом, общий алгоритм равен O (nm) во времени. Возможно, можно улучшить шаг 3 как O (n), но я еще не пробовал.

Наконец, обратите внимание, что исходная сложная проблема, возможно, еще полезна для решения. Это потому, что я не учитывал многосимвольные элементы сопоставления, которые большинство людей, реализующих регулярное выражение, и такие, как правило, игнорируют, потому что они уродливы, чтобы получить право, и нет стандартного API для взаимодействия с языковой системой и получения необходимой информации для получения их. Но с учетом сказанного здесь приведен пример: предположим, что ch является многосимвольным элементом сортировки. Тогда [c[.ch.]] может потреблять 1 или 2 символа. И мы снова нуждаемся в более сложном алгоритме, который я описал в своем первоначальном ответе, который, мне кажется, нуждается в пространстве O(log m) и, возможно, несколько больше, чем O(nm) времени (в лучшем случае я предполагаю O(n²m)). На данный момент у меня нет интереса к реализации поддержки многосимвольных элементов, но это оставляет приятную открытую проблему...

Ответ 2

Вы изучали механизм регулярных выражений re2 от Russ Cox (от Google)?

Это механизм согласования регулярных выражений, основанный на детерминированных конечных автоматах, который отличается от обычных реализаций (Perl, PCRE) с использованием обратного отслеживания для моделирования недетерминированного конечного автомата. Одна из конкретных целей проекта заключалась в том, чтобы устранить описанное вами катастрофическое поведение обратной трассировки.

Он запрещает некоторые расширения Perl, такие как обратные ссылки в шаблоне поиска, но вам не нужно это для сопоставления glob.

Я не уверен, что он гарантирует O(mn) время и O(1) ограничения памяти специально, но он был достаточно хорош, чтобы запустить службу поиска кодов Google во время ее существования.

По крайней мере, должно быть здорово заглянуть внутрь и посмотреть, как это работает. Russ Cox написал три статьи о re2 - один, два, три - и re2 code с открытым исходным кодом.

Ответ 3

Изменить: WHOOPS! Большое признание я испортил определение синтаксиса шаблона ? in fnmatch и, похоже, решил гораздо более сложную задачу, когда он ведет себя как .? в регулярных выражениях. Конечно, на самом деле он должен вести себя как . в регулярных выражениях (сопоставление ровно одного символа, а не нуля или одного). Это, в свою очередь, означает, что моя первоначальная работа по сокращению проблем была достаточной для решения (теперь довольно скучной) оригинальной проблемы. Однако решение более сложной проблемы довольно интересно; Я мог бы написать это когда-нибудь.

Ниже приведено возможное решение более сложной проблемы.

Я разработал то, что кажется решением в пространстве O(log q) (где q - количество вопросительных знаков в шаблоне и, следовательно, q < m) и неопределенное, но, чем экспоненциальное время.

Прежде всего, быстрое объяснение проблемы. Сначала разбивайте шаблон на каждом *; он разлагается как исходный и конечный компонент (возможно, нулевой длины), а также ряд внутренних компонентов, фланкированных с обеих сторон a *. Это означает, что если мы определим, совпадают ли исходные/конечные компоненты, мы можем применить следующий алгоритм для внутренних совпадений: начиная с последнего компонента, поиск соответствия в строке, начинающейся с самого последнего смещения. Это оставляет максимально возможное количество символов "сена", чтобы соответствовать предыдущим компонентам; если они не все нужны, это не проблема, потому что тот факт, что вмешательство * позволяет нам позже выбросить столько, сколько необходимо, поэтому не рекомендуется попробовать "использовать больше ? меток" последнего компонента или найти более раннее его появление. Затем эту процедуру можно повторить для каждого компонента. Обратите внимание, что здесь я сильно использую тот факт, что единственным "оператором повторения" в выражении fnmatch является *, который соответствует нулю или более вхождению любого символа. Такое же сокращение не будет работать с регулярными выражениями.

С этой точки зрения я начал искать, как эффективно подойти к одному компоненту. Я разрешаю коэффициент времени n, так что это означает, что все в порядке, чтобы начать пытаться на все возможные позиции в строке, и сдаться и перейти к следующей позиции, если мы потерпим неудачу. Это общая процедура, которую мы возьмем (еще никаких боев-Муро-подобных трюков, возможно, их можно будет привезти позже).

Для данного компонента (который не содержит *, только буквенные символы, скобки, которые соответствуют точно одному символу из заданного набора, и ?), он имеет минимальную и максимальную длину, которые он мог бы сопоставить. Минимум - это длина, если вы опускаете все символы ? и выражаете скобки в виде одного символа, а максимальная длина, если вы включаете символы ?. В каждой позиции мы будем пробовать каждую возможную длину, с которой мог бы сравниться компонент шаблона. Это означает, что мы проводим испытания q+1. Для следующего объяснения предположим, что длина остается фиксированной (это самый внешний цикл, вне рекурсии, который должен быть введен). Это также фиксирует длину (в символах) строки, которую мы будем сравнивать с шаблоном в этой точке.

Теперь здесь интересная часть. Я не хочу перебирать все возможные комбинации, из которых символы ? не используются/не используются. Итератор слишком велик для хранения. Поэтому я обманываю. Я разбиваю компонент шаблона на две "половинки", L и R, где каждая содержит половину символов ?. Затем я просто перебираю все возможности того, сколько символов ? используется в L (от 0 до общего числа, которое будет использоваться на основе длины, указанной выше), а затем количество символов ? используемый в R. Это также разделяет строку, которую мы пытаемся сопоставить, с частью, которая будет сопоставлена с шаблоном L и шаблоном R.

Теперь мы уменьшили проблему проверки того, соответствует ли компонент шаблона с символами q ? определенной строке фиксированной длины двум экземплярам проверки того, соответствует ли шаблон с символами q/2 ? конкретную меньшую строку фиксированной длины. Применить рекурсию. И так как каждый шаг уменьшает количество задействованных <<20 > символов, количество уровней рекурсии ограничено log q.

Ответ 4

Вы можете создать хэш обеих строк, а затем сравнить их. Хэш-расчет будет выполнен в O (m), а поиск в O (m + n)

Вы можете использовать что-то вроде этого для вычисления хэша строки, где s [i] является символом

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Как вы сказали, это для сопоставления имен файлов, и вы не можете использовать это, когда у вас есть подстановочные знаки в строках. Удачи!

Ответ 5

Я чувствую, что это невозможно.

Хотя я не могу предоставить аргумент, предупреждающий о пуле, моя интуиция заключается в том, что вы всегда сможете создавать шаблоны, содержащие q = тета (m) ?, где необходимо, чтобы алгоритм в некоторых смысл, учитывают все возможности 2 ^ q. Для этого потребуется пространство O (q) = O (m), чтобы отслеживать, какие из возможностей вы сейчас просматриваете. Например, алгоритм NFA использует это пространство для отслеживания множества состояний, в которых он сейчас находится; метод обратной перемотки грубой силы использует пространство как стек (и для добавления оскорбления к травме, он использует O (2 ^ q) в дополнение к O (q) пространства).