Balisage Paper: Serverless Searching with XSLT and JavaScript

Cleaning and Pre-Processing

What we refer to as the "tokenization" process is a bit of a misnomer: it refers to a single monolithic stylesheet—tokenize.xsl—that processes each source document in multiple passes in order to create the minimal HTML structure necessary for generating the index.^[6] The first stage in the process is to remove irrelevant content, retaining only the information that is necessary for the indexing process and removing ignored elements, unnecessary wrappers, and most attributes. In most cases, input documents will contain a significant amount of boilerplate HTML that appears on every page and should be completely ignored by the indexer, like the site menu, sidebar, or footer. As the example above shows, these elements are given a weight of 0, which means they are removed from the tokenized document. The tokenization process also removes elements that will have no bearing on the indexing process; this includes most inline elements, like links, spans, etc, unless these elements must be retained for a specific reason (i.e. they are assigned a higher weight or they contain a fragment identifier, which can be linked from the search results).

Often, a well-configured instance of staticSearch will produce tokenized documents that are significantly smaller than the original. For example, consider this line from a poem in the Digital Victorian Periodical Poetry Project:

                        
<div class="l" data-el="l" id="l_1"><span class="lineContent"><span data-el="hi" class="hi" style="font-variant: small-caps; letter-spacing: 0.06em;">A blush</span>, a smile, a dusk sweet vio<span class="rhyme label_a" data-el="rhyme" title="Masculine rhyme (Final syllable rhymes exactly; for example, Keats/beets.); label: a">let</span>—</span><span class="lineNum">1</span></div>

After being run through the tokenizer, all classes, data attributes, superfluous wrapping elements, and other information irrelevant to the indexer are removed:

                        
<div id="l_1" ss-ctx="true">A <span ss-pos="3" ss-fid="l_1" ss-stem="blush">blush</span>, a <span ss-pos="4" ss-fid="l_1" ss-stem="smile">smile</span>, a <span ss-pos="5" ss-fid="l_1" ss-stem="dusk">dusk</span> <span ss-pos="6" ss-fid="l_1" ss-stem="sweet">sweet</span> <span ss-pos="7" ss-fid="l_1" ss-stem="violet">violet</span>—</div>

Stemming

The second process is, of course, tokenization. The tokenization stage wraps each token in a span element and decorates the element with the token’s stem, position, weight, et cetera. Each meaningful text node is matched and analyzed using <xsl:analyze-string> to identify each word where a word is understood as:

We also consider apostrophes and quotation marks (both straight and curly) as part of a word, so the constructed Regular Expression is slightly more complicated when expressed in the XSLT:

                        
 <xsl:variable name="numericWithDecimal">[<xsl:value-of select="string-join($allApos,'')"/>\d]+([\.,]?\d+)</xsl:variable>
 <xsl:variable name="alphanumeric">[\p{L}\p{M}<xsl:value-of select="string-join($allApos,'')"/>]+</xsl:variable>
 <xsl:variable name="hyphenatedWord">(<xsl:value-of select="$alphanumeric"/>-<xsl:value-of select="$alphanumeric"/>(-<xsl:value-of select="$alphanumeric"/>)*)</xsl:variable>
 <xsl:variable name="tokenRegex">(<xsl:value-of select="string-join(($numericWithDecimal,$hyphenatedWord,$alphanumeric),'|')"/>)</xsl:variable>

Which yields the the following:

