WikiDer > TRE (вычисления)

TRE (computing)
TRE
Оригинальный автор (ы)Вилле Лаурикари[1]
Репозиторий
Отредактируйте это в Викиданных
Написано в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. ^ а б c "Использование нечеткого поиска с 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. ^ "Детерминированные конечные автоматы с метками и опережением просмотра". практические улучшения .. Алгоритм Лурикари, в частности ..

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

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