Programmable hardware finite state machine for facilitating tokenization of an XML document
US7596745B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 14, 2005 |
| Grant date | Sep 29, 2009 |
| Priority date | — |
| Expiry date | Nov 29, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06N5/022
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A hardware finite state machine for facilitating the processing of an XML (Extensible Markup Language) document or other structured data stream. An accelerator is implemented in hardware to enable fast processing of a document (or a segment thereof). The accelerator includes a finite state machine that embodies a ternary CAM (Content-Addressable Memory) and associated RAM (Random Access Memory). Processing of the document is divided into multiple states, with each state transition defined by a markup delimiter that triggers the transition. The CAM is programmed with entries containing the processing states and, for each possible transition from that state, a pattern for matching delimiters that trigger the possible transitions. For a CAM entry matching the current processing state and a sequence of characters from the document, which may contain a delimiter, the associated RAM identifies the next state and any action to be taken (e.g., to shift the sequence of characters).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.