BAILII is celebrating 24 years of free online access to the law! Would you consider making a contribution?
No donation is too small. If every visitor before 31 December gives just £1, it will have a significant impact on BAILII's ability to continue providing free access to the law.
Thank you very much for your support!
 |
[Home] [Databases] [World Law] [Multidatabase Search] [Help] [Feedback] | |
United Kingdom Intellectual Property Office Decisions |
||
|
You are here: BAILII >> Databases >> United Kingdom Intellectual Property Office Decisions >> Roke Manor Research Limited (Patent) [2009] UKIntelP o28509 (18 September 2009) URL: http://www.bailii.org/uk/cases/UKIntelP/2009/o28509.html Cite as: [2009] UKIntelP o28509 |
||
[New search] [Printable PDF version] [Help]
For the whole decision click here: o28509
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).
