The State of Swish3

I've been working on the next version of Swish-e (codename: Swish3) for about a year now. Squirreling away hours in the late evening after the kid is asleep, with one ear on the TV my wife is watching in the other room, and eyes on the screen in here. I've been learning C, UTF-8 and Perl's XS glue language. It's been a very stretching year.

This little corner of the blog will record my progress.

22:15:32 29-Sep-2006
Swish3 Status 19 April 2008

There's been quite a bit of activity in the last month.

  • The C++ Xapian example now can search as well as index, and there are Perl equivalents using Search::Xapian checked into svn as well. The C++ code will read/write the swish.xml header; the Perl does not (yet).
  • The meta/prop id unique check now uses a hash for quick look up.
  • The test suite for libswish3 is totally restructured. Now using Perl's Test::Harness and added a slew of new meta/prop tests. Alongside that were additions to the NamedBuffer debugging output to print each substring in the buffer.
  • Several new string-related utility functions for converting ints to strings and back. Also a new config hash for configration options that use a StringList instead of a simple string.
  • Fixed some mem leaks in the example .c programs and added more info to the swish_lint usage() output (including reminders about the various SWISH_DEBUG* env var values).
There are still several parser features yet to be implemented to support the Swish-e 2.4 config options, but those will likely take a backseat to getting a working swish3 Perl script running with SWISH::Prog and SWISH::Prog::Xapian.

22:42:14 19-Apr-2008
Introduction to Swish3

Swish is the Simple Web Indexing System for Humans. Swish is an information retrieval tool. It is not a search engine, but can be used as an integral part of creating a search engine. Swish gathers, parses, indexes and searches document collections. A collection can be any set of real or virtual documents: web pages, database rows, PDFs or office files, or anything else that can be converted to text.

Swish3 is version three of Swish. Kevin Hughes wrote the original version in 1994. In 2000, the project was updated and released as Swish-e version 2 (the -e is for Enhanced). Swish3 is the third phase in the evolution of the project.

In this document, the name Swish will refer to the entire project, without regard to a particular version. Swish-e will refer specifically to version 2.x. Swish3 will refer specifically to version three.

Anatomy of a Search Tool Chain

The following description could apply to any search system or information retrival project, not just Swish. First we'll look at the various parts of the system, then look at how they are implemented in Swish3.

Every search system implements the following chain of features:

  • aggregator

    An aggregator assembles documents into a collection. It can be as simple as a filesystem tool like the Unix find command or as sophisticated as a web crawler. An aggregator selects documents based on various criteria: content, MIME type or format, date, author, URL, or any other criteria that you desire.

  • normalizer

    A normalizer verifies that all documents the aggregator collects are in a format that the analyzer can parse. For example, a binary file format like PDF is converted to HTML or unmarked text. The same is true for all office file formats, PostScript, etc.

  • analyzer

    An analyzer examines the text supplied via the aggegrator/normalizer steps. The analyzer does several things, some of them optional:

    • parsing

      Separates text from any surrounding markup, optionally remembering the context (tag) in which text was found.

    • case folding

      Changes the text to all lowercase or all uppercase, to make comparisons easier.

    • tokenizing

      Splitting a string of text into tokens or words.

    • stemming

      Using one of a variety of word-stemming algorithms, tries to discover the root stem of each word.

    • customization

      Many advanced analyzers offer some level of customization to apply at some point in the analysis, whether it be synonym matching or other linguistic logic.

  • indexer

    An indexer stores basic document metadata and token (word) information in an index for fast and efficient retrieval.

  • searcher

    A searcher parses a user query using the same logic used by the analyser when processing the original document collection, applies some well-defined rules for matching documents in the index, and then returns results, typically a list or iterator of matching documents.

Now let's look at how Swish3 implements these five features.

A Library, Not a Command

The first thing to know about Swish3 is that, unlike previous versions of Swish, there is not a single Swish3 implementation.

That might sound confusing at first, because it is a significant departure from earlier versions of Swish, where there was a primary program, written in C, which handled all five links in the search chain. Swish3 takes a different approach.

