EFFICIENT STORAGE FOR FINITE STATE MACHINES

• US 20090228502A1
• Filed: 03/05/2008
• Published: 09/10/2009
• Est. Priority Date: 03/05/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lambov, Branimir Z.
• Granted Patent: US 7,949,679 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 of a finite state machine, the method comprising:

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.

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, further comprising transforming a dictionary of words into the machine.

6. The method according to claim 5, further comprising:

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

listing contents of the dictionary.

9. The method according to claim 1, further comprising receiving an initial input of the machine.

10. The method according to claim 1, further comprising determining whether a subsequently inputted word is defined.

11. The method according to claim 3, further comprising issuing an error message indicating that the subsequently inputted word is not defined.

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

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;

reducing the 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.

8. A method of operating a storage of a finite state machine, 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; and

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

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

13. A method of operating a storage of a finite state machine, 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; and

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

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

a storage unit 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; and

a generating unit configured to generate 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.

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

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

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

18. The finite state machine according to claim 14, further comprising a data compressing unit configured to compress the generated payload-transition matrix in a row-displaced format.

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