Balisage Paper: TCS tcs: Tata Consultancy Services trash compactor script

Dale Waldt suggested starting with all XPaths (presumably FQGI, fully qualified generic identifier, ancestry paths) in a larger set, and finding an example of each.

Paul Ryan said he automated the extraction of all XPaths (again, presumably FQGIs) and automatically created Lorem Ipsum text.

Murray Maloney spoke of running all variations, as determined by the possibilities allowed by the Schema.

John Cowan talked about how, with LexisNexis, it was easy to get a firehose blast of volumes of data. He talked about crafting a sample document that was actually true facts, though a constructed sample.

Robert Stuart advised against real, or real-looking data, having once had an intelligence agency get upset with him when he to closely simulated, using public sources, the look of secret documents.

Syd Bauman said that when he needs a set of test documents to exercise a collection, he typically starts by cutting out the uninteresting TEI header metadata, and then keeping the first few paragraphs of each of several document. When he needs to generate test data about an instance he tends to need to be much pickier about which bits he keeps, and, in general, he does this by hand.

For the cases where content could not be shared, Syd also mentioned that Elliotte Rusty Harold had presented an XML Randomizer that worked like a neutron bomb on XML documents (my inappropriate analogy), scrambling the content but leaving the structures intact. [Harold]

Debbie Lapeyre warned against taking the first ten pages, and relayed a anecdote in which the last thousand pages were very different from the first ten.

Ian Gorman described taking all available content as the universe from which to choose. If I understood correctly, this is the approach automated by the current paper.

Plausible results. The hope is that the results will feel natural: compact, but recognizable.

Good defaults. The default parameter settings should hit some kind of sweet spot. Is it presumptious to imagine that such a sweet spot exists? I imagine it to be something like this: one can say that the sample is complete and that at the same time it is manageably short.

Single dial. Given the trade-offs between brevity and completeness, it would be nice to have a single parameter that simultaneously adjusted all the other parameters towards one extreme or the other.

Ease over perfection. If the occassional result is invalid, because of a wrong guess about required elements, that's probably okay.

Use information from schema. If there is a schema available, it would be nice to take advantage of it. The goal would not to be to include elements only because they exist in the schema, but to avoid deleting elements that are required by the schema.

Intuit schema. My guess is that in most real-life situations, required elements can be easily intuited. For example, if every section contains a title, it's reasonable to guess that title is required in section. Of course this rule of thumb can fail in one of two ways:

Regex text trimming. The current implementation keeps the first few words and the last few words of each text node. The regular expression processing to acheive this appears to be slow. My guess is that it has to do with backtracking, and might be improved by simply taking the first few words and not looking to keep the last.

Best time to trim text. In the naïve expectation that reducing the amount of text to be processed by subsequent passes would be an efficiency gain, the first pass does the trimming of the text nodes. But only a small number of text nodes are retained in the end, so it turns out to be more efficient to prune the tree first before abbreviating the text nodes.

The truth is that the most useful results might come from untrimmed text.

N-squared comparison to previous elements. Unlike text trimming, which isn't essential to the process, finding unique signatures is the purpose of the script, so it can't be skipped. The first implementation of the script used a comparison of the current tcs:signature with all the tcs:signatures on the with preceding axis. This obviously introduces an order n ² inefficiency. The second attempt involved using a key to map signatures to elements, and an intersect to detect if the set of similar signatures includes elements that overlap with the preceding axis. This is someone more efficient, but on the same order.

In order to work with large data sets, this needs to be resolved. The current solution is to use a non-XSLT streaming pass. The current implementation is not XML-aware, programmed using Perl regular expressions. It could be done using a streaming XML parser, but unless there are tcs:signature attributes that aren't actually markup in the documents, there will be no problem.

Multiple passes vs complicated XPath. The current implementation consists of several passes as outlined above. In order to accommodate a non-XSLT streaming pass in the middle, the first pass is in a separate script from the last passes. It's almost certainly the case that several of these calculations could be strung together in a more complicated XPath expression. This might be easier to understand, or not. And it might be more efficient, or not. I imagine it might be elegant, in a way.

Ancestor count. How much context should be included in an element's signature? Measured on a scale of zero to infinity, with 0 representing no ancestry, 1 representing the the parent of the current element, 2 representing the grandparent and parent, 7 presumed to be the largest number ever needed short of 8 which is taken to represent infinity (at a ninety-degree angle). Infinity seems to be a good default, as some XML processing operates on fully-qualified generic identifiers. Also, it's common for deeply nested elements have a tendency to stress stylesheets and other processing.

Preceding-sibling count. How many preceding siblings should be included in an element's signature? A good default seems to be 1, looking only at the closest preceding sibling.