Swish3 is primarily a C library called libswish3 . The library has a well-defined list of public functions and data structures that aim to fill a particular void in the world of information retrieval tools: analyzing HTML and XML documents.

Swish3 takes as its starting point the -S prog feature of Swish-e, where you can define your own aggregator/normalizer program, and makes that Swish3's central feature. Swish3 extends the -S prog API to include additional header values, and adds the same MIME-type-matching feature as the popular Apache web server.

Swish3 has no native indexer or searcher features [TODO: this might change if the 2.6 BDB backend is ported]. Nor does it have any aggregator or normalizer features. Swish3 is primarily an analyzer.

The Swish3 distribution does come with some examples of how to write Swish3 applications, including an example program for using the popular Xapian library. And there is a Perl implementation based on the SWISH::Prog package.

So How Does It Work?

libswish3 defines hooks or callbacks where you can override the default behaviour of the analyzer. These hooks are intended for making it easy to plug libswish3 into the indexing chain.

Here's one example. If you wanted to index a web site, you might use an aggregator/normalizer tool like Swish-e's spider.pl . spider.pl will print its output on stdout.

 % spider.pl your_config > spider_output

Then you could use a program like swish_xapian to analyze and index the output:

 % swish_xapian -c swish.conf - < spider_output

If you look at the source for the swish_xapian program, in the libswish3 distribution, you will see that there is a handler function defined that takes the output of the libswish3 parsing function and adds it to a Xapian index.

See Also

This document provides an overview of Swish3's anatomy. You might also be interested in these docs:

22:45:59 15-Apr-2008
Migrating from Swish-e to Swish3

If you haven't already, read the Introduction to Swish3 document first.

This document is intended for users already familiar with Swish-e version 2.x who want to migrate to using Swish3.

The Tool Chain

Swish3 is intended to be one part of a search system tool chain. In this section we will look at how Swish-e implements each of the tool chain features, and then compare it to Swish3.

Aggregator

Swish-e has two built-in aggregators, for filesystem and web, indicated with the -S flag to the swish-e command. Swish-e also has a third -S option called prog , which is short for program . The program is an aggregator that you define. Swish-e ships with several example aggregators, including a filesystem crawler called DirTree.pl and a web crawler called spider.pl . There are also example aggregators for pulling data from a database and for specific kinds of documents, like Hypermail mail archives.

Swish3 has no built-in aggregators. Instead, Swish3 takes the -S prog approach of defining an API for external aggregators to follow.

Normalizer

Swish-e has a feature called FileFilter which allows you define an external program to call if a document's name matches a particular pattern. The file is handed to the external program and the output of the external program is treated as the contents of the document. For example, you can specify that all documents that end with .pdf are first filtered through the pdftotext command.

Swish-e also comes with a set of Perl modules bundled together as SWISH::Filter . SWISH::Filter is used by the external aggregators like DirTree.pl and spider.pl , thus making those programs both aggregators and normalizers.

Swish3 has no built-in normalizer or feature like FileFilter . Instead, Swish3 assumes that something like SWISH::Filter will be used to standardize documents before they are handed to Swish3.

Configuration

One of the biggest changes is the configuration file format. Swish3 uses XML-style configuration files, and supports a subset of the configuration options available in Swish-e.

This section documents the configuration options supported in Swish3.

See Also
22:45:58 15-Apr-2008
Swish3 Status 30 March 2008

More progress with Swish3.

  • There is now a swish_xapian.cpp C++ example for using libswish3 with a Xapian backend. All that is complete is the indexing portion; still TODO is the search part. Still, a significant thing that it was so easy to build a search engine.
  • The swish.xml header format is complete and can now read/write the header file. Need to add that part to the swish_xapian.cpp example.
  • Squashed some long-standing memory leaks when using the filehandle functions.
Little by little.

22:03:48 30-Mar-2008
Swish3 Status 2008-03-15

I've finally gotten back to Swish3 development after several months away. Hard to believe I've been working on this project for something close to 3 years now.

Lately I have been focusing on the following things:

