Pattern recognition system having inter-pattern spacing correction

• US 5,161,245 A
• Filed: 05/01/1991
• Issued: 11/03/1992
• Est. Priority Date: 05/01/1991
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Fenwick, David
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/694,527
• Time in Patent Office: 552 Days
• Field of Search: 382/9, 382/40, 382/36, 382/14, 382/15, 364/900, 364/419, 395/63
• US Class Current: 382/231
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A pattern recognition system having inter-pattern spacing correction is disclosed which recognizes words and determines where to place spaces between those words by (a) storing each input character in one or more buffers in memory, (b) comparing the last entry of each buffer against a dictionary of known words, (c) copying last entries which match words to new buffers and placing a space after the last entry in the old buffer, (d) deleting a buffer when a last entry from that buffer does not at least match the beginning of a known word in the dictionary, (e) repeating steps (a) through (d) until all the buffers have been deleted or until an end character, such as a carriage return or period has been stored in each buffer, (f) again comparing the last entries from each buffer to the dictionary and deleting any buffer having a last entry which is not a known word in the dictionary or which does not end with a space followed by an end character, and (g) saving and/or outputting the remaining words. Common words which appear in each buffer, and have therefore been positively identified, can be saved or output to reduce the size of each buffer at any point in the process. Words can either be output in the longest possible combined form or in shorter segmented forms as desired by a user.

Claims

1. A method for recognizing groups of patterns from a string of patterns derived from data input to a processor and placing dividers between the groups of patterns, comprising the steps of:

(a) storing a pattern from said string of patterns in one or more memory positions of a memory in communication with said processor to start or continue formation of one or more series of patterns;

(b) comparing at least a portion of each of said series with a database of defined groups of patterns to locate any matched entries or any unmatchable entries from each of said series, a matched entry including one or more sequential patterns from one of said series which match one of said defined groups of patterns, an unmatchable entry including one or more sequential patterns from one of said series which do not match at least a beginning of one of said defined groups of patterns;

(c) copying each of said series having one of said matched entries from an old memory position to a new memory position in said memory;

(d) placing a divider after said matched entry as stored in said old memory position;

(e) deleting each of said series having one of said unmatchable entries from said memory;

(f) repeating steps (a) through (e) to continue formation of said series until all of said series have been deleted or until an end pattern indicating the end of said string has been stored in one or more of said memory positions;

(g) comparing a last entry from each of said series with said database to locate any final matched series, a final matched series including one or more sequential patterns from one of said series which match one of said defined groups of patterns and which ends with one of said dividers followed by one of said end patterns;

(h) deleting any of said series which is not one of said final matched series; and

(i) saving all of said final matched series in said memory.

2. A method for recognizing groups of patterns, as recited in claim 1, and further comprising the step of

(j) outputting predetermined types of said final matched series to an output device for display.

3. A method for recognizing groups of patterns, as recited in claim 2, wherein said predetermined types are large groups of patterns formed from smaller groups of patterns from a single final matched series.

4. A method for recognizing groups of patterns, as recited in claim 3, wherein said large groups are output as preferred groups of patterns and said smaller groups of patterns are output as optional groups of patterns for selection by a user.

5. A method for recognizing groups of patterns, as recited in claim 1, and further comprising, after step (e) and before step (f), the step of

(k) saving one of said matched entries as one of said final matched series and deleting each of said matched entries from said old memory positions and said new memory positions if said matched series is common to all of said series and if there are at least two of said series in said memory.

6. A method for recognizing groups of patterns, as recited in claim 1, wherein said patterns are characters and symbols from a written language, wherein said defined groups of patterns form words and meaningful symbols in said written language, and wherein said dividers form spaces between said words and meaningful symbols.

7. A method for recognizing groups of patterns, as recited in claim 6, wherein said end patterns include punctuation marks indicating an end to a sentence in said written language.

8. A method for recognizing words from a string of characters derived from data input to a processor and placing spaces between the words, comprising the steps of:

