NR‐grep: a fast and flexible pattern‐matching tool
Identifieur interne : 002139 ( Istex/Curation ); précédent : 002138; suivant : 002140NR‐grep: a fast and flexible pattern‐matching tool
Auteurs : Gonzalo Navarro [Chili]Source :
- Software: Practice and Experience [ 0038-0644 ] ; 2001-11-10.
English descriptors
- KwdEn :
Abstract
We present nrgrep (‘non‐deterministic reverse grep’), a new pattern‐matching tool designed for efficient search of complex patterns. Unlike previous tools of the grep family, such as agrep and Gnu grep, nrgrep is based on a single and uniform concept: the bit‐parallel simulation of a non‐deterministic suffix automaton. As a result, nrgrep can find from simple patterns to regular expressions, exactly or allowing errors in the matches, with an efficiency that degrades smoothly as the complexity of the searched pattern increases. Another concept that is fully integrated into nrgrep and that contributes to this smoothness is the selection of adequate subpatterns for fast scanning, which is also absent in many current tools. We show that the efficiency of nrgrep is similar to that of the fastest existing string‐matching tools for the simplest patterns, and is by far unmatched for more complex patterns. Copyright © 2001 John Wiley & Sons, Ltd.
Url:
DOI: 10.1002/spe.411
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002294
Links to Exploration step
ISTEX:84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">NR‐grep: a fast and flexible pattern‐matching tool</title>
<author><name sortKey="Navarro, Gonzalo" sort="Navarro, Gonzalo" uniqKey="Navarro G" first="Gonzalo" last="Navarro">Gonzalo Navarro</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile</mods:affiliation>
<country xml:lang="fr">Chili</country>
<wicri:regionArea>Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago</wicri:regionArea>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D</idno>
<date when="2001" year="2001">2001</date>
<idno type="doi">10.1002/spe.411</idno>
<idno type="url">https://api.istex.fr/document/84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002294</idno>
<idno type="wicri:Area/Istex/Curation">002139</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">NR‐grep: a fast and flexible pattern‐matching tool</title>
<author><name sortKey="Navarro, Gonzalo" sort="Navarro, Gonzalo" uniqKey="Navarro G" first="Gonzalo" last="Navarro">Gonzalo Navarro</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile</mods:affiliation>
<country xml:lang="fr">Chili</country>
<wicri:regionArea>Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago</wicri:regionArea>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Software: Practice and Experience</title>
<title level="j" type="abbrev">Softw: Pract. Exper.</title>
<idno type="ISSN">0038-0644</idno>
<idno type="eISSN">1097-024X</idno>
<imprint><publisher>John Wiley & Sons, Ltd.</publisher>
<pubPlace>Chichester, UK</pubPlace>
<date type="published" when="2001-11-10">2001-11-10</date>
<biblScope unit="volume">31</biblScope>
<biblScope unit="issue">13</biblScope>
<biblScope unit="page" from="1265">1265</biblScope>
<biblScope unit="page" to="1312">1312</biblScope>
</imprint>
<idno type="ISSN">0038-0644</idno>
</series>
<idno type="istex">84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D</idno>
<idno type="DOI">10.1002/spe.411</idno>
<idno type="ArticleID">SPE411</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0038-0644</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>BNDM</term>
<term>agrep</term>
<term>approximate string matching</term>
<term>grep</term>
<term>online string matching</term>
<term>regular expression searching</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We present nrgrep (‘non‐deterministic reverse grep’), a new pattern‐matching tool designed for efficient search of complex patterns. Unlike previous tools of the grep family, such as agrep and Gnu grep, nrgrep is based on a single and uniform concept: the bit‐parallel simulation of a non‐deterministic suffix automaton. As a result, nrgrep can find from simple patterns to regular expressions, exactly or allowing errors in the matches, with an efficiency that degrades smoothly as the complexity of the searched pattern increases. Another concept that is fully integrated into nrgrep and that contributes to this smoothness is the selection of adequate subpatterns for fast scanning, which is also absent in many current tools. We show that the efficiency of nrgrep is similar to that of the fastest existing string‐matching tools for the simplest patterns, and is by far unmatched for more complex patterns. Copyright © 2001 John Wiley & Sons, Ltd.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002139 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002139 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= OcrV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:84E6817E3C87E3D1FD3B4A72ADB9546A35AEDF2D |texte= NR‐grep: a fast and flexible pattern‐matching tool }}
This area was generated with Dilib version V0.6.32. |