TRE(컴퓨터)

TRE (computing)
TRE
원본 작성자빌레 로리카리[1]
리포지토리
기록 위치C
유형대략적인 문자열 일치
면허증2-clause BSD 유사
웹사이트laurikari.net/tre/

TRE는 텍스트에서 패턴 매칭을 위한 오픈소스 라이브러리로,[2] 대략적인 문자열 매칭을 할 수 있는 기능을 가진 정규식 엔진처럼 작동한다.[3]Ville Laurikari에[1] 의해 개발되었으며 2클라우스 BSD와 같은 라이센스로 배포된다.

도서관은[4] C로 작성되어 있으며, 입력 텍스트 라인을 검색할 때 정규 표현식을 사용할 수 있는 기능을 제공한다.다른 정규식 엔진과의 주요 차이점은 TRE가 텍스트 조각을 대략적인 방법으로 일치시킬 수 있다는 것이다. 즉, 텍스트에 오타가 몇 개 있을 수 있다고 가정할 때.

특징들

TRE는 앞의 조각을 근사하게 일치시키기 위해 "방향"을 추가하여 확장 정규식 구문을 사용한다.그러한 각 방향은 이 조각에 오타가 몇 개나 허용되는지 명시한다.

대략적인 일치는[5] 레벤슈테인 거리와 유사한 방식으로 수행되며, 이는 '인식'[6]된 오타가 세 가지 유형임을 의미한다.

타이포 예 데이터
여분의 문자 삽입 리걸러식. 엑스트라 l, 엑스트라 e
무늬에서 글자를 빠뜨리다 섭정. missing u, missing r
어떤 인물의 교체 왕조 퇴치 u → o, s → z

TRE는 세 가지 유형 각각에 대한 비용을 독립적으로 지정할 수 있다.

이 프로젝트에는 명령행 유틸리티, 즉 agrep의 재구성이 수반된다.

대략적인 일치에는 약간의 구문 확장이 필요하지만, 이 기능을 사용하지 않을 때 TRE는 대부분의 다른 정규식 일치 엔진과 같이 작동한다.라는 뜻이다.

  • 엄격한 일치를 위해 작성된 일반적인 정규 표현을 구현한다.[3][7]
  • POSIX 스타일의 정규 표현에[4] 익숙한 프로그래머들은 TRE를 사용할 수 있도록 많은 연구를 할 필요가 없다.[3]

예측 가능한 시간 및 메모리 소비량

도서관의 저자는 일치에 소요되는 시간은 입력 텍스트 길이가 증가함에 따라 선형적으로 증가하는 반면, 일치 시 메모리 요구 사항은 일정하며 패턴에만 의존하지 않는다고[8] 말한다.

기타

대부분의 정규식 엔진에 공통적인 다른 기능들은 regex 엔진 비교표 또는 웹 페이지의 TRE 기능 목록에서 확인할 수 있다.

사용 예제

대략적인 일치 방향은 곱슬 브래킷으로 지정되며 반복 정량자(대괄호를 연 후 공백을 삽입하는 경우)와 구별할 수 있어야 한다.

  • (regular){~1}\s+(expression){~2}일반적인 정규 표현에서처럼 "정규어"는 오타가 1개 이하, "정규어"는 2개 이하인 "정규어 표현"의 변형과 일치한다.\s+"는 하나 이상의 공백 문자를 의미한다. 즉, 
    로글러 ekspression
    시험에 합격할 수 있다.
  • (expression){ 5i + 3d + 2s < 11}삽입 비용이 5로 설정되고, 삭제 비용이 3으로 설정되며, 문자를 2로 대체하는 동안, 총 오타 비용이 11보다 작으면 단어 "match"와 일치할 것이다. ekspresson10의 비용을 지불하다.

언어 바인딩

C 외에도 Perl, Python, Haskell용 바인딩을 통해 TRE를 사용할 수 있다.[9] R의 기본 정규식 엔진이다.[10]그러나 프로젝트가 교차 플랫폼이어야 하는 경우, 각 대상 플랫폼에 필요한 별도의 인터페이스가 있을 것이다.

단점들

다른 정규식 엔진은 대개 대략적인 일치 능력을 제공하지 않기 때문에, TRE를 비교할 수 있는 동시 구현이 거의 없다.그러나 프로그래머가 향후 릴리스에서 구현하기를 원하는 몇 가지 사항이 있다.[11]

  • 일치하는 텍스트 조각을 대체하기 위한 대체 메커니즘(예: Sed String Processor 및 Perl 또는 Java에 내장된 정규 표현식의 많은 현대적 구현)
  • 더 나은 타이포 값 평가(예: 사운덱스)를 위해 다른 근사 일치 알고리즘(레벤슈테인보다)을 사용할 기회 또는 적어도 이 알고리즘이 "스왑" 유형의 오타가 가능하도록 개선될 기회(다메라우-레벤슈테인 거리 참조).

참고 항목

참조

  1. ^ a b "R: Pattern Matching for Raw Vectors". MIT.edu.
  2. ^ "Tre for Windows".
  3. ^ a b c "Using fuzzy searches with tre-agrep". Linux Magazine.
  4. ^ a b "tre 0.8.0-6 (x86_64)". July 7, 2020.
  5. ^ Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). Polylogarithmic approximation for edit distance and the asymmetric query complexity. IEEE Symp. Foundations of Computer Science (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079.
  6. ^ "TRE web-page - Regex Syntax".
  7. ^ "Tre-agrep은 grep의 기능을 모두 갖추고 있지만 모호하거나 모호한 기능도 할 수 있다."
  8. ^ "TRE web-page - About".
  9. ^ "TRE web-page - FAQ".
  10. ^ "Regular Expressions as used in R".
  11. ^ "Tagged Deterministic Finite Automata with Lookahead". practical improvements .. Lurikari algorithm, notably ..

외부 링크

추가 읽기