Header file format
Because Swish3 will have multiple IR backends, it is important that there be a consistent index metadata file that describes the MetaNames, Properties, and tokenizing information, just like the Swish2 header does. Just as with the config file format, it makes sense to define the header file format as XML, since we already have a robust XML parser for free. To make it simple, I have defined the header file XML schema to be the same as the config file schema. In short, you configure Swish3 by creating a header file. The "real" header file will be more strict about explicitly naming all the expected attribute values, numbering the MetaName/Property ids, etc. But the idea is simple: a single XML schema.

I have written the code to read header/config file format and create a swish_Config object. There's also code for merging 2 swish_Config objects together, so that you can define a config file to override an existing header file.

Still TODO is the code for writing the header file.

The Perl bindings have been updated to reflect the new swish_Config API. This required a great deal of reworking and thinking about the Perl API. I had to rewrite things a few times to get a workable solution. The key Perl mantra is "objects on demand." I.e., do not define any Perl objects that wrap C pointers and try to keep them on the XS side. Instead, create all Perl objects "just in time" as part of the get_* method call. This makes reference counting much simpler.

MetaNames and PropertyNames
These now have their own C API with swish_MetaName and swish_Property structs. These relate directly to the header file format and swish_Config. There will end up being a separate PropertyName API for search results. I still think we're going to have to port the Swish2 PropertyNames storage/retrieval code to Swish3 and have a backend-indepedent index.prop file. The issue with this is going to be scaling. One other thought I've had is storing properties in a SQLite db. That route won't allow for presorted properties, but does have the advantage of being much more transparent and de-buggable.

SWISH::Prog
I have moved the SWISH::Prog svn tree to svn.swish-e.org from peknet.com. I also moved SWISH::Filter (and likely will eventually move SWISH::API::More and its cousins).

SWISH::Prog will form the framework for the Perl implementation of Swish3. I know there are some folks who don't like the idea of Swish3 being so Perl-centric. To that I can say only, tough luck. :)

Seriously though, my perspective is that there will be multiple Swish3 implementations. The one I am working on is in Perl using SWISH::Prog. There's nothing to stop someone from implementing one in C or C++ or Java or whatever. libswish3 provides the parsing/tokenizing piece missing from other IR projects, and it is a library for the very reason that implementing a Swish3 program should be language-neutral. If you can link against a C library, then you can write a Swish3 program. The header file API is well documented; the backend is supposed to be pluggable. It's all about the API.

I do intend to write a swish_xapian.cpp program eventually, showing how to implement a C++ Swish3 program with Xapian. That could be the fallback program if you really don't want to use Perl.

Documentation
I've stared a swish_intro.7 and swish_migration.7 set of docs. swish_intro will outline the aggregator/normalizer/analyzer/indexer/searcher philosophy and the outline of the libswish3 API. swish_migration will discuss differences in Swish2 vs Swish3 and how you can convert your config files and move to using Swish3.

22:23:14 15-Mar-2008
SWISH::Prog take 2

