TRE (informatyka)

TRE

Oryginalni autorzy	Ville Laurikari
Magazyn	github.com/laurikari/tre _ _ _
Napisane w	C
Typ	Przybliżone dopasowanie ciągów
Licencja	2-klauzulowa licencja podobna do BSD
Strona internetowa	laurikari .net /tre /

TRE to biblioteka typu open source do dopasowywania wzorców w tekście, która działa jak silnik wyrażeń regularnych z możliwością przybliżonego dopasowywania ciągów znaków . Został opracowany przez Ville Laurikari i jest rozpowszechniany na podstawie 2-klauzulowej licencji podobnej do BSD .

Biblioteka jest napisana w języku C i udostępnia funkcje umożliwiające wykorzystanie wyrażeń regularnych do przeszukiwania linii tekstu wejściowego. Główną różnicą w stosunku do innych silników wyrażeń regularnych jest to, że TRE może dopasowywać fragmenty tekstu w sposób przybliżony, to znaczy zakładając, że tekst może zawierać pewną liczbę literówek .

Cechy

TRE wykorzystuje rozszerzoną składnię wyrażeń regularnych z dodatkiem „kierunków” do przybliżonego dopasowania poprzedzającego fragmentu. Każdy z takich kierunków określa ile literówek jest dozwolonych dla tego fragmentu.

Przybliżone dopasowanie odbywa się w sposób podobny do odległości Levenshteina , co oznacza, że ​​istnieją trzy rodzaje „rozpoznawanych” literówek:

literówka	Przykład	Dane
wstawienie dodatkowego znaku	regularna ekspozycja	dodatkowe l , dodatkowe e
brak znaku we wzorcu	regularna ekspresja	tęsknię za tobą , tęsknię za r
zastąpienie jakiegoś znaku	wyrażenie regularne	u → o , s → z

TRE umożliwia określenie kosztu dla każdego z trzech typów literówek niezależnie.

Projekt jest dostarczany z narzędziem wiersza poleceń, reimplementacją agrep .

Chociaż przybliżone dopasowanie wymaga pewnego rozszerzenia składni, gdy ta funkcja nie jest używana, TRE działa jak większość innych silników dopasowywania wyrażeń regularnych. To znaczy że

• implementuje zwykłe wyrażenia regularne napisane dla ścisłego dopasowywania;
• programiści zaznajomieni z wyrażeniami regularnymi w stylu POSIX nie muszą dużo się uczyć, aby móc używać TRE.

Przewidywalny czas i zużycie pamięci

Autor biblioteki stwierdza, że ​​czas poświęcony na dopasowanie rośnie liniowo wraz ze wzrostem długości wprowadzanego tekstu, podczas gdy zapotrzebowanie na pamięć jest stałe podczas dopasowywania i nie zależy od danych wejściowych, tylko od wzorca.

Inny

Inne funkcje, wspólne dla większości silników wyrażeń regularnych, można sprawdzić w tabelach porównawczych silników wyrażeń regularnych lub na liście funkcji TRE na jego stronie internetowej.

Przykład użycia

Przybliżone kierunki dopasowania podane są w nawiasach klamrowych i powinny być odróżnialne od powtarzających się kwantyfikatorów (ewentualnie z wstawieniem spacji po nawiasie otwierającym):

• ( regularne ) { ~1 } \ s +( wyrażenie ) { ~2 } pasowałoby do wariantów frazy "wyrażenie regularne", w którym "regularne" ma nie więcej niż jedną literówkę, a "wyrażenie" nie więcej niż dwie; jak w zwykłych wyrażeniach regularnych " \s+ " oznacza jedną lub więcej spacji — tj

  łobuzerska ekspresja

  zdałby egzamin;
• (wyrażenie){ 5i + 3d + 2s < 11} pasowałoby do słowa "wyrażenie", jeśli całkowity koszt literówek jest mniejszy niż 11, podczas gdy koszt wstawienia jest ustawiony na 5, usunięcie na 3, a podstawienie znaku na 2 - czyli ekspresson daje koszt z 10.

Wiązania językowe

Oprócz C, TRE jest użyteczny poprzez powiązania dla Perl , Python i Haskell . Jest to domyślny mechanizm wyrażeń regularnych w R . Jeśli jednak projekt miałby być wieloplatformowy , niezbędny byłby osobny interfejs dla każdej z platform docelowych.

Niedogodności

Ponieważ inne silniki wyrażeń regularnych zwykle nie zapewniają możliwości przybliżonego dopasowania, prawie nie ma równoczesnej implementacji, z którą można by porównać TRE. Istnieje jednak kilka rzeczy, które programiści mogą chcieć zaimplementować w przyszłych wersjach:

• mechanizm zastępczy podstawiania dopasowanych fragmentów tekstu (jak w procesorze łańcuchowym sed i wielu nowoczesnych implementacjach wyrażeń regularnych, w tym wbudowane w Perla czy Javę );
• możliwość użycia innego przybliżonego algorytmu dopasowywania (niż algorytm Levenshteina ) w celu lepszej oceny wartości literówek (na przykład Soundex ) lub przynajmniej ulepszenia tego algorytmu, aby umożliwić literówki typu „zamiana” (patrz odległość Damerau – Levenshtein ).

Zobacz też

• Automat Levenshteina
• Porównanie silników wyrażeń regularnych
• Zgadzam się

Linki zewnętrzne

• TRE — bezpłatna i przenośna biblioteka przybliżonego dopasowywania wyrażeń regularnych

Dalsza lektura

•    Navarro, Gonzalo (marzec 2001), „Wycieczka z przewodnikiem po przybliżonym dopasowywaniu ciągów”, ACM Computing Surveys , 33 (1): 31–88, CiteSeerX 10.1.1.452.6317 , doi : 10.1145/375360.375365 , S2CID 207551224