TRE (вычислительная техника)

TRE — это библиотека с открытым исходным кодом для сопоставления шаблонов в тексте, ^[2] которая работает как механизм регулярных выражений с возможностью приблизительного сопоставления строк . ^[3] Она была разработана Вилле Лаурикари ^[1] и распространяется по лицензии типа BSD с двумя пунктами .

Библиотека ^[4] написана на языке C и предоставляет функции, которые позволяют использовать регулярные выражения для поиска по строкам входного текста. Главное отличие от других движков регулярных выражений заключается в том, что TRE может сопоставлять фрагменты текста приблизительным образом, то есть предполагая, что текст может иметь некоторое количество опечаток .

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

Приблизительное сопоставление ^[5] выполняется способом, аналогичным расстоянию Левенштейна , что означает, что «распознаются» три типа опечаток: ^[6]

TRE позволяет указать стоимость для каждого из трех типов опечаток независимо.

Проект поставляется с утилитой командной строки, представляющей собой повторную реализацию agrep .

Хотя приблизительное соответствие требует некоторого расширения синтаксиса, когда эта функция не используется, 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 — бесплатная и переносимая библиотека приближенного сопоставления регулярных выражений

• Наварро, Гонсало (март 2001 г.), «Путеводитель по приближенному сопоставлению строк», ACM Computing Surveys , 33 (1): 31–88 , CiteSeerX  10.1.1.452.6317 , doi :10.1145/375360.375365, S2CID  207551224