- From: Graham Klyne <GK@ninebynine.org>
- Date: Tue, 28 Oct 2003 10:43:23 +0000
- To: "Jeremy Carroll" <jjc@hplb.hpl.hp.com>, "Martin May" <maym@foobar.lu>, "Rahul Singh" <kingtiny@cs.cmu.edu>
- Cc: <www-rdf-interest@w3.org>
At 10:57 28/10/03 +0100, Jeremy Carroll wrote: >A linear search for the namespace uri can be quite efficient (I don't have >the reference for the technique for searching for a long fixed substring, >but you only have to look at a few of the characters). You then need to work >back from there to see if the rdf:RDF matches. This sounds like the Knuth-Morris-Pratt algorithm; Google returns many hits, e.g. http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Essentially, a finite state automaton is constructed to look for the substring, skipping any parts of the target string that are known not to be a possible match. (A similar technique is often used for efficient regular expression matching.) #g -- ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
Received on Tuesday, 28 October 2003 05:57:37 UTC