I am aware of at least two very efficient algorithms:
1. Using *suffix-trees* -- all possible suffixes of the given
string are organized as a trie. The search (same as the contains()
function) is very fast.
But whether we are talking about searching for elements, or searching for
substrings, the designer of an XPath engine has to make choices about the
trade-off between tree-building time, tree-searchiing time, space occupied by
the tree, and size of the XPath engine itself.
For documents stored in a database, the developers generally delegate some of
these decisions to the database designer, asking them to choose what index
structures to build.
For documents held transiently in memory, building indexes like a suffix-tree
is very unlikely to be cost-effective unless you know that the same data will
be processed in this kind of way very frequently.
Whatever engineering choices are made, they are likely to vary significantly
from one XPath engine to another, which makes Roger's question completely
meaningless.
Michael Kay
Saxonica
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--