(a) storing a character from said string of characters in one or more memory positions of a memory in communication with said processor to start or continue formation of one or more series of characters;

(b) comparing at least a portion of each of said series with a database of defined words to locate any matched entries or any unmatchable entries from each of said series, a matched entry including one or more sequential characters from one of said series which match one of said defined words, an unmatchable entry including one or more sequential characters from one of said series which do not match at least a beginning of one of said defined words;

(c) copying each of said series having one of said matched entries from an old memory position to a new memory position in said memory;

(d) placing a space after said matched entry as stored in said old memory position;

(e) deleting each of said series having one said unmatchable entries from said memory;

(f) repeating steps (a) through (e) to continue formation of said series until all of said series have been deleted or until an end character indicating the end of said string has been stored in one or more of said memory positions;

(g) comparing a last entry from each of said series with said database to locate any final matched series, a final matched series including one or more sequential characters from one of said series which match one of said defined words and which ends with one of said spaces followed by one of said end characters;

(h) deleting any of said series which is not one of said final matched series; and

(i) saving all of said final matched series in said memory.

9. A method for recognizing words, as recited in claim 8, and further comprising the step of

(j) outputting predetermined types of said final matched series to an output device for display.

10. A method for recognizing words, as recited in claim 9, wherein said predetermined types include one or more large words formed from smaller words from a single final matched series.

11. A method for recognizing words, recited in claim 10, wherein said large words are output as preferred words and said smaller words are output as optional words for selection by a user.

12. A method for recognizing words, as recited in claim 8, and further comprising, after step (e) and before step (f), the step of

(k) saving one of said matched entries as a final matched series and deleting each of said matched entries from said old memory positions and said new memory positions if said matched series is common to all of said series and if there are at least two of said series in said memory.

13. A method for recognizing words, as recited in claim 8, wherein said end character includes punctuation marks indicating an end of a sentence.

14. A method for recognizing words, as recited in claim 8, wherein said end character includes a carriage return symbol.

16. A word recognition system for recognizing words, as recited in claim 13, and further comprising means for saving one of said matched entries as a final matched series and deleting each of said matched entries from said storage means if said matched series is common to all of said series and if there are at least two of said series in said storage means.

15. A word recognition system for recognizing words from a string of characters derived from input data and placing dividers between the words, comprising:

processing means for receiving said input data from an input device, detecting said words, determining whether said words should be combined together to form large words or separated into small words by said dividers, and outputting said large words and said small words in accordance with a user selected predetermined output option; and

storage means for communicating with said processing means and storing said characters and said words at one or more memory positions wherein one or more series of said characters and said dividers are formed or appended at a memory position when said storage means stores a character at said memory position, said series including said characters and said dividers forming said words, and wherein said processing means includes;

means for comparing at least a portion of each of said series with a database of defined words to locate any matched entries or any unmatchable entries from each of said series, a matched entry including one or more sequential patterns of said characters from one of said series which match one of said defined words, an unmatchable entry including one or more sequential patterns of said characters from one of said series which do not match at least a beginning of one of said defined words;

means for copying each of said series having one of said matched entries from an old memory position to a new memory position in said storage means;

means for placing a divider after said matched entry as stored in said old memory position;

means for deleting each of said series having one of said unmatchable entries from said storage means;

means for continuing to form said series from said string of characters until all of said series have been deleted or until an end pattern indicating the end of said string of characters has been stored in one or more of said memory positions;

means for comparing a last entry from each of said series with said database to locate any final matched series, a final matched series including one or more sequential patterns from one of said series which match one of said defined words and which ends with one of said dividers followed by one of said end patterns;

means for deleting any of said series which is not one of said final matched series; and

means for saving all of said final matched series in said storage means.

17. A word recognition system for recognizing words, as recited in claim 15, wherein said end patterns include symbols indicating an end of a sentence and a line of said characters in a written language.