TRE (вычисления)
| Оригинальный автор(ы) | Вилле Лаурикари [1] |
|---|---|
| Репозиторий | |
| Написано в | С |
| Тип | Примерное соответствие строк |
| Лицензия | Лицензия типа BSD из 2 пунктов |
| Веб-сайт | лаурикари |
TRE — это с открытым исходным кодом библиотека для сопоставления шаблонов в тексте. [2] который работает как механизм регулярных выражений с возможностью приблизительного сопоставления строк . [3] Его разработал Вилле Лаурикари. [1] и распространяется по лицензии BSD, состоящей из двух пунктов .
Библиотека [4] написан на C и предоставляет функции, позволяющие использовать регулярные выражения для поиска по строкам входного текста. Основное отличие от других движков регулярных выражений заключается в том, что TRE может сопоставлять фрагменты текста приблизительным образом, то есть предполагая, что в тексте может быть некоторое количество опечаток .
Функции
[ редактировать ]TRE использует расширенный синтаксис регулярных выражений с добавлением «направлений» для приблизительного сопоставления предыдущего фрагмента. В каждом из таких направлений указано, сколько опечаток допускается в данном фрагменте.
Примерное соответствие [5] выполняется аналогично расстоянию Левенштейна , что означает, что «распознаются» три типа опечаток: [6]
| Опечатка | Пример | Данные |
|---|---|---|
| вставка дополнительного символа | регулировать опыт | дополнительный л , дополнительный е |
| отсутствует символ в шаблоне | выражение правил | скучаю по тебе , скучаю по р |
| замена какого-то персонажа | регулярное выражение | ты → о , s → z |
TRE позволяет указать стоимость для каждого из трех типов опечаток независимо.
В состав проекта входит утилита командной строки, представляющая собой повторную реализацию agrep .
Хотя приблизительное сопоставление требует некоторого расширения синтаксиса, когда эта функция не используется, TRE работает так же, как и большинство других механизмов сопоставления регулярных выражений. Это означает, что
- он реализует обычные регулярные выражения, написанные для строгого соответствия; [3] [7]
- программисты, знакомые с в стиле POSIX регулярными выражениями [4] не нужно много учиться, чтобы иметь возможность использовать TRE. [3]
Предсказуемое потребление времени и памяти
[ редактировать ]Автор библиотеки утверждает [8] что время, затрачиваемое на сопоставление, растет линейно с увеличением длины входного текста, а потребность в памяти при сопоставлении постоянна и не зависит от ввода, а только от шаблона.
Другой
[ редактировать ]Другие функции, общие для большинства движков регулярных выражений, можно проверить в сравнительных таблицах движков регулярных выражений или в списке функций TRE на его веб-странице.
Пример использования
[ редактировать ]Приблизительные направления соответствия указаны в фигурных скобках и должны отличаться от повторяющихся кванторов (возможно, с вставкой пробела после открывающей скобки):
(regular){~1}\s+(expression){~2}будет соответствовать вариантам словосочетания «регулярное выражение», в которых «регулярное» имеет не более одной опечатки, а «выражение» — не более двух; как в обычных регулярных выражениях"\s+" означает один или несколько пробелов, т.е.пройдет испытание;rogular ekspression
(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 ) или, по крайней мере, улучшить этот алгоритм, чтобы допускать опечатки типа «подкачка» (см. Расстояние Дамерау–Левенштейна ).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Тре для Windows» .
- ^ Jump up to: а б с «Использование нечеткого поиска с tre-agrep» . Журнал Линукс .
- ^ Jump up to: а б «тре 0.8.0-6 (x86_64)» . 7 июля 2020 г.
- ^ Андони, Александр; Краутгамер, Роберт; Онак, Кшиштоф (2010). Полилогарифмическая аппроксимация расстояния редактирования и сложности асимметричных запросов . IEEE симп. Основы информатики (FOCS). arXiv : 1005.4033 . Бибкод : 2010arXiv1005.4033A . CiteSeerX 10.1.1.208.2079 .
- ^ «Веб-страница TRE — синтаксис регулярных выражений» .
- ^ «Tre-agrep обладает всеми функциями grep, но также может работать неоднозначно или нечетко»
- ^ "Сайт-страница TRE - О компании" .
- ^ "Сайт-страница TRE - Часто задаваемые вопросы" .
- ^ «Регулярные выражения, используемые в R» .
- ^ Трофимович, Уля (2019). «Тегированные детерминированные конечные автоматы с прогнозом вперед». arXiv : 1907.08837 [ cs.FL ].
практические улучшения..алгоритм Лурикари, в частности..
Внешние ссылки
[ редактировать ]Дальнейшее чтение
[ редактировать ]- Наварро, Гонсало (март 2001 г.), «Экскурсия по приблизительному сопоставлению строк», ACM Computing Surveys , 33 (1): 31–88, CiteSeerX 10.1.1.452.6317 , doi : 10.1145/375360.375365 , S2CID 207551224