Patent ID: 7769788
Filing Date: 2010-08-03
Classification: G06F

Abstract:
1. A method of searching a text to locate occurrences of user specified patterns of words or phrases comprising character strings, said method comprising: receiving an input comprising user specified patterns that are to be searched for; based on said user specified patterns, constructing a finite state pattern matching machine that includes an Aho-Corasick tree having branches that comprise nodes connected by paths, go to links and failure links; processing the text according to said finite state pattern matching machine to locate matches to the user specified patterns; and said state pattern matching machine outputting locations in said text string where said specified patterns appear; wherein, said finite state pattern matching machine is constructed first in a general depth first manner, for each path comprising links representing a single user specified pattern; said step of constructing said Aho-Corasick tree in said finite state pattern matching machine comprises a) forming a root; b) starting from the root, building a series of nodes, paths and links that corresponds to a specified pattern comprising a character string, said building being performed depth-wise from the root by c) repeating steps i) and ii) for each node of a current string; d) repeating steps b) and c) for each new string inserted into the finite state pattern matching machine; step b) ii) I) comprises, s) finding the longest suffix of a newly inserted branch that matches a prefix of an existing or the current branch, and if the prefix exists, then for each path emerging from a node that represents the prefix, creating a corresponding path from the inserted node that leads to the same destination; t) taking the next shortest suffix and repeat the step s), but not overwriting any that were created in the previous step; and u) continuing until all the suffixes have been exhausted including an empty suffix; and step b) ii) II comprises, v) identifying existing nodes which have been affected by the insertion of the new node; w) reapplying the steps s), t) and u) to each of the affected nodes in a depth first manner by forming a string from a concatenation of path labels leading from the root to a corrupt nodes; x) reapplying steps s) t) and u) with the corrupt node taking the role of a current node; and y) if there is already a path emerging from the corrupt node that is labeled with the same character as one of the paths emerging from the prefix node, then if said path leads to a child of the corrupt node do not overwrite it, and otherwise setting the path to point at the destination referenced from the node that represents the prefix.