Patent decision

BL number

O/285/09

Concerning rights in

GB0608420.6

Hearing Officer

Mr P Slater

Decision date

18 September 2009

Person(s) or Company(s) involved

Roke Manor Research Limited

Provisions discussed

PA 1977 Section 1(2)

Keywords

Excluded fields (refused)

Related Decisions

None

Summary

The invention relates to a method of searching for user-specified strings of characters, or keywords in an input data stream using a finite state machine based on an Aho-Corasick algorithm. User-specified keywords are used to construct the state machine in the form of a “tree” structure having branches representing each of the user’s keywords into which the input data stream is then fed. The machine providing an output each time a match is detected between any of the specified keywords and the input data.

In prior-art systems, problems arise when the user adds to, deletes or changes the keywords in some other way which requires the state machine to be rebuilt or recompiled. This can take a considerable amount of time and processing power to achieve particularly, as in the prior-art, where the state machine is said to be built-up in a “breadth first” manner when the addition of new keywords requires all of the state transitions to be updated. For large keyword sets the computational cost of updating the entire structure is often excessive, requiring significant buffering of data or delays in processing the input data stream which may result in the loss of data, and may even prevent the structure from being updated whilst online.

The application provides a new method of constructing an Aho-Corasick state machine wherein the tree structure is built-up in a “depth first” manner, a branch at a time corresponding to any new keywords added by the user and requires only those states or nodes associated with that branch to updated. This allegedly requires no buffering or loss of data and enables real-time online processing of the input data stream.

The hearing officer considered the four-step test in Aerotel/Macrossan in the light of the Symbian judgment, and found the contribution to relate to computer program for transferring and converting data between various schema or formats. The Hearing Officer could find no technical contribution and so refused the application under Section 18(3).