Method, system, and program for generating a table to determine boundaries between characters

• US 6,626,960 B1
• Filed: 09/01/1999
• Issued: 09/30/2003
• Est. Priority Date: 09/01/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Gillam, Richard Theodore
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Bieneman, Charles A.
• Application Number:
  US09/388,330
• Time in Patent Office: 1,490 Days
• Field of Search: 707/521, 707/530, 707/531, 707/532, 382/229, 382/230, 382/231, 704/8, 704/9, 704/10
• US Class Current: 715/201
• CPC Class Codes: G06F 40/177 of tables; using ruled lines

Abstract

Disclosed is a system, method, and program for generating a table for use by a computer in determining a location of a boundary, such as a word boundary, between two characters in text. A first table indicates a boundary between characters when processing text in a first direction, such as the forward direction. A second table is generated based on the content of the first table. The second table can be used to determine whether one boundary is located between any two consecutive characters processed in a second direct ion, such as the backward direction.

Claims

1. A method for generating a table for use by a computer in determining a location of a boundary between two characters, comprising:

receiving a first table indicating a boundary between characters when processing text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character, and wherein, for the first table, the rows indicate a current state, the columns indicate an input character, a non-empty row/column value indicates the a row including the a next state, and an empty row/column value indicates a boundary following the a current state;

automatically generating a second table based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein generating the second table comprises;

generating the second table using the columns from the first table as the columns and rows of the second table; and

indicating an absence of the a boundary at a column/row value in the second table if the a corresponding column/row value in the first table indicates the a next state; and

using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

2. A method for generating a table for use by a computer in determining a location of a boundary between two characters, comprising:

receiving a first table indicating a boundary between characters when processing text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character, and wherein a row/cell value in the first table indicates the a row including the a next state based on the a current state indicated in the row and the input character indicated in the column;

automatically generating a second table based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein generating the second table comprises;

determining, for each column i and row j pair in the first table, whether a column i, row j value cell in the first table is empty;

setting a variable k to a value of the column i, row j value cell in the first table if the cell is not empty;

determining, for each column l, whether a row k, column 1 cell in the first table is empty; and

setting the a value of a column l, row i value cell in the second table to indicate no boundary between a first character of the a type indicated in column 1 of the second table and a second character of the a type indicated in row i of the second table; and

using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

3. A method for generating a table for use by a computer in determining a location of a boundary between two characters, comprising:

receiving a first table indicating a boundary between characters when processing text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character;

automatically generating a second table based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein the second table is a paired comparison table implemented as a state machine; and

using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

4. A method for generating a table for use by a computer in determining a location of a boundary between two characters, comprising:

receiving a first table indicating a boundary between characters when processing text in a first direction, wherein the boundary is a member of a set of boundaries between characters consisting of;

word boundaries, sentence boundaries, syllable boundaries, and paragraph boundaries;

automatically generating a second table based on the a content of the first table, wherein generating the second table comprises;

adding a new first row to the second table;

inserting, for each column i in the new first row of the second table, a value of i plus one;

performing, for each row j greater than two and column i in the second table;

(i) determining whether a row j, column i cell in the second table is empty; and

(ii) setting a value of the row j, column i cell in the second table to i plus one if the row j, column i cell in the second table is empty; and

using the second table to determine whether one boundary is located between any two consecutive characters processed in a second direction.

5. A system for generating a table for use in determining a location of a boundary between two characters, comprising:

a processor;

a memory accessible to the processor, including a document containing text and a first table;

means for processing the first table in the memory indicating a boundary between characters when processing the text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character, and wherein, for the first table, the rows indicate a current state, the columns indicate an input character, a non-empty row/column value indicates the a row including the a next state, and an empty row/column value indicates a boundary following the a current state;

means for automatically generating a second table in the memory based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein the means for generating the second table comprises;

means for generating the second table using the columns from the first table as the columns and rows of the second table; and

means for indicating an absence of the a boundary at a column/row value in the second table if the a corresponding column/row value in the first table indicates the next state; and

means for using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

6. A system for generating a table for use in determining a location of a boundary between two characters, comprising:

a processor;

a memory accessible to the processor, including a document containing text and a first table;

means for processing the first table in the memory indicating a boundary between characters when processing the text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character, and wherein a row/cell value in the first table indicates the a row including the a next state based on the a current state indicated in the row and the input character indicated in the column;

means for automatically generating a second table in the memory based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein the means for generating the second table comprises;

means for determining, for each column i and row j pair in the first table, whether a column i, row j cell in the first table is empty;

means for setting a variable k to a value of the column i, row j value cell in the first table if the cell is not empty;

means for determining, for each column 1, whether a row k, column 1 cell in the first table is empty; and

means for setting the a value of a column l, row i value cell in the second table to indicate no boundary between a first character of the a type indicated in column l of the second table and a second character of the a type indicated in row i of the second table; and

means for using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

7. A system for generating a table for use in determining a location of a boundary between two characters, comprising:

a processor;

a memory accessible to the processor, including a document containing text and a first table;

means for processing the first table in the memory indicating a boundary between characters when processing the text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character;

means for automatically generating a second table in the memory based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein the second table is a paired comparison table implemented as a state machine; and

means for using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.

8. A system for generating a table for use in determining a location of a boundary between two characters, comprising:

a processor;

a memory accessible to the processor, including a document containing text and a first table;

means for processing the first table in the memory indicating a boundary between characters when processing the text in a first direction, wherein the first table comprises rows and columns defining a state machine table indicating a next state based on a current state and an input character;

means for automatically generating a second table in the memory based on the a content of the first table, wherein the second table indicates whether one boundary should be placed between any two consecutive characters processed in the a second direction, and wherein means for generating the second table comprises;

means for adding a new first row to the second table;

means for inserting, for each cell at column i in the new first row of the second table, a value of i plus one; and

means for performing, for each row j greater than two and column i in the second table;

(i) determining whether a row j, column i cell in the second table is empty; and

(ii) setting a value of the row j, column i cell in the second table to i plus one if the row j, column i cell in the second table is empty; and

means for using the second table to determine whether one boundary is located between any two consecutive characters processed in a the second direction.