Spent the last week or 2 totally reworking SWISH::Prog. Reorganized the class layout to mirror the aggregator/parser/indexer/searcher paradigm I described some time ago. It has started to look a little like KinoSearch in that respect, with the addition of the aggregators and parser (which is of course Swish-e's contribution to IR).

After mulling/experimenting for several days over how best to write the spider, I have decided to use WWW::Mechanize along with WWW::Rules and write from scratch. Then I'll provide backwards API compat for the Swish-e 2.4 spider.pl script config files/callbacks/etc. This proved easier than a direct port, and allows me to provide extensible caching/queueing/user_agent classes rather than hardcoding everything in a single script/library. I toyed with WWW::CheckSite but in order to make it work with the aggregator API required so many gymnastics it finally became easier to just write the spider myself. And a good programming exercise as well. :)

22:29:46 10-Dec-2007
libswish3.3
NAME

libswish3 - Swish3 C library

SYNOPSIS
Data Structures
 
 struct swish_StringList
 {
     int             n;
     xmlChar **      word;
 };
 
 
 struct swish_Config
 {
     int             ref_cnt;    /* for scripting languages */
     void           *stash;      /* for scripting languages */
     xmlHashTablePtr conf;       /* the meat */
 };
 
 struct swish_ConfigValue
 {
     int             ref_cnt;
     unsigned int    multi;      /* indicates whether value is a string or hashref */
     unsigned int    equal;      /* indicates whether key/value pairs are equal */
     void            *value;     /* xmlHashTablePtr or xmlChar *str */
     xmlChar         *key;       /* should be same as the key that points at this object */
 };
 
 
 struct swish_NamedBuffer
 {
     int             ref_cnt;    /* for scripting languages */
     void           *stash;      /* for scripting languages */
     xmlHashTablePtr hash;       /* the meat */
 };
 
 struct swish_DocInfo
 {
     time_t              mtime;
     off_t               size;
     xmlChar *           mime;
     xmlChar *           encoding;
     xmlChar *           uri;
     unsigned int        nwords;
     xmlChar *           ext;
     xmlChar *           parser;
     xmlChar *           update;
 };
 
 
 struct swish_Word
 {
     unsigned int        position;       // word position in doc
     xmlChar             *metaname;      // immediate metaname
     xmlChar             *context;       // metaname ancestry
     xmlChar             *word;          // the word itself (NOTE stored as multibyte not wchar)
     unsigned int        start_offset;   // start byte
     unsigned int        end_offset;     // end byte   
     struct swish_Word  *next;          // pointer to next swish_Word
     struct swish_Word  *prev;          // pointer to prev swish_Word
 };
 
 struct swish_WordList
 {
     swish_Word    *head;
     swish_Word    *tail;
     swish_Word    *current;        // for iterating
     unsigned int   nwords;
     unsigned int   ref_cnt;        // for scripting languages
 };
 
 struct swish_Tag
 {
     xmlChar            *name;
     struct swish_Tag   *next;
     unsigned int        n;
 };
 
 struct swish_TagStack
 {
     swish_Tag         *head;
     swish_Tag         *temp;
     unsigned int       count;
     char              *name;       // debugging aid -- name of the stack
     xmlChar           *flat;       // all the stack item names as a string for convenience
 };
 
 struct swish_Analyzer
 {
     unsigned int           maxwordlen;         // max word length
     unsigned int           minwordlen;         // min word length
     unsigned int           tokenize;           // should we parse into WordList
     swish_WordList*      (*tokenizer) (swish_Analyzer*, xmlChar*, ...);
     xmlChar*             (*stemmer)   (xmlChar*);
     unsigned int           lc;                 // should tokens be lowercased
     void                  *stash;              // for script bindings
     void                  *regex;              // optional regex
     int                    ref_cnt;            // for script bindings
 };
 
 struct swish_Parser
 {
     int                    ref_cnt;             // for script bindings
     swish_Config          *config;              // config object
     swish_Analyzer        *analyzer;            // analyzer object
     void                 (*handler)(swish_ParseData*); // handler reference
     void                  *stash;               // for script bindings
 };
 
 // TODO maybe store swish_Parser * here instead of separate config and analyzer
 struct swish_ParseData
 {
     xmlBufferPtr           buf_ptr;            // tmp text (MetaName) buffer
     xmlBufferPtr           prop_buf;           // tmp Property buffer
     xmlChar               *tag;                // current tag name
     swish_DocInfo         *docinfo;            // document-specific properties
     swish_Config          *config;             // global config
     unsigned int           context_as_meta;    // index tokens under all applicable MetaNames
     unsigned int           no_index;           // toggle flag for special comments
     unsigned int           is_html;            // shortcut flag for html parser
     unsigned int           bump_word;          // boolean for moving word position/adding space
     unsigned int           word_pos;           // word position in document
     unsigned int           offset;             // current offset position
     swish_TagStack        *metastack;          // stacks for tracking the tag => metaname
     swish_TagStack        *propstack;          // stacks for tracking the tag => property
     xmlParserCtxtPtr       ctxt;               // so we can free at end
     swish_WordList        *wordlist;           // linked list of words
     swish_NamedBuffer     *properties;         // buffer all properties
     swish_NamedBuffer     *metanames;          // buffer all metanames
     swish_Analyzer        *analyzer;           // Analyzer struct
     void                  *stash;              // for script bindings
 };
Global Functions
 void        swish_init();
 void        swish_cleanup();
I/O Functions
 xmlChar *   swish_slurp_stdin( long flen );
 xmlChar *   swish_slurp_file_len( xmlChar *filename, long flen );
 xmlChar *   swish_slurp_file( xmlChar *filename );
Hash Functions
 int         swish_hash_add( xmlHashTablePtr hash, xmlChar *key, void * value );
 int         swish_hash_replace( xmlHashTablePtr hash, xmlChar *key, void *value );
 int         swish_hash_delete( xmlHashTablePtr hash, xmlChar *key );
 xmlHashTablePtr swish_new_hash(int size);
Memory Functions
 void        swish_init_memory();
 void *      swish_xrealloc(void *ptr, size_t size);
 void *      swish_xmalloc( size_t size );
 void        swish_xfree( void *ptr );
 void        swish_mem_debug();
 xmlChar *   swish_xstrdup( const xmlChar * ptr );
 xmlChar *   swish_xstrndup( const xmlChar * ptr, int len );
Time Functions
 double      swish_time_elapsed(void);
 double      swish_time_cpu(void);
 char *      swish_print_time(double time);
 char *      swish_print_fine_time(double time);
Error Functions
 void        swish_set_error_handle( FILE *where );
 void        swish_fatal_err(char *msg,...);
 void        swish_warn_err(char *msg,...);
 void        swish_debug_msg(char *msg,...);
String Functions
 void                swish_verify_utf8_locale();
 int                 swish_is_ascii( xmlChar *str );
 int                 swish_utf8_chr_len( xmlChar *utf8 );
 wchar_t *           swish_locale_to_wchar(xmlChar * str);
 xmlChar *           swish_wchar_to_locale(wchar_t * str);
 wchar_t *           swish_wstr_tolower(wchar_t *s);
 xmlChar *           swish_str_tolower(xmlChar *s );
 xmlChar *           swish_str_skip_ws(xmlChar *s);
 void                swish_str_trim_ws(xmlChar *string);
 void                swish_debug_wchars( const wchar_t * widechars );
 int                 swish_wchar_t_comp(const void *s1, const void *s2);
 int                 swish_sort_wchar(wchar_t *s);
 swish_StringList *  swish_make_StringList(xmlChar * line);
 swish_StringList *  swish_init_StringList();
 void                swish_free_StringList(swish_StringList * sl);
Configuration Functions
 swish_Config *  swish_init_config();
 swish_Config *  swish_add_config( xmlChar * conf, swish_Config * config );
 swish_Config *  swish_parse_config( xmlChar * conf, swish_Config * config );
 swish_Config *  swish_parse_config_new( xmlChar * conf, swish_Config * config );
 int             swish_debug_config( swish_Config * config );
 xmlHashTablePtr swish_subconfig_hash( swish_Config * config, xmlChar *key);
 int             swish_config_value_exists( swish_Config * config, xmlChar *key, xmlChar *value );
 xmlChar *       swish_get_config_value(swish_Config * config, xmlChar * key, xmlChar * value);
 void            swish_free_config(swish_Config * config);
 swish_ConfigValue * swish_keys( swish_Config * config, ... );
 swish_ConfigValue * swish_value( swish_Config * config, xmlChar * key, ... );
 swish_ConfigValue * swish_init_ConfigValue();
 void                swish_free_ConfigValue( swish_ConfigValue * cv );
 xmlHashTablePtr swish_mime_hash();
 xmlChar *       swish_get_mime_type( swish_Config * config, xmlChar * fileext );
 xmlChar *       swish_get_parser( swish_Config * config, xmlChar *mime );
Parser Functions
 swish_Parser *  swish_init_parser(  swish_Config * config, 
                                     swish_Analyzer * analyzer, 
                                     void (*handler) (swish_ParseData *),
                                     void *stash                                 
                                     );
 void  swish_free_parser( swish_Parser * parser );
 int swish_parse_file(   swish_Parser * parser,
                         xmlChar *filename,
                         void * stash );
 int swish_parse_stdin(  swish_Parser * parser,
                         void * stash  );
 int swish_parse_buffer( swish_Parser * parser,
                         xmlChar * buf, 
                         void * stash  );
Token Functions 
 void                swish_init_words();
 swish_WordList *    swish_init_wordlist();
 void                swish_free_wordlist(swish_WordList * list);
 swish_WordList *    swish_tokenize( swish_Analyzer * analyzer, xmlChar * str, ... );
 
 swish_WordList *    swish_tokenize_utf8_string(
                                       swish_Analyzer * analyzer,  
                                       xmlChar * str,
                                       unsigned int offset,
                                       unsigned int word_pos,
                                       xmlChar * metaname, 
                                       xmlChar * context
                                       );
 
 swish_WordList *    swish_tokenize_ascii_string(   
                                       swish_Analyzer * analyzer, 
                                       xmlChar * str,
                                       unsigned int offset,
                                       unsigned int word_pos,
                                       xmlChar * metaname, 
                                       xmlChar * context
                                       );
 
 swish_WordList *    swish_tokenize_regex(
                                       swish_Analyzer * analyzer, 
                                       xmlChar * str,
                                       unsigned int offset,
                                       unsigned int word_pos,
                                       xmlChar * metaname, 
                                       xmlChar * context
                                       );
                                         
 size_t              swish_add_to_wordlist(  swish_WordList * list, 
                                             xmlChar * word,
                                             xmlChar * metaname,
                                             xmlChar * context,
                                             int word_pos, 
                                             int offset );
 
 int                 swish_add_to_wordlist_len(  
                                             swish_WordList * list, 
                                             xmlChar * str,
                                             int len,
                                             xmlChar * metaname,
                                             xmlChar * context,
                                             int word_pos, 
                                             int offset );
                                             
 void                swish_debug_wordlist( swish_WordList * list );
Analyzer Functions
 swish_Analyzer *    swish_init_analyzer( swish_Config * config );
 void                swish_free_analyzer( swish_Analyzer * analyzer );
DocInfo Functions
 swish_DocInfo *     swish_init_docinfo();
 void                swish_free_docinfo( swish_DocInfo * ptr );
 int                 swish_check_docinfo(swish_DocInfo * docinfo, swish_Config * config);
 int                 swish_docinfo_from_filesystem(  xmlChar *filename, 
                                                     swish_DocInfo * i, 
                                                     swish_ParseData *parse_data );
 void                swish_debug_docinfo( swish_DocInfo * docinfo );
 xmlChar *           swish_get_file_ext( xmlChar *url );
Buffer Functions
 swish_NamedBuffer * swish_init_nb( swish_Config * config, xmlChar * configKey );
 void                swish_free_nb( swish_NamedBuffer * nb );
 void                swish_debug_nb( swish_NamedBuffer * nb, xmlChar * label );
 void                swish_add_buf_to_nb( swish_NamedBuffer *nb, 
                                          xmlChar * name,
                                          xmlBufferPtr buf, 
                                          xmlChar * joiner,
                                          int cleanwsp,
                                          int autovivify);
 void                swish_add_str_to_nb( swish_NamedBuffer * nb, 
                                          xmlChar * name, 
                                          xmlChar * str,
                                          unsigned int len,
                                          xmlChar * joiner,
                                          int cleanwsp,
                                          int autovivify);
 void                swish_append_buffer( xmlBufferPtr buf, xmlChar * txt, int len );
DESCRIPTION

libswish3 is the core C library of Swish3 .

libswish3 uses the GNOME Libxml2 library to parse words and metadata from XML, HTML and plain text files. libswish3 supports full UTF-8 encoding.

libswish3 is a parsing tool for use with information retrieval (IR) libraries. Dynamic language bindings are available in the source distribution in the bindings directory.

APIs

The following APIs are defined:

Parsing API

libswish3 provides three basic input functions:

  • swish_parse_file()

  • swish_parse_fh()

  • swish_parse_buffer()

Each of these functions takes a swish_Parser struct pointer and optional user_data .

In addition:

  • The swish_parse_file() function takes a file path, which must be a valid file. Directories and links are not supported. The a