Efficient storage for finite state machines

• US 7,949,679 B2
• Filed: 03/05/2008
• Issued: 05/24/2011
• Est. Priority Date: 03/05/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lambov, Branimir Z.
• Primary Examiner(s): Thai; Hanh B
• Application Number:
  US12/042,566
• Publication Number:
  US 20090228502A1
• Time in Patent Office: 1,175 Days
• Field of Search: 707/101, 707/802, 704/2, 704231-232, 704/251, 704/255, 710/8, 710/23, 711/147, 715/531
• US Class Current: 707/790
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method of operating a storage of a finite state machine includes organizing information concerning an operation of the machine in a payload-transition matrix, in which a given number of columns of the matrix reflect features of a state of the machine and other columns describe valid transitions between the states of the machine depending on input characters, and compressing the payload-transition matrix in a row-displaced format.

Claims

1. A method of operating a storage unit of a finite state machine, the storage unit comprising:

a computer readable medium having executable instructions stored thereon to execute the method, the method comprising;

organizing information concerning an operation of the machine in a payload-transition matrix, in which at least a first column is a finality vector indicating an end of data defined by the payload-transition matrix, a second column indicates production values of the data and other columns describe valid transitions between states of the machine depending on input characters; and

compressing the payload-transition matrix in a row-displaced format associating the finality vector, the production values and each state with a unique base index.

2. The method according to claim 1, wherein the machine comprises a deterministic finite state automaton.

3. The method according to claim 1, wherein the machine comprises a subsequential transducer.

4. The method according to claim 1, wherein the machine comprises a non-deterministic finite state transducer.

5. The method according to claim 1, wherein the method further comprises transforming a dictionary of words into the machine.

6. The method according to claim 5, further wherein the method further comprises:

testing the machine to determine whether a word appears in the dictionary; and

listing contents of the dictionary.

7. A method of operating a storage unit of a finite state machine, the storage unit comprising:

a computer readable medium having executable instructions stored thereon to execute the method, the method comprising;

organizing information concerning an operation of the machine in a payload-transition matrix, in which at least a first column is a finality vector indicating an end of data defined by the payload-transition matrix, a second column indicates production values of the data and other columns describe valid transitions between states of the machine depending on input characters;

reducing an alphabet of the machine by converting each of the valid transitions into a set of valid sub-transitions; and

compressing the payload-transition matrix in a row-displaced format associating the finality vector, the production values and each state with a unique base index.

8. A method of operating a storage unit of a finite state machine, the storage unit comprising:

a computer readable medium having executable instructions stored thereon to execute the method, the method comprising;

where the machine includes a set of words that have been converted into data that is characterized by a set of states linked by transitions specifying permissible input characters, generating a payload-transition matrix in which a given number of columns of the matrix reflect features of a state of the machine and other columns describe valid transitions between the states of the machine depending on input characters;

compressing the payload-transition matrix in a row-displaced format;

determining whether a subsequently inputted word is defined; and

issuing an error message indicating that the subsequently inputted word is not defined.

9. The method according to claim 8, wherein the method further comprises receiving an initial input of the machine.

10. A computer readable medium having executable instructions stored thereon to execute the method according to claim 8.

11. A method of operating a storage unit of a finite state machine, the storage unit comprising:

a computer readable medium having executable instructions stored thereon to execute the method, the method comprising;

where the machine includes a set of words have been converted into data that is characterized by a set of states linked by transitions specifying permissible input characters, generating a payload-transition matrix in which a given number of columns of the matrix reflect features of a state of the machine and other columns describe valid transitions between the states of the machine depending on input characters;

reducing the alphabet of the set of the words by secondarily converting each of the transitions into a set of sub-transitions;

compressing the payload-transition matrix in a row-displaced format;

determining whether a subsequently inputted word is defined; and

issuing an error message indicating that the subsequently inputted word is not defined.

12. A storage system for a finite state machine comprising:

a storage unit including a computer readable medium having executable instructions stored thereon, which is configured to store the machine including data of a set of words that have been converted into data that is characterized by a set of states linked by transitions specifying permissible input characters;

a generating unit configured to generate a payload-transition matrix, in which at least a first column is a finality vector indicating an end of each of the words, a second column indicates production values of the words and other columns describe valid transitions between states of the machine depending on input characters; and

a data compressing unit configured to compress the generated payload-transition matrix in a row-displaced format associating the finality vector, the production values and each state with a unique base index.

13. The finite state machine according to claim 12, further comprising a receiving unit configured to receive an initial input of the machine.

14. The finite state machine according to claim 12, further comprising a processor configured to determine whether a subsequently inputted word is defined.

15. The finite state machine according to claim 14, wherein the processor is further configured to issue an error message indicating that the subsequently inputted word is not defined.

16. The finite state machine according to claim 12, wherein the data compressing unit is further configured to reduce a size of an alphabet of the words.