(['‘’”“"\d]+([\.,]?\d+)|([\p{L}\p{M}'‘’”“"]+-[\p{L}\p{M}'‘’”“"]+(-[\p{L}\p{M}'‘’”“"]+)*)|[\p{L}\p{M}'‘’”“"]+)

If a word is indeed a word and is neither too short nor a stopword, it is then run through the user-configured XSLT stemmer. At the moment, staticSearch has four different stemmers: the Porter stemming algorithms for English and French (Porter 1980; Porter 2002; Porter French) ; an identity stemmer; and a diacritic stemmer, which simply strips diacritics and is otherwise idempotent.^[7] Users can specify their own stemmers, but, at the moment, the stemmers need to be implemented identically in both XSLT and JavaScript. We are currently exploring options for integrating existing implementations of Porter’s stemming algorithms in Java and JavaScript (for Saxon and the browser, respectively).

Stem Files

Here’s an example of the stem file for the term glow:

                        
{
    "stem": "glow",
    "instances": [
        {
            "docUri": "poems/twilight.html",
            "score": 1,
            "contexts": [
                {
                    "form": "glow",
                    "weight": "1",
                    "pos": 49,
                    "context": "Twilight for dreams, the dun and dying <mark>glow</mark>",
                    "fid": "l_9"
                }
            ]
        }
    ]
}

This contains an entry for each document which contains the stem, an overall score for that stem in that document, and precise information about each individual instance, including a keyword-in-context extract in which it is marked.

Each stem is created by grouping the entire set of stems by their @ss-stem value.

                        
<xsl:for-each-group select="$stems" group-by="string(@ss-stem)">
  <xsl:variable name="stem" select="current-grouping-key()" as="xs:string"/>
  <xsl:call-template name="makeTokenCounterMsg"/>
  <xsl:variable name="map" as="element(j:map)">
    <xsl:call-template name="makeMap"/>
  </xsl:variable>
  <xsl:result-document href="{$outDir}/stems/{$stem}{$versionString}.json" method="text">
    <xsl:sequence select="xml-to-json($map, map{'indent': $indentJSON})"/>
  </xsl:result-document>
</xsl:for-each-group>

The makeMap template takes each group of stems and creates an XML map in the JSON namespace^[8] for the file:

                        
    <xsl:template name="makeMap" as="element(j:map)">
        <!--The term we're creating a JSON file for, inherited from the createMap template -->
        <xsl:variable name="stem" select="current-grouping-key()" as="xs:string"/>
        <!--The group of all the terms (so all of the spans that have this particular term
            in its @ss-stem -->
        <xsl:variable name="stemGroup" select="current-group()" as="element(span)*"/>
        <!--Create the outermost part of the structure-->
        <map xmlns="http://www.w3.org/2005/xpath-functions">
           <!--The stem is the top level string key for this map; it should be
                the same as the JSON file name.-->
            <string key="stem">
                <xsl:value-of select="$stem"/>
            </string>
             <!--Start instances array: this contains all of the instances of the stem
                 per document -->
            <array key="instances">
                <!--If every HTML document processed has an @id at the root,
                    then use that as the grouping-key; otherwise,
                    use the document uri -->
                <xsl:for-each-group select="$stemGroup"
                    group-by="document-uri(/)">
                    <!--Sort the documents so that the document with the
                    most number of this hit comes first-->
                    <xsl:sort select="count(current-group())" order="descending"/>
                    <!--The current document uri, which functions
                    as the key for grouping the spans-->
                    <xsl:variable name="currDocUri" select="current-grouping-key()" 
                    as="xs:string"/>
                    <!--The spans that are contained within this document-->
                    <xsl:variable name="thisDocSpans" 
                    select="current-group()" as="element(span)*"/>
                    <!--Get the total number of documents 
                    (i.e. the number of iterations that this
                     for-each-group will perform) for this span-->
                    <xsl:variable name="stemDocsCount" select="last()" as="xs:integer"/>
                    <!--The document that we want to process
                            will always be the ancestor html of
                        any item of the current-group() -->
                    <xsl:variable name="thisDoc"
                        select="current-group()[1]/ancestor::html"
                        as="element(html)"/>
                    <!--Get the raw score of all the spans by getting the weight for 
                        each span and then adding them all together -->
                    <xsl:variable name="rawScore" 
                        select="sum(for $span in $thisDocSpans
                        return hcmc:returnWeight($span))"
                        as="xs:integer"/>
                        
                   <!--Map for each document that has this token-->
                    <map xmlns="http://www.w3.org/2005/xpath-functions">
                        <string key="docId">
                            <xsl:value-of select="$thisDoc/@id"/>
                        </string>
                        <!--And the relative URI from the document, which is to be used
                        for linking from the KWIC to the document. We've created this
                        already in the tokenization stage and stored it in a custom
                        data-attribute-->
                        <string key="docUri">
                            <xsl:value-of select="$thisDoc/@data-staticSearch-relativeUri"/>
                        </string>
                        <!--The document's score, forked depending on configured
                            algorithm -->
                        <number key="score">
                            <xsl:choose>
                                <xsl:when test="$scoringAlgorithm = 'tf-idf'">
                                    <xsl:sequence select="hcmc:returnTfIdf($rawScore, $stemDocsCount, $currDocUri)"/>
                                </xsl:when>
                                <xsl:otherwise>
                                    <xsl:sequence select="$rawScore"/>
                                </xsl:otherwise>
                            </xsl:choose>
                        </number>
                        <!--Now add the contexts array, if specified to do so -->
                        <xsl:if test="$phrasalSearch or $createContexts">
                            <xsl:call-template name="returnContextsArray"/>
                        </xsl:if>
                    </map>
                </xsl:for-each-group>
            </array>
        </map>
    </xsl:template>

Each stem files contains precise information about each individual instance in which that stem appears. This is the most onerous part of the process as each context contains the a keyword-in-context string, which shows this word in situ.

This has been difficult to optimize. Our approach so far has been to move up the tree and use node comparison operators (<< and >>) to compile all of the nodes that precede the span and the nodes that follow and then trim each string to the configured length.

This can still lead to very long strings being stored in memory, however, and so we have tried to optimize by iterating through each node using <xsl:iterate> and breaking once a string of the desired length has been found.

                        
    <xsl:function name="hcmc:returnSnippet" as="xs:string?">
        <xsl:param name="nodes" as="node()*"/>
        <xsl:param name="isStartSnippet" as="xs:boolean"/>
    
        <!--Iterate through the nodes: 
            if we're in the start snippet we want to go from the end to the beginning-->
        <xsl:iterate select="if ($isStartSnippet) then reverse($nodes) else $nodes">
            <xsl:param name="stringSoFar" as="xs:string?"/>
            <xsl:param name="tokenCount" select="0" as="xs:integer"/>
            <!--If the iteration completes, then just return the full string-->
            <xsl:on-completion>
                <xsl:sequence select="$stringSoFar"/>
            </xsl:on-completion>
            <xsl:variable name="thisNode" select="."/>
            <!--Normalize and determine the word count of the text-->
            <xsl:variable name="thisText" select="replace(string($thisNode),'\s+', ' ')" as="xs:string"/>
            <xsl:variable name="tokens" select="tokenize($thisText)" as="xs:string*"/>
            <xsl:variable name="currTokenCount" select="count($tokens)" as="xs:integer"/>
            <xsl:variable name="fullTokenCount" select="$tokenCount + $currTokenCount" as="xs:integer"/>
            
            <xsl:choose>
                <!--If the number of preceding tokens plus the number of current tokens is 
                    less than half of the kwicLimit, then continue on, passing 
                    the new token count and the new string-->
                <xsl:when test="$fullTokenCount lt $kwicLengthHalf + 1">
                    <xsl:next-iteration>
                        <xsl:with-param name="tokenCount" select="$fullTokenCount"/>
                        <!--If we're processing the startSnippet, prepend the current text;
                            otherwise, append the current text-->
                        <xsl:with-param name="stringSoFar" 
                            select="if ($isStartSnippet)
                                    then ($thisText || $stringSoFar) 
                                    else ($stringSoFar || $thisText)"/>
                    </xsl:next-iteration>
                </xsl:when>
                
                <xsl:otherwise>
                    <!--Otherwise, break out of the loop and output the current context string-->
                    <xsl:break>
                        <!--Figure out how many tokens we need to snag from the current text-->
                        <xsl:variable name="tokenDiff" select="1 + $kwicLengthHalf - $tokenCount"/>
                        <xsl:choose>
                            <xsl:when test="$isStartSnippet">
                                <!--We need to see if there's a space before the token we care about:
                                    (there often is, but that is removed when we tokenized above) -->
                                <xsl:variable name="endSpace" 
                                    select="if (matches($thisText,'\s$')) then ' ' else ()"
                                    as="xs:string?"/>
                                <!--Get all of the tokens that we want from the string by:
                                    * Reversing the current token sequence
                                    * Getting the subset of tokens we need to hit the limit
                                    * And then reversing that sequence of tokens again.
                                -->
                                <xsl:variable name="newTokens" 
                                    select="reverse(subsequence(reverse($tokens), 1, $tokenDiff))"
                                    as="xs:string*"/>
                                <!--Return the string: we know we have to add the truncation string here too-->
                                <xsl:sequence 
                                    select="$kwicTruncateString || string-join($newTokens,' ') || $endSpace || $stringSoFar "/>
                            </xsl:when>
                            <xsl:otherwise>
                                <!--Otherwise, we're going left to right, which is simpler
                                    to handle: the same as above, but with no reversing -->
                                <xsl:variable name="startSpace" 
                                    select="if (matches($thisText,'^\s')) then ' ' else ()"
                                    as="xs:string?"/>
                                <xsl:variable name="newTokens" 
                                    select="subsequence($tokens, 1, $tokenDiff)" 
                                    as="xs:string*"/>
                                <xsl:sequence
                                    select="$stringSoFar || $startSpace || string-join($newTokens,' ') || $kwicTruncateString"/>
                            </xsl:otherwise>
                        </xsl:choose>
                    </xsl:break>
                </xsl:otherwise>
            </xsl:choose>
        </xsl:iterate>
    </xsl:function>

Additional Files

In addition to the stem files, the build process also creates the following individual JSON files:

...|page||pairs||paragraph||part||parts||peep||People||per||percent||percentages||perhaps|...

Filter Files

In addition to the text search, the user can trigger the creation of a range of different search filter controls on the search page, by including some HTML meta tags with specific formats in the document. For example, if a document has these three meta tags:

                        
    <meta name="Document type" class="staticSearch_desc" content="Poems"/>
    <meta name="Document type" class="staticSearch_desc" content="Translations"/>
    <meta name="Date of publication" class="staticSearch_date" content="1895-01-05"/>

then the containing document will be classified as belonging to two document categories, Poems and Translations, in the Document type selection filter (which we refer to as a description filter). A second date range filter will also be created. If an end-user searches for documents in either of those categories, using a date-range that includes 1895-01-05, then this document will be selected. Other filter types include boolean, number range, and feature filters, which provide a typeahead searchable list of keywords. The build process creates a separate JSON file for each of these filters.

The JSON for a description filter looks like this (heavily truncated example):

                        
{
  "filterId": "ssDesc4",
  "filterName": "Poet’s nationality",
  "ssDesc4_1": {
    "name": "English",
    "docs": 
        ["poems\/p_1095_a_duet.html",
       "poems\/p_1099_the_ox.html"]
  },
  "ssDesc4_2": {
    "name": "Irish",
    "docs": 
    [ "poems\/p_8866_golden_lilies.html",
      "poems\/p_8825_in_a_cathedral.html"]
  }
}

When an end-user’s search makes use of a filter control, then required filter JSON will also be downloaded along with any stem files needed, but the filter files are also downloaded in the background on page load so that most are already available by the time a user has initiated a search.

When filters are combined with text search, the list of documents containing hits for the text search are first computed, then those hits are filtered based on the filter settings. The small size and innate compressibility of the JSON files enables staticSearch to produce results quite rapidly, even from relatively large document collections.