TRE (вычисления) - TRE (computing)

TRE

Оригинальный автор (ы)	Вилле Лаурикари[1]
Репозиторий	github.com/ лаурикари/ tre
Написано в	C
Тип	Приблизительное соответствие строк
Лицензия	BSD-подобная лицензия с двумя пунктами
Интернет сайт	лаурикари.сеть/ tre/

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

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

Функции

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

Примерное соответствие^[5] выполняется аналогично Расстояние Левенштейна, что означает, что существует три типа "распознанных" опечаток:^[6]

Опечатка	Пример	Данные
вставка лишнего символа	регулярная экспрессия	дополнительный л, дополнительный е
отсутствует символ в шаблоне	регулярное выражение	отсутствующий ты, отсутствующий р
замена какого-либо персонажа	реголярное выражение	ты → о, s → z

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

Проект поставляется с утилитой командной строки, повторной реализацией соглашаться.

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

• он реализует обычные регулярные выражения, написанные для строгого соответствия;^[3][7]
• программисты, знакомые с POSIX-стиль обычные выражения^[4] не нужно много изучать, чтобы использовать TRE.^[3]

Прогнозируемое потребление времени и памяти

Автор библиотеки утверждает^[8] время, затрачиваемое на сопоставление, линейно увеличивается с увеличением длины входного текста, в то время как требования к памяти постоянны во время сопоставления и не зависят от ввода, а только от шаблона.

Другой

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

Пример использования

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

• (обычный){~1}\s+(выражение){~2} будет соответствовать вариантам фразы "регулярное выражение", в которых "регулярное" содержит не более одной опечатки, а "выражение" не более двух; как в обычных регулярных выражениях " s +"означает один или несколько пробелов, т. е. обычная экспрессия пройдет тест;
• (выражение) {5i + 3d + 2s <11} будет соответствовать слову "выражение", если общая стоимость опечаток меньше 11, в то время как стоимость вставки установлена ​​на 5, удаление - на 3 и замена символа - на 2, т. е. экспрессон дает стоимость 10.

Языковые привязки

Помимо C, TRE можно использовать через привязки за Perl, Python и Haskell. ^[9] Это механизм регулярных выражений по умолчанию в р.^[10] Однако если проект должен быть кросс-платформенный, потребуется отдельный интерфейс для каждой из целевых платформ.

Недостатки

Поскольку другие механизмы регулярных выражений обычно не обеспечивают возможности приблизительного сопоставления, практически не существует параллельной реализации, с которой можно было бы сравнить TRE. Однако есть несколько вещей, которые программисты могут пожелать реализовать в будущих выпусках:^[11]

• механизм замены для замены совпадающих фрагментов текста (как в sed строковый процессор и многие современные реализации регулярных выражений, в том числе встроенные в Perl или же Ява );
• возможность использовать другой алгоритм приблизительного сопоставления (чем Левенштейна ) для лучшей оценки значения опечатки (например, Soundex ) или, по крайней мере, этот алгоритм нужно улучшить, чтобы допустить опечатки типа "своп" (см. Расстояние Дамерау – Левенштейна ).

Смотрите также

• Автомат Левенштейна
• Сравнение движков регулярных выражений
• Агреп

Рекомендации

1. «R: сопоставление с образцом для исходных векторов». Массачусетский технологический институт.edu.
2. «Tre для Windows».
3. "Использование нечеткого поиска с tre -gotip". Журнал Linux.
4. "tre 0.8.0-6 (x86_64)". 7 июля 2020.
5. Андони, Александр; Krauthgamer, Роберт; Онак, Кшиштоф (2010). Полилогарифмическое приближение для расстояния редактирования и асимметричной сложности запроса. IEEE Symp. Основы компьютерных наук (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX  10.1.1.208.2079.
6. "Веб-страница TRE - Синтаксис регулярных выражений".
7. «Tre -gotip имеет все функции grep, но также может делать неоднозначные или нечеткие»
8. "Веб-страница TRE - О компании".
9. "Интернет-страница TRE - FAQ".
10. «Регулярные выражения, используемые в R».
11. "Детерминированные конечные автоматы с метками и опережением просмотра". практические улучшения .. Алгоритм Лурикари, в частности ..

внешняя ссылка

• TRE - бесплатная и переносимая библиотека приблизительного сопоставления регулярных выражений

дальнейшее чтение

• Наварро, Гонсало (март 2001 г.), «Экскурсия по приблизительному сопоставлению строк», Опросы ACM Computing, 33 (1): 31–88, CiteSeerX  10.1.1.452.6317, Дои:10.1145/375360.375365, S2CID  207551224