Self count. Should the element name itself be include in its own signature? Surely the answer should be yes in most applications. For consistency, this parameter is included, on a scale from 0 (no) to 1 (yes).

Attribute count. Should the element's specified attributes count as part of its signature? Measured on a scale of 0 (no) to 8 (all of them), with no sensible meaning for the numbers in between. The current script has a bug in that it doesn't sort the attribute names as it should. A good default seems to be to include the attributes names.

Child count. How many children should be included an element's signature? Again, this parameter is measured on a scale of 0 = none to 8 = infinity. The children are counted out in document order. The thought here is to distinguish between a section that starts with a number from a section that starts with a title. An overlapping effect can sometimes also be achieved by using using the preceding-sibling parameter: including a section not on its own merits, but because it contains a title that follows a number.

Start words count. How many words should kept at the start when abbreviating a text node?

Middle words count. What is the minimum number of words to delete from the middle of a text node? If there are less than this number of words in the middle, don't abbreviate.

End words count. How many words should be kept at the end when abbreviating a text node? So, a text node is not abbreviated unless it contains start + middle + end words. Though these parameters are still available in the full code, more readable results are found more efficiently by simply taking the first sentence of each text node. This is the approach taken in the simplified code below.

Repetition count. How many times would we like to see each signature? Since we may want to reduce a very large corpus to a still large sample, it doesn't make sense to follow the silly pattern of the other parameters, insisting that after 7 comes infinity. One discovery, working with the tool, is that the most effective way to get a bulkier sample is to include higher values for the various context parameters. This way, in addition to being simply bulkier, the extra included elements will show more variety. For this reason, the chosen default value is 1.

Show deletions. Should comments be left in the sample to indicate where elements have been pruned? It can be helpful, when working with a smaller sample, to have indication of where elements have been deleted from the larger source. As implemented, the integer parameter is interpreted as a Boolean. But it might make sense to interpret as a number: showing some number of comments before stopping. To avoid overwhelming results, the default value is 0 = no.

Debug signatures. Should the intermediate element signatures be shown in the final output? Like with the parameters above and below, it would make sense to interpret this value as a integer, rather than as a Boolean. The default value here is 0, meaning no tcs:signatures are shown.

Debug marks. Should the intermediate tcs:mark attributes be shown? Again, this integer parameter might make better sense interpreted as a count, rather than interpreted as a Boolean. The tcs:mark attributes are added to all elements that are to be kept, with the value indicating the reason. Reasons include that the element had a unique signature (or was within the specified repetition count), that the element had a descendent that was to be kept, that the element was known or guessed to be a required child of a kept element, or that the element was an textual inline in the middle of kept text. The default value is 0, meaning no intermediate tcs:mark attributes are shown.

Collapse parallel structures.

Target length.

Schema information.

Text abbreviation.

Pointers. It would be nice to link the samples, element-by-element, back to the full corpus, so that you could see the full context if curious.

Randomize. Liam Quinn suggested that if you are taking a small sample from a larger set, it would be nice to be be able to randomize the selection, rather than just taking the first examples of each markup combination.

Log the seed. As a follow-on suggestion, Lee says to log the seed used for the random selection, so that it can be recreated as required.

Redo from back. Wendell Piez observed that in order to avoid redundant elements, in which for example, the first paragraph is included because we've never seen a paragraph before, but the second paragraph is included because it contains an inline, we can run the algorithm twice: once front to back and then a second time back to front.

XQuery. There seemed to be general consensus that multiple passes were the natural approach, and that any attempt to collapse this into a single XPath expression or XQuery was misguided.

Xmlsh. David Lee said the individual passes could be run together with xmlsh. This would be especially relevant if the inefficient have-I-seen-this-before pass were recast using another programming language.

Efficiency. Michael Sperberg-McQueen said that the n² inefficiency could be solved, even in XSLT 1.0, using keys and Muenchian method. [Tennison]

Accummulators. Abel Braaksma said that XSLT 3.0 accumulators were designed to solve problems just like the have-I-seen-this-before inefficiency, and took the example back to the XSLT working group.

My initial intuition was to add the current element's signature to the accumulated set as the element starts. But this is too soon, as we need to know about all preceding elements, not including the one we're on. On the other had, updating the accumulator at the end of the element would be too late, as we would not have had its signature as we reviewed all of its descendants. The naive fix would be to somehow put the current element's signature on deck so that it can be folded in to the accumulated list of all signatures as soon we hit the start of the next element. Rather than building this data structure ourselves, the elegant choice seems to be to avoid the temptation to add the current element's signature to the accumulated set, but to rather add the immediately preceding element's signature to the accumulator.