README file for sgrep version 1.71-alpha From: http://www.cs.helsinki.fi/~jjaakkol/sgrep/README.txt Date: 1998-08-29 README file for sgrep version 1.71-alpha - a tool to search and index text, SGML, XML and HTML files using structured patterns Copyright (C) 1998 University of Helsinki, Department of Computer Science Authors: Jani Jaakkola Jani.Jaakkola@cs.helsinki.fi Pekka Kilpelainen Pekka.Kilpelainen@cs.helsinki.fi --------------------------------------------------------------------------- If you want to know what sgrep is, please check http://www.cs.helsinki.fi/~jjaakkol/sgrep.html This file (and newer versions of this file) is available from http://www.cs.helsinki.fi/~jjaakkol/sgrep/README.txt Sgrep is distributed under GNU General Public License. See file COPYING for details. However, the sources for sgrep are not yet currently available. They will be made available later, when they are in a slightly more stable state. This piece of software is still under development. This means that: - New features might be included before final release. - Existing features might be changed. - It is guaranteed to have bugs. - All suggestions are welcome. - All available documentation of the new features is contained in this file. --------------------------------------------------------------------------- NEW FEATURES --------------------------------------------------------------------------- Major new features since sgrep-1.0 which are already present: - Indexing of both structure and content. - SGML/XML/HTML scanner. - Official W32 binary. - sgtool has been dumped. It never really worked and even when it did, it wasn't very useful. - Should be completely compatible with older versions of sgrep. Features which will be present in sgrep-2.0: - Proper documentation - Support for querying notations, element type declarations and attribute list declarations inside SGML/XML document prolog - Scanning of all well-formed XML-documents. Features which might be present in sgrep-2.0: - Regular expressions. - Nearness operators. - Unicode support. --------------------------------------------------------------------------- Win32-binary release --------------------------------------------------------------------------- The Win32-binary release contains both sgrep binary and m4 binary. Sgrep binary is compiled with MSVC and requires no additional libraries. The m4 binary comes from cygnus GNU-Win32 project. See http://www.cygnus.com/misc/gnu-win32/ for details on GNU-Win32. Included binary release of m4 and the required Cygwin32 API library are both distributed under GNU General Public License (GPL). See file COPYING for details. Sources for m4 and Cygwin32 API library are available for download from http://www.cs.helsinki.fi/~jjaakkol/sgrep/download.html --------------------------------------------------------------------------- SGML-scanner --------------------------------------------------------------------------- Sgrep has a built-in scanner for XML, SGML and HTML-documents. This means that complex macros for querying SGML-files are no longer needed. However, sgrep still does not contain a full blown SGML-parser: the thing which it does contain could be described as an SGML-scanner. It does not recognize any syntax errors, it does not provide a parse tree, it does not maintain an element stack and it does not provide any event stream. It just recognizes regions from SGML-files corresponding to different SGML tokens: start tags, end tags, attributes, etc. SGML has many features which make it very difficult to parse. The SGML-scanner implemented in sgrep does not attempt to be a complete and error free SGML-parser; valid SGML-documents might confuse it. However, my goal is that all well formed XML-documents will be parsed correctly. The scanner has two modes: - SGML/HTML-mode o Names are case insensitive o PIs end with '>' - XML-mode o Names are case sensitive o PIs end with '?>' Sgrep will recognize empty XML elements () in both modes. The scanner does not automatically include entity references. However, it can automatically add external parsed entities defined in the internal document type definition subset to scanned files. Eg. if you have a line in your document, the scanner can automatically include file "chapter1.sgml" to the list of scanned files, when the scanner sees this line in the internal document type definition subset. To use this feature you need to use "-g include-entities" option. --------------------------------------------------------------------------- NEW QUERY LANGUAGE FEATURES --------------------------------------------------------------------------- The example file "example.sgml" and its DTD "example.dtd" are included in this distribution. * file("filename") Returns the region containing the named file. * pi("PITarget") Returns the regions containing the processing instructions beginning with the given PI target. % sgrep 'pi("example_pi")' example.sgml * attribute("attribute name") Returns the regions containing the named attribute. % sgrep 'attribute("ATT1")' example.sgml att1="value1" * attvalue("attribute value") Returns the regions containing the given attribute value. % sgrep 'attvalue("value2")' example.sgml "value2" % sgrep 'attribute("*") containing attvalue("value2")' example.sgml att2="value2" * stag("GI") Returns the regions containing the start tags with the given GI. % sgrep 'stag("EXAMPLE")' example.sgml * etag("GI") Returns the regions containing the end tags with the given GI. % sgrep 'etag("EXAMPLE")' example.sgml * word("word") Returns the regions containing the given word. N.B: A query word("foo") does not recognize occurrences of word "foo" inside comments. (See operators comment and comment_word below.) % sgrep 'word("example")' example.sgml example % sgrep '"\n"_."\n" containing word("example")' example.sgml This is an example SGML file to demonstrate new features in sgrep-2.0. * comments Returns the regions containing all SGML comments. % sgrep 'comments' example.sgml * comment_word("comment word") Returns the region containing the given word inside comments. % sgrep 'comment_word("another")' example.sgml another % sgrep 'comments containing comment_word("another")' example.sgml * cdata Returns regions containing CDATA marked sections. Sgrep recognizes words also inside CDATA marked sections. % sgrep 'cdata' example.sgml §ion ]]> % sgrep 'cdata containing word("another")' example.sgml * entity("entity name") Returns the regions containing references to the given entity. (Entity references are currently recognized only in PCDATA.) % sgrep 'entity("entity1")' example.sgml &entity1; % sgrep 'stag("ELEM1") .. etag("ELEM1") containing entity("entity1")' example.sgml &entity1; * doctype("doctype name") Returns the regions containing given document type name inside the document type declaration. % sgrep 'doctype("*")' example.sgml EXAMPLE * doctype_pid("publicid") Returns the regions containing the given document type public id inside document type declarations. % sgrep 'doctype_pid("*")' example.sgml -//SID//DTD sgrep example//EN * doctype_sid("systemid") Returns the regions containing the given document type system id inside document type declarations. % sgrep 'doctype_sid("ex*")' example.sgml example.dtd * entity_declaration("entity name") Returns the regions containing the declaration of the given entity name. % sgrep 'entity_declaration("entity1")' example.sgml * entity_literal("entity name") Returns the regions containing the literal value of the given entity name. % sgrep 'entity_literal("entity1")' example.sgml literal value * entity_pid("entity public id") Returns the regions containing the given public id of an entity within its declaration. % sgrep 'entity_pid("*")' example.sgml -//SID//NONSGML entity example//EN * entity_sid("entity system id") Returns the regions containing the given system id inside an entity declaration. % sgrep 'entity_sid("*")' example.sgml figure.file * entity_ndata("notation name") Returns the regions containing the given notation name inside entity declarations. % sgrep 'entity_ndata("*")' example.sgml anotation % sgrep 'entity_declaration("*") containing entity_ndata("ANOTATION")' example.sgml * prologs Returns the regions containing document prologs. % sgrep 'pi("*") in prologs' example.sgml -------------------------------------------------------------------- INDEXING -------------------------------------------------------------------- Sgrep supports indexing of both structure and content of SGML, HTML and XML documents. Indexing is implemented by creating a separate index file, which contains a list of terms and of regions corresponding to these terms. This means that if you want to output the actual content of result regions you have to keep the original files around. If the query uses only the new SGML query features, the same query should return same results independent of whether an index was used or not. Indexes are stored in compressed binary files. Depending on the indexed material the index file size is 30-60% of the original files. This is not so bad, since in theory you can produce the full content of the original files from the index file, except for whitespace and punctuation marks. Maximum size of the indexed data is currently 2 gigabytes. If you want to index larger collections, you have to split the index to multiple index files. Sgrep is switched to indexing mode by giving "-I" as first option in the command line. Command 'sgrep -I -h' will give you the summary of available indexing options: Usage: (sgindex | sgrep -I) Use 'sgrep -h' for help on query mode options. Indexing mode options are: -C display copyright notice -h help (means this text) -i fold all words to lower case when indexing -T show statistics about created index files -V display version information -v verbose mode. Shows what is going on -c create new index file -F read list of input files from instead of command line -g Options -C, -h, and -V should be self explanatory. Indexes are created using the -c option and giving a file list to index. The file list can be give directly on the command line, or with -F option (see below). % sgrep -I -c demo.index demo.sgml % ls -l demo.* -rw------- 1 jjaakkol grpd 53577 Aug 24 12:52 demo.index -rw------- 1 jjaakkol grpd 91536 Mar 6 13:40 demo.sgml First 13 lines of the index file contain statistics about the created index. % head -13 demo.index sgrep-index v0 2441 terms 11554 entries 1024 bytes header (1%) 9764 bytes term index (18%) 17222 bytes strings (32%) 26366 total strings 9144 compressed with lcps (-34%) 25545 bytes postings (47%) 22 bytes file list (0%) 53577 total index size -- With -F option you can give a list of the files to be indexed in the named file, instead of giving it on the command line. The file names given in the file have to separated by a newline. The -v option gives verbose progress reports while indexing: % sgrep -I -v -c demo.index demo.sgml Indexing 1/1 files 64/89K (71%) Writing index file of 52K Writing index 2048/2441 entries (83%) The entries added to the index are case sensitive by default. For example, word("Foo") is different from word("foo"). With option -i you can instruct sgrep to fold all words (only words in content or comments, not any structural elements like element type names or attribute values) to lowercase. With option -T you can get some statistics (some useful for debugging, some less useful, and some mighty cryptic) about the created index. With option -L you can create a file containing list of all terms added to index. Each line in created file will contain the amount of bytes required by the term and the term itself. This example is using the XML WWW-page from http://www.sil.org/sgml/xml.html % sgrep -I -i -L terms -c xml.index xml.html % cat terms | sort -n | tail 2043 eLI 2094 wa 2263 wto 2543 wof 2713 wand 3414 eA 3433 wxml 4410 wthe 5076 aHREF 5390 sA With option -S you can give indexer a stop word list to reduce the size of index. Stop word list consists of one stop word per line, with possibly including the amount of bytes in the term (so you can actually use a part of file originally created with the -L option to indexer). Here is an example using a simple English stop word list (containing words like "to", "and", "the" and so on) to reduce the size of the index: % sgrep -I -i -L terms -c xml.index xml.html % ls -l xml.index -rw------- 1 jjaakkol grpd 291599 Aug 24 14:13 xml.index % sgrep -I -i -S stoplist -c xml.index xml.html % ls -l xml.index -rw------- 1 jjaakkol grpd 259058 Aug 24 14:14 xml.index With using "-l " option you can obtain information about the impact of stop word list on index size when all terms taking more space than a fraction of 1/number of the index would be considered as stop words. % sgrep -I -l 200 -i -c xml.index xml.html Possible stop words: 4K (1.74%) 'aHREF' 3K (1.17%) 'eA' 1K (0.70%) 'eLI' 5K (1.85%) 'sA' 1K (0.70%) 'sLI' 2K (0.72%) 'wa' 2K (0.93%) 'wand' 1K (0.62%) 'wfor' 1K (0.67%) 'win' 2K (0.87%) 'wof' 4K (1.51%) 'wthe' 2K (0.78%) 'wto' 3K (1.18%) 'wxml' ------------- 38K (13.43%) total Using the "-g sgml" option you can select SGML mode scanner. Using the "-g xml" option you can select XML mode scanner. Using the "-g include-entities" option you can automatically include defined system entities to indexed files (see SGML scanner above). Using the "-g sgml-debug" option you can check the tokens which sgrep recognized from its input files: % sgrep -I -c demo.index -g sgml-debug sgreptest.sgml doctype("SGREPTEST"):dnSGREPTEST:(10,18) doctype_pid("-//SID//DTD Just something to test sgrep//EN"):dp-//SID//DTD Just something to test sgrep//EN:(29,72) doctype_sid("empty"):dsempty:(77,81) comment_word("Comment"):cComment:(93,99) comment(""):-:(88,110) pi("PI"):?PI:(111,115) .... word("third"):wthird:(1391,1395) etag("PARTNO"):ePARTNO:(1396,1404) etag("SGREPTEST"):eSGREPTEST:(1406,1417) With the "-m '" option you can adjust the amount of main memory indexer will use for postings spool before writing a temporary file. Default value for -m option is 20 megabytes. Creating the index completely in main is faster than using temporary files. However, if you give a value larger than available main memory, sgrep will probably start trashing and indexing will be slow. With "-w " option you can select which characters make up words. The default is "-w a-zA-Z". Here in Finland I would use "-w A-Za-ZÅÄÖåäö" (assuming you have iso-8859-1 font). If you want to index also numbers you could use "-w A-Za-z0-9" --------------------------------------------------------------------------- QUERIES --------------------------------------------------------------------------- Sgrep has some new options when used in the query mode. Options "-F ", "-w " and "-g " have the same functions as in the indexing mode. Option "-x " is used to specify an index while when one is used. If -x option is used and no file list is specified either in the command line or with -F option, sgrep obtains the list of queried files straight from the index. --------------------------------------------------------------------------- EXAMPLE --------------------------------------------------------------------------- Here the input file xml.html is taken from Robin Cover's excellent WWW-page at http://www.sil.org/sgml/xml.html Example: Find all P elements containing word "newsfax": % time sgrep -x xml.index 'stag("P") .. etag("P") containing word("newsfax")'

[August 19, 1998] Tools and Utilities from Robert Hanson: XML::Parser, LOTE NewsFax to XML Parsers, LOTE XML to Kingdom Summaries, XML Script Server Parser.

0.03user 0.03system 0:00.25elapsed 24%CPU (0avgtext+0avgdata 0maxresident)k The same example without using index: % time sgrep -i 'stag("P") .. etag("P") containing word("newsfax")' xml.html

[August 19, 1998] Tools and Utilities from Robert Hanson: XML::Parser, LOTE NewsFax to XML Parsers, LOTE XML to Kingdom Summaries, XML Script Server Parser.

0.82user 0.05system 0:01.18elapsed 73%CPU (0avgtext+0avgdata 0maxresident)k --------------------------------------------------------------------------- ANOTHER EXAMPLE --------------------------------------------------------------------------- This example uses Jon Bosak's XML-example material: religious texts and Shakespeare's works. Since this query is slightly more complex, it has been put together from smaller parts by using m4. File "filelist" contains the list of all XML-example files from Bosak's collection. Here is the file "query" # Finds elements having given name define(ELEMENT, (stag($1) .. etag($1))) # Finds LINE elements define(E_LINE, (ELEMENT("LINE"))) # Finds SPEECH elements define(E_SPEECH, (ELEMENT("SPEECH"))) # Finds SPEECH elements where HAMLET is speaking define(HAMLET_SPEAKING, (E_SPEECH containing ( ELEMENT("SPEAKER") containing word("HAMLET")))) # Finds LINE elements containing words to, be, not and question define(TOBENOTQUESTION, (E_LINE containing word("to") containing word("be") containing word("not") containing word("question"))) # Finds the LINE where HAMLET says the famous words define(HAMLET_SAYS, (TOBENOTQUESTION in HAMLET_SPEAKING)) Evaluate the query using plain search: % time sgrep -o "%f:\n %r\n" -f query -e HAMLET_SAYS -F filelist /xml/shakespeare.1.10.xml/hamlet.xml: To be, or not to be: that is the question: 16.60user 0.78system 0:18.29elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (327major+455minor)pagefaults 0swaps Create an index of the input texts: % time sgrep -I -c index -v -F filelist Indexing 43/43 files 14957/14958K (99%) Writing index file of 5472K Writing index 35840/36691 entries (97%) 23.65user 4.56system 0:32.77elapsed 86%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (94major+5928minor)pagefaults 0swaps Evaluate the query using index: % time sgrep -x index -o "%f:\n %r\n" -f query -e HAMLET_SAYS -F filelist /xml/shakespeare.1.10.xml/hamlet.xml: To be, or not to be: that is the question: 1.24user 0.13system 0:01.43elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (536major+728minor)pagefaults 0swaps --------------------------------------------------------------------------- THAT'S IT! Enjoy! --------------------------------------------------------------------------- Please send comments about sgrep-2.0 to Jani Jaakkola (jjaakkol@cs.helsinki.fi).