TRE (výpočetní) - TRE (computing)

TRE
Původní autořiVille Laurikari[1]
Úložiště
Upravte to na Wikidata
NapsánoC
TypPřibližná shoda řetězce
Licence2-klauzule BSD licence
webová stránkalaurikari.síť/ tre/

TRE je open-source knihovna pro porovnávání vzorů v textu,[2] který funguje jako a regulární výraz motor se schopností dělat přibližná shoda řetězců.[3] Byl vyvinut Ville Laurikari[1] a je distribuován pod a 2-klauzule BSD licence.

Knihovna[4] je napsán v C a poskytuje funkce, které umožňují použití regulárních výrazů pro vyhledávání přes řádky vstupního textu. Hlavní rozdíl od ostatních motorů regulárních výrazů spočívá v tom, že TRE může odpovídat fragmentům textu přibližným způsobem, tj. Za předpokladu, že by text mohl mít určitý počet překlepy.

Funkce

TRE používá rozšířený regulární výraz syntaxe s přidáním "směrů" pro přibližné porovnání předchozího fragmentu. Každý z těchto směrů určuje, kolik překlepů je pro tento fragment povoleno.

Přibližná shoda[5] se provádí podobným způsobem jako Levenshteinova vzdálenost, což znamená, že existují tři typy „překlepů“:[6]

PřeklepPříkladData
vložení dalšího znakupravidelný experimentdalší l, navíc E
chybí znak ze vzorupravidelné expiracechybějící u, chybí r
nahrazení nějaké postavyregolární expreseu → Ó, s → z

TRE umožňuje specifikaci náklady pro každý ze tří typů překlepů samostatně.

Projekt je dodáván s nástrojem příkazového řádku, reimplementací souhlas.

Ačkoli přibližná shoda vyžaduje určité rozšíření syntaxe, pokud se tato funkce nepoužívá, TRE funguje jako většina ostatních motorů pro shodu regulárních výrazů. Tohle znamená tamto

  • implementuje běžné regulární výrazy psané pro přísnou shodu;[3][7]
  • programátoři obeznámeni s Styl POSIX regulární výrazy[4] nemusíte používat mnoho studií, abyste mohli používat TRE.[3]

Předvídatelná spotřeba času a paměti

Autor knihovny uvádí[8] že čas strávený párováním roste lineárně se zvyšováním délky vstupního textu, zatímco paměťový požadavek je během párování konstantní a nezávisí na vstupu, pouze na vzoru.

jiný

Mohly být zkontrolovány další funkce společné pro většinu modulů regulárních výrazů srovnávací tabulky motorů regex nebo v seznamu funkcí TRE na jeho webové stránce.

Příklad použití

Přibližné směry shody jsou uvedeny v složených závorkách a měly by být odlišitelné od opakujících se kvantifikátorů (případně s vložením mezery po otevření závorky):

  • (pravidelný){~1}\s+(výraz){~2} by odpovídalo variantám fráze „regulární výraz“, ve které „regulární“ nemá více než jeden překlep a „výraz“ ne více než dva; jako v běžných regulárních výrazech " s +„znamená jeden nebo více mezerových znaků - tj. Rogular ekspression projde testem;
  • (výraz) {5i + 3d + 2s <11} by odpovídalo slovu „výraz“, pokud je celková cena překlepů menší než 11, zatímco cena za vložení je nastavena na 5, smazání na 3 a nahrazení znaku 2 - tj. ekspresson dává cenu 10.

Jazykové vazby

Kromě C je TRE použitelný prostřednictvím vazby pro Perl, Krajta a Haskell. [9] Je to výchozí modul regulárního výrazu v R.[10] Pokud by však projekt měl být napříč platformami, pro každou z cílových platforem by bylo nutné samostatné rozhraní.

Nevýhody

Jelikož jiné stroje s regulárními výrazy obvykle neposkytují přibližnou shodu, není téměř žádná souběžná implementace, se kterou by bylo možné TRE srovnávat. Existuje však několik věcí, které by programátoři mohli chtít vidět implementované v budoucích verzích:[11]

  • náhradní mechanismus pro nahrazování shodných textových fragmentů (jako v sed řetězcový procesor a mnoho moderních implementací regulárních výrazů, včetně vestavěných Perl nebo Jáva );
  • možnost použít jiný přibližný algoritmus shody (než Levenshteinovy ) pro lepší posouzení překlepové hodnoty (například Soundex ), nebo alespoň tento algoritmus má být vylepšen, aby umožňoval překlepy typu „swap“ (viz Vzdálenost Damerau – Levenshtein ).

Viz také

Reference

  1. ^ A b „R: Porovnávání vzorů pro surové vektory“. MIT.edu.
  2. ^ „Tre pro Windows“.
  3. ^ A b C „Použití fuzzy vyhledávání s tre-agree“. Linux Magazine.
  4. ^ A b „tre 0.8.0-6 (x86_64)“. 7. července 2020.
  5. ^ Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). Polylogaritmická aproximace pro úpravu vzdálenosti a asymetrickou složitost dotazu. IEEE Symp. Základy informatiky (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX  10.1.1.208.2079.
  6. ^ „TRE web-page - Regex Syntax“.
  7. ^ „Tre-agreep má všechny funkce grepu, ale může také dělat dvojznačně nebo fuzzy“
  8. ^ „TRE web-page - About“.
  9. ^ „Webová stránka TRE - FAQ“.
  10. ^ "Regulární výrazy použité v R".
  11. ^ "Označené deterministické konečné automaty s Lookahead". praktická vylepšení .. Lurikariho algoritmus, zejména ..

externí odkazy

Další čtení