Как эффективно реализовать регулярное выражение типа. * A. * B. *?

Question

Я хочу сопоставить имена файлов, как Colibri . Я пытался решить это с помощью регулярных выражений.

Поиск в Colibri работает так, что вы вводите символы по порядку внутри имени файла, и он находит все файлы с этими символами по порядку в имени файла. Например, для «ab» он находит «cabal», «ab» и «achab».

Простая вставка .* между буквами работает (поэтому искомая строка "ab" становится регулярным выражением .*a.*b.*), но я хочу сделать это для большого количества файлов.

Пока у меня есть O (N * ???), где N - количество имен файлов и ??? в лучшем случае линейная сложность (я предполагаю, что мой язык использует NFA). Меня не волнует космическая сложность. Какие структуры данных или алгоритмы я должен выбрать, чтобы сделать его более эффективным (с точки зрения временной сложности)?

Answer 1

Если вы просто хотите проверить, содержатся ли символы строки поиска search в другой строке str в том же порядке, вы можете использовать этот простой алгоритм:

pos := -1
for each character in search do
    pos := indexOf(str, character, pos+1)
    if pos is -1 then
        break
    endif
endfor
return pos

Этот алгоритм возвращает смещение последнего символа search в str и -1 в противном случае. Его время выполнения в O ( n ) (вы можете заменить indexOf на простой цикл while, который сравнивает символы в str с pos и Length ( str ) - 1 и возвращает смещение или -1).

Answer 2

Это значительно повысит вашу эффективность, если вы замените . на отрицание персонажа.т. е.

 [^a]*a[^b]*b.*

Таким образом, у вас намного меньше отката назад. См. Этот справочник

---

Редактировать * @yi_H Вы правы, это регулярное выражение, вероятно, также будет служить:

a[^b]*b

Answer 3

Ваш . не нужен. Вы получите лучшую производительность, если вы просто преобразуете «abc» в ^[^a]*a[^b]*b[^c]*c.

string exp = "^";
foreach (char c in inputString)
{
   string s = Regex.Escape (c.ToString()); // escape `.` as `\.`
   exp += "[^" + s + "]*" + s; // replace `a` with `[^a]*a`
}
Regex regex = new Regex (exp, RegexOptions.IgnoreCase);
foreach (string fileName in fileNames)
{
   if (regex.IsMatch (fileName))
      yield return fileName;
}

Answer 4

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

Если ваша ABC содержит X символов, тогда таблица поиска «1 длина» будет содержать записи таблицы X, если это таблица «2 длины», она будет содержать записи X ^ 2 и т. Д. Таблица 2 длины будет содержать для каждой записи («ab», «qx») все файлы, в которых эти буквы расположены в указанном порядке. При поиске более длинного ввода «строка» найдите соответствующую запись и выполните поиск по этим записям.

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