Title:
METHOD AND CHIP STRUCTURE FOR MATCHING MULTI-CHARACTER STRING
Document Type and Number:
WIPO Patent Application WO/2008/141519
Kind Code:
A1
Abstract:
A method for matching multi-character strings based on a cache state machine
as well as a chip structure for matching multi-character strings are disclosed,
wherein the chip structure is realized by a method and structure for searching
a next state. The method for matching multi-character strings searches the next
state in a state transformation rule database based on input characters, a current
state and cached states then jumps, and caches the state by specific cache rules.
In the chip structure for matching multi-character strings, a main memory which
includes basic transformation rules and n step cross transformation rules and
an input translation table are shared by two paths of a state register, a color
register and a state cache, a color cache, so as to calculate the possible next
state and acquire corresponding input characters. An auxiliary memory, which
stores fail and restart transformation rules, is used to acquire the next state
corresponding to the actual input and updates the state cache and the color cache.
Tri-state selector implements multi-way selection of the next state based on
the actually input character and the character corresponding to the possible
next state, so as to update the state registers and color registers.
More Like This:
Inventors:
SONG TIAN (CN)
Application Number:
PCT/CN2008/000293
Publication Date:
November 27, 2008
Filing Date:
February 03, 2008
Export Citation:
Assignee:
BEIJING ZHEAN TECHNOLOGY CORP (CN)
SONG TIAN (CN)
SONG TIAN (CN)
International Classes:
G06F17/30
Foreign References:
| CN1801152A | 2006-07-12 | |||
| JP2002297681A | 2002-10-11 | |||
| US4241402A | 1980-12-23 | |||
| US6961693B2 | 2005-11-01 | |||
| CN101051321A | 2007-10-10 |
Other References:
AHO A.V. AND CORASICK M.J.: "Efficient String Matching: An Aid to Bibliographic Search", COMMUNICATIONS OF THE ACM, vol. 18, no. 6, June 1975 (1975-06-01), pages 333 - 340, XP001152117
Attorney, Agent or Firm:
BEIJING ZHONGYUAN HUAHE INTELLECTUAL PROPERTY AGENCY CO., LTD. (Huibin BuildingNo.8 Beichendong Street,Chaoyang, Beijing 1, CN)
Download PDF:
Previous Patent: A DISTRIBUTING METHOD FOR CARRIER POWER IN THE SAME POWER AMPLIFIER AND A POWER AMPLIFIER
Next Patent: MULTIFUNCTIONAL ELECTRONIC OVEN
Next Patent: MULTIFUNCTIONAL ELECTRONIC OVEN