W3C home > Mailing lists > Public > www-rdf-interest@w3.org > October 2003

RE: Attaching (embedding?) RDF

From: Graham Klyne <GK@ninebynine.org>
Date: Tue, 28 Oct 2003 10:43:23 +0000
Message-Id: <>
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.)


Graham Klyne
For email:
Received on Tuesday, 28 October 2003 05:57:37 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:44:45 UTC