TRE - это библиотека с открытым исходным кодом для сопоставления с образцом в тексте [2], которая работает как механизм регулярных выражений с возможностью приблизительного сопоставления строк . [3] Он был разработан Вилле Лаурикари [1] и распространяется по BSD-подобной лицензии с двумя пунктами .
Автор (ы) оригинала | Вилле Лаурикари [1] |
---|---|
Репозиторий | |
Написано в | C |
Тип | Приблизительное соответствие строк |
Лицензия | BSD-подобная лицензия с двумя пунктами |
Веб-сайт | laurikari |
Библиотека [4] написана на C и предоставляет функции, позволяющие использовать регулярные выражения для поиска по строкам ввода текста. Основное отличие от других движков регулярных выражений состоит в том, что TRE может приближенно сопоставлять фрагменты текста, то есть предполагая, что в тексте может быть некоторое количество опечаток .
Функции
TRE использует расширенный синтаксис регулярных выражений с добавлением «направлений» для приблизительного сопоставления предыдущего фрагмента. Каждое из таких указаний указывает, сколько опечаток допустимо для этого фрагмента.
Приблизительное сопоставление [5] выполняется аналогично расстоянию Левенштейна , что означает, что существует три типа «распознанных» опечаток: [6]
Опечатка | Пример | Данные |
---|---|---|
вставка лишнего символа | регулярная экспрессия | extra l , extra e |
отсутствует символ в шаблоне | регулярное выражение | скучаю по тебе , скучаю по р |
замена какого-либо персонажа | регулярное выражение | u → o , s → z |
TRE позволяет отдельно указать стоимость каждого из трех типов опечаток.
Проект поставляется с утилитой командной строки, являющейся повторной реализацией согласования .
Хотя приблизительное сопоставление требует некоторого расширения синтаксиса, когда эта функция не используется, TRE работает как большинство других механизмов сопоставления регулярных выражений. Это значит, что
- он реализует обычные регулярные выражения, написанные для строгого соответствия; [3] [7]
- программистам, знакомым с регулярными выражениями в стиле POSIX [4], не нужно много изучать, чтобы использовать TRE. [3]
Прогнозируемое потребление времени и памяти
Автор библиотеки утверждает [8], что время, затрачиваемое на сопоставление, линейно растет с увеличением длины входного текста, в то время как требования к памяти постоянны во время сопоставления и не зависят от ввода, только от шаблона.
Другой
Другие функции, общие для большинства механизмов регулярных выражений, можно проверить в таблицах сравнения механизмов регулярных выражений или в списке функций TRE на его веб-странице.
Пример использования
Приблизительные направления сопоставления указаны в фигурных скобках и должны отличаться от повторяющихся квантификаторов (возможно, со вставкой пробела после открывающей скобки):
(regular){~1}\s+(expression){~2}
будет соответствовать вариантам фразы «регулярное выражение», в которых «регулярное» содержит не более одной опечатки, а «выражение» - не более двух; как и в обычных регулярных выражениях "\s+
" означает один или несколько пробелов, т. е.пройдет тест;обычная экспрессия
(expression){ 5i + 3d + 2s < 11}
будет соответствовать слову «выражение», если общая стоимость опечаток меньше 11, в то время как стоимость вставки установлена на 5, удаление - на 3 и замена символа - на 2, т. е.ekspresson
дает стоимость 10.
Языковые привязки
Помимо C, TRE можно использовать через привязки для Perl , Python и Haskell . [9] Это регулярное выражение двигателя по умолчанию в R . [10] Однако, если проект должен быть кроссплатформенным , потребуется отдельный интерфейс для каждой из целевых платформ.
Недостатки
Поскольку другие механизмы регулярных выражений обычно не обеспечивают возможности приблизительного сопоставления, практически не существует параллельной реализации, с которой можно было бы сравнить TRE. Однако есть несколько вещей, которые программисты, возможно, захотят реализовать в будущих выпусках: [11]
- механизм замены для замены совпадающих фрагментов текста (например, в строковом процессоре sed и многих современных реализациях регулярных выражений, в том числе встроенных в Perl или Java );
- возможность использовать другой алгоритм приблизительного сопоставления (чем у Левенштейна ) для лучшей оценки значения опечатки (например, Soundex ), или, по крайней мере, этот алгоритм должен быть улучшен, чтобы допускать опечатки типа «своп» (см. расстояние Дамерау – Левенштейна ).
Смотрите также
- Автомат Левенштейна
- Сравнение движков регулярных выражений
- Агреп
Рекомендации
- ^ «Tre для Windows» .
- ^ а б в «Использование нечеткого поиска с tre-соглашением» . Журнал Linux .
- ^ а б "tre 0.8.0-6 (x86_64)" . 7 июля 2020.
- ^ Андони, Александр; Krauthgamer, Роберт; Онак, Кшиштоф (2010). Полилогарифмическое приближение для расстояния редактирования и асимметричной сложности запроса . IEEE Symp. Основы компьютерных наук (FOCS). arXiv : 1005,4033 . Bibcode : 2010arXiv1005.4033A . CiteSeerX 10.1.1.208.2079 .
- ^ "Веб-страница TRE - Синтаксис регулярных выражений" .
- ^ "Tre -gotip имеет все функции grep, но может также делать неоднозначные или нечеткие"
- ^ "Интернет-страница TRE - О компании" .
- ^ "Интернет-страница TRE - FAQ" .
- ^ «Регулярные выражения, используемые в R» .
- ^ «Детерминированные конечные автоматы с тегами с прогнозированием» .
практические улучшения .. Алгоритм Лурикари, в частности ..
Внешние ссылки
- TRE - бесплатная и переносимая библиотека приблизительного сопоставления регулярных выражений
дальнейшее чтение
- Наварро, Гонсало (март 2001 г.), «Экскурсия по приблизительному сопоставлению строк», ACM Computing Surveys , 33 (1): 31–88, CiteSeerX 10.1.1.452.6317 , doi : 10.1145 / 375360.375365 , S2CID 207551224