Простой сопоставитель регулярных выражений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 5 участников)
Строка 5: Строка 5:
  
 
==Алгоритм==
 
==Алгоритм==
Введем обозначения:
+
Данный алгоритм работает быстрее [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], построенного по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], но только для регулярных выражений, состоящих из символов:  
:<tex>c</tex> {{---}} один любой буквенный символ
+
:<tex>c</tex> {{---}} один любой буквенный символ,
:<tex>\ldotp</tex> {{---}} один любой символ
+
:<tex>\ldotp</tex> {{---}} один любой символ,
:<tex>\wedge</tex> {{---}} символ начала текста
+
:<tex>\wedge</tex> {{---}} символ начала текста,
:<tex>\mathdollar</tex> {{---}} символ конца текста
+
:<tex>$</tex> {{---}} символ конца текста,
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз
+
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
 +
 
 +
Например, для <tex>\mathtt{http://\ldotp*wiki\ldotp*com}</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
 
  <font color=darkgreen>// поиск вхождения регулярного выражения в любом месте текста</font>
 
  <font color=darkgreen>// поиск вхождения регулярного выражения в любом месте текста</font>
  '''function''' match(regexp: '''string''', text: '''string'''): '''boolean'''   
+
  '''function''' match(regexp: '''String''', text: '''String'''): '''boolean'''   
 
     '''if''' regexp[0] == '^'
 
     '''if''' regexp[0] == '^'
         '''return''' matchHere(regexp.drop(1), text)  <font color=darkgreen>// drop(n) возвращает строку без первых n элементов</font>
+
         '''return''' matchHere(regexp[1:], text)  <font color=darkgreen>// regexp[n:] возвращает regexp без первых n элементов за O(1)</font>
 
     '''int''' i = 0
 
     '''int''' i = 0
 
     '''while''' i <tex>\leqslant</tex> text.length
 
     '''while''' i <tex>\leqslant</tex> text.length
         '''if''' matchHere(regexp, text.drop(i))
+
         '''if''' matchHere(regexp, text[i:])
 
             '''return''' ''true''
 
             '''return''' ''true''
 
         i++
 
         i++
 
     '''return''' ''false''
 
     '''return''' ''false''
+
 
 +
Функция <tex>\mathrm{match(regexp, text)}</tex> проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое.
 +
 
 +
Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. То есть если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.
 +
 
 +
В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. То есть если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
 +
 
 
  <font color=darkgreen>// поиск вхождения регулярного выражения в начале текста</font>
 
  <font color=darkgreen>// поиск вхождения регулярного выражения в начале текста</font>
  '''function''' matchHere(regexp: '''string''', text: '''string'''): '''boolean'''  
+
  '''function''' matchHere(regexp: '''String''', text: '''String'''): '''boolean'''  
 
     '''if''' regexp[0] == '\0'
 
     '''if''' regexp[0] == '\0'
         '''return''' ''true''
+
         '''return''' ''true''  
     '''if''' regexp[1] == '*'
+
     '''if''' regexp[1] == '*' <font color=darkgreen>// не будет выхода за пределы строки, так как в конце regexp и text всегда есть символ '\0'</font>
         '''return''' matchStar(regexp[0], regexp.drop(2), text)
+
         '''return''' matchStar(regexp[0], regexp[2:], text)
 
     '''if''' regexp[0] == '$' '''and''' regexp[1] == '\0'
 
     '''if''' regexp[0] == '$' '''and''' regexp[1] == '\0'
         '''return''' text == '\0';
+
         '''return''' text == '\0'
 
     '''if''' text[0] != '\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == text[0])
 
     '''if''' text[0] != '\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == text[0])
         '''return''' matchHere(regexp.drop(1), text.drop(1))
+
         '''return''' matchHere(regexp[1:], text[1:])
 
     '''return''' ''false''
 
     '''return''' ''false''
+
 
 +
Основная часть работы сделана в <tex>\mathrm{matchHere(regexp, text)}</tex>, которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция <tex>\mathrm{matchHere}</tex> пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав <tex>\mathrm{matchHere}</tex> рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.
 +
 
 
  <font color=darkgreen>// сопоставление с регулярным выражением вида: c*</font>
 
  <font color=darkgreen>// сопоставление с регулярным выражением вида: c*</font>
  '''function''' matchStar(c : '''char''', regexp: '''string''', text: '''string'''): '''boolean'''
+
  '''function''' matchStar(c: '''char''', regexp: '''String''', text: '''String'''): '''boolean'''
 
     '''int''' i = 0
 
     '''int''' i = 0
 
     '''while''' i <tex>\leqslant</tex> text.length '''and''' (text[i] == c '''or''' c == '.')
 
     '''while''' i <tex>\leqslant</tex> text.length '''and''' (text[i] == c '''or''' c == '.')
         '''if''' matchHere(regexp, text.drop(i))
+
         '''if''' matchHere(regexp, text[i:])
 
             '''return''' ''true''
 
             '''return''' ''true''
 
         i++
 
         i++
 
     '''return''' ''false''
 
     '''return''' ''false''
 
Данный псевдокод использует указатели и арифметические операции над ними из языка C.
 
 
Функция <tex>\mathrm{match(regexp, text)}</tex> проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое.
 
 
Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. Т.е. если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.
 
 
В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. Т.е. если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
 
 
Основная часть работы сделана в <tex>\mathrm{matchHere(regexp, text)}</tex>, которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция <tex>\mathrm{matchHere}</tex> пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав <tex>\mathrm{matchHere}</tex> рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.
 
  
 
Рассмотрим возможные случаи:
 
Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>(regexp[0] == \backslash0)</tex>, то текст допускается этим регулярным выражением.
+
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)},\,</tex> то текст допускается этим регулярным выражением.
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[https://ru.wikipedia.org/wiki/Grep grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
+
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция <tex>\mathrm{mathchStar},\,</tex> которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep Wikipedia {{---}} grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
+
# Если регулярное выражение это <tex>$</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
 
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
 
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
 
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.
 
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.
 
 
Данный алгоритм прост и лаконичен, но у него есть недостаток. Для регулярного выражения содержащего несколько <tex>.*</tex> подряд этот алгоритм может работать очень медленно. Рассмотрим время работы '''grep'а''' (наш алгоритм схож со стандартным '''grep'ом'''). Например команда: "<tex>grep</tex> <tex>a.*a.*a.*a.a</tex>" потребует 20 секунд, чтобы обработать текстовой файл размером 4MB на обычной машине. В то же время алгоритм, который конвертирует [[Недетерминированные конечные автоматы|недетерминированный конечный автомат]] в [[Детерминированные конечные автоматы|детерминированный конечный автомат]] (например, '''egrep'''<ref>[https://ru.wikipedia.org/wiki/Grep egrep]</ref>), потребует менее одной десятой доли секунды на обработку тех же данных.
 
  
 
===Модификации===
 
===Модификации===
 
Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
 
Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>s</tex>.  
+
# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>S</tex>.  
# Сопоставим часть текста без <tex>s</tex> с остатком регулярного выражения.
+
# Сопоставим часть текста без <tex>S</tex> с остатком регулярного выражения.
# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>s</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>s</tex> и повторяем шаг 2.
+
# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>S</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>S</tex> и повторяем шаг <tex>2</tex>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
  '''function''' matchStar(c : '''char''', regexp: '''string''', text: '''string'''): '''boolean'''
+
  '''function''' matchStar(c: '''char''', regexp: '''String''', text: '''String'''): '''boolean'''
 
     '''int''' i
 
     '''int''' i
 
     '''for''' (i = 0; text[i] != '\0' '''and''' (text[i] == c '''or''' c == '.'); i++)
 
     '''for''' (i = 0; text[i] != '\0' '''and''' (text[i] == c '''or''' c == '.'); i++)
 
     '''while''' i <tex>\geqslant</tex> 0
 
     '''while''' i <tex>\geqslant</tex> 0
         '''if''' matchHere(regexp, text.drop(i))
+
         '''if''' matchHere(regexp, text[i:])
 
             '''return''' ''true''
 
             '''return''' ''true''
 
         i--
 
         i--
 
     '''return''' ''false''
 
     '''return''' ''false''
 
 
Увеличить количество символов из которых может состоять регулярное выражение можно, задавая регулярное выражение последовательностью структур, описывающих каждый ее элемент.
 
=== Псевдокод ===
 
'''struct''' Token
 
    type: '''int'''  <font color=darkgreen>/ тип элемента: STAR, QUESTION, PLUS, SYMBOL, ...</font>
 
    c: '''char'''    <font color=darkgreen>/ сам символ</font>
 
    cs: '''char'''[]  <font color=darkgreen>/ для случая [...]</font>
 
    ncs: '''bool'''  <font color=darkgreen>/ для случая отрицания cs: [^...]</font>
 
  
 
==См. также==
 
==См. также==
 
* [[Регулярные языки: два определения и их эквивалентность]]
 
* [[Регулярные языки: два определения и их эквивалентность]]
 +
 +
==Примечания==
 +
<references />
  
 
== Источники информации ==
 
== Источники информации ==
 
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
 
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
 
== Примечания ==
 
<references/>
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Регулярные языки и ДКА]]

Текущая версия на 19:11, 4 сентября 2022

Задача:
Даны регулярное выражение и текст. Нужно проверить допускает ли регулярное выражение данный текст.


Алгоритм

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

[math]c[/math] — один любой буквенный символ,
[math]\ldotp[/math] — один любой символ,
[math]\wedge[/math] — символ начала текста,
[math]$[/math] — символ конца текста,
[math]*[/math] — предыдущий символ встречается ноль или более раз.

Например, для [math]\mathtt{http://\ldotp*wiki\ldotp*com}[/math], очевидно, проще написать простой сопоставитель, чем строить НКА.

Псевдокод

// поиск вхождения регулярного выражения в любом месте текста
function match(regexp: String, text: String): boolean  
    if regexp[0] == '^'
        return matchHere(regexp[1:], text)  // regexp[n:] возвращает regexp без первых n элементов за O(1)
    int i = 0
    while i [math]\leqslant[/math] text.length
        if matchHere(regexp, text[i:])
            return true
        i++
    return false

Функция [math]\mathrm{match(regexp, text)}[/math] проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое.

Логика функции [math]\mathrm{match}[/math] проста. Если [math]\wedge[/math] — первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. То есть если [math]\wedge[/math][math]abc[/math] — регулярное выражение, то [math]abc[/math] должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.

В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. То есть если [math]abc[/math] — регулярное выражение, то для него найдется самое левое вхождение в текст.

// поиск вхождения регулярного выражения в начале текста
function matchHere(regexp: String, text: String): boolean 
    if regexp[0] == '\0'
        return true 
    if regexp[1] == '*'  // не будет выхода за пределы строки, так как в конце regexp и text всегда есть символ '\0'
        return matchStar(regexp[0], regexp[2:], text)
    if regexp[0] == '$' and regexp[1] == '\0'
        return text == '\0'
    if text[0] != '\0' and (regexp[0] == '.' or regexp[0] == text[0])
        return matchHere(regexp[1:], text[1:])
    return false

Основная часть работы сделана в [math]\mathrm{matchHere(regexp, text)}[/math], которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция [math]\mathrm{matchHere}[/math] пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав [math]\mathrm{matchHere}[/math] рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.

// сопоставление с регулярным выражением вида: c*
function matchStar(c: char, regexp: String, text: String): boolean
    int i = 0
    while i [math]\leqslant[/math] text.length and (text[i] == c or c == '.')
        if matchHere(regexp, text[i:])
            return true
        i++
    return false

Рассмотрим возможные случаи:

  1. Если в ходе рекурсии регулярное выражение осталось пустым [math]\mathrm{(regexp[0] == \backslash0)},\,[/math] то текст допускается этим регулярным выражением.
  2. Если регулярное выражение имеет вид [math]c*[/math], то вызывается функция [math]\mathrm{mathchStar},\,[/math] которая пытается сопоставить повторение символа [math]c[/math], начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в grep[1], где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
  3. Если регулярное выражение это [math]$[/math], то оно допускает этот текст тогда и только тогда, когда текст закончился.
  4. Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов [math]\mathrm{matchHere}[/math].
  5. Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.

Модификации

Немного изменим функцию [math]\mathrm{matchStar}[/math] для поиск самого левого и самого длинного вхождения [math]c*[/math]:

  1. Найдем максимальную последовательность подряд идущих символов [math]c[/math]. Назовем ее [math]S[/math].
  2. Сопоставим часть текста без [math]S[/math] с остатком регулярного выражения.
  3. Если части совпали, то текст допускается этим регулярным выражением. Иначе, если [math]S[/math] пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из [math]S[/math] и повторяем шаг [math]2[/math].

Псевдокод

function matchStar(c: char, regexp: String, text: String): boolean
    int i
    for (i = 0; text[i] != '\0' and (text[i] == c or c == '.'); i++)
    while i [math]\geqslant[/math] 0
        if matchHere(regexp, text[i:])
            return true
        i--
    return false

См. также

Примечания

Источники информации