Patent Publication Number: US-10762293-B2

Title: Using parts-of-speech tagging and named entity recognition for spelling correction

Description:
BACKGROUND OF THE INVENTION 
     Part of speech tagging is the process of tagging a word as corresponding to a particular part of speech based on its definition and/or context, e.g., adjacent and related words in a phrase, sentence, or paragraph. Techniques are known to process a corpus (body) of annotated text to generate a model that can be used to determine a statistical likelihood that a word in a given context in a non-annotated text corresponds to a particular part of speech. Similar techniques have been used to identify a word or words as corresponding to a named entity (e.g., “Apple” the company as opposed to “apple” the fruit) and/or to distinguish between one sense of a word and another (e.g., “play” as used to refer to a dramatic work as opposed to children&#39;s “play”). 
     Techniques to correct or complete automatically text that is not recognized as a complete and correctly spelled word are known. Reference dictionaries, statistical information, commonly encountered misspellings and/or mistyping, and keyboard geometry-based techniques have been used to identify and/or select candidates to replace a misspelled word or complete a partially typed word. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings. 
         FIG. 1  is a flow diagram illustrating an embodiment of a process for auto-correction or completion of entered text. 
         FIG. 2  is a block diagram illustrating an embodiment of a system configured to perform auto-correction and/or completion. 
         FIG. 3  is a flow diagram illustrating an embodiment of a process to configure a system to perform part of speech tagging. 
         FIG. 4  is a flow diagram illustrating an embodiment of a process of performing part of speech tagging. 
         FIG. 5  is a flow diagram illustrating an embodiment of a process of auto-correction and/or completion of entered text. 
         FIG. 6  is a block diagram illustrating an embodiment of a network environment comprising systems configured to perform auto-correction and/or completion. 
     
    
    
     DETAILED DESCRIPTION 
     The invention can be implemented in numerous ways, including as a process; an apparatus; a system; a composition of matter; a computer program product embodied on a computer readable storage medium; and/or a processor, such as a processor configured to execute instructions stored on and/or provided by a memory coupled to the processor. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention. Unless stated otherwise, a component such as a processor or a memory described as being configured to perform a task may be implemented as a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. As used herein, the term ‘processor’ refers to one or more devices, circuits, and/or processing cores configured to process data, such as computer program instructions. 
     A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured. 
     Auto-correction or completion of text based on how a word or phrase is used in context is disclosed. In various embodiments, part of speech tagging and/or other techniques are used to determine one or more features of a word or phrase as used in context, for example in the context of a sentence. The contextually determined feature(s) is/are used, in addition to the word or phrase itself, to determine and/or evaluate the suitability of an auto-correction or completion candidate. For example, in some embodiments if a string, word, and/or phrase is typed that is not recognized as a valid and complete word or phrase, and one or more candidates for replacement are identified, a candidate that matches a statistically expected part of speech for the word or phrase as used in context is more likely to be selected than a candidate that does not match the expected part of speech. For example, if the word or phrase appears from the structure of a sentence in which it occurs to be the subject of the sentence, a replacement candidate that is a noun is more likely to be selected than one that is a verb. In various embodiments, a weighted set of one or more features of a word or phrase, included one or more of the word or phrase itself, the statistically expected part of speech, whether the word or phrase is capitalized, whether the word or phrase appears to be a named entity, prefixes and suffixes, such as an -ing ending, etc. are considered to evaluate replacement candidates. 
       FIG. 1  is a flow diagram illustrating an embodiment of a process for auto-correction or completion of entered text. In the example shown, key press events are received ( 102 ) and analyzed in real time to detect spelling or other errors and/or to make auto-completion suggestions ( 104 ). If an error or partially entered word or phrase is detected ( 106 ), a replacement candidate is selected and suggested to the user ( 108 ). In some embodiments, contextual information, such as the statistically expected part of speech of the text to be replaced or completed, whether the text is a named entity, etc., is considered in determining whether an error or partially typed word or phrase has been entered and/or to determine and/or selected a replacement text to replace (or suggest as a replacement for) the entered text. The process continues until done ( 110 ), for example text is no longer being entered. 
       FIG. 2  is a block diagram illustrating an embodiment of a system configured to perform auto-correction and/or completion. In the example shown, the system  202  includes one or more applications running in an application framework  206  running on an operating system  208 . In various embodiments, one or more of applications  204 , application framework  206 , and operating system  208  comprise computer instructions stored in a memory or other storage comprising system  202  and executed by a processor comprising system  202 . An input device  210 , such as a keyboard, is connected to and/or an integral part of the system  202 . Keystrokes or other character selection inputs received at the input device  210  are provided to the operating system  208  via an input device driver  212 . The operating system  208  provides keystroke (or other character input) event data to the application framework  206 , which uses a statistical language model  214  to evaluate entered text. Entered text is parsed, for examples, to identify word, phrase, and sentence boundaries. Strings (e.g., partial words), words, and phrases are evaluated in light of contextual information, for example where they occur in a sentence, whether they are capitalized, suffixes and/or prefixes, and other contextual “features” of the string, word, or phrase, to determine an expected part of speech and/or other expected attribute(s) of the string, work, or phrase. The part of speech or other attribute(s) of the string, word, or phrase are used to determine and/or evaluate replacement candidates for the entered string, word, or phrase. In various embodiments, part of speech and/or other contextually determined attributes are used to assign respective scores to and/or otherwise evaluate replacement candidates determined using one or more conventional techniques, such as dictionaries or other stores of commonly mistyped and/or misspelled words, keyboard geometry based techniques (e.g., to detect extra, missed, or transposed characters), etc. All else being equal, a candidate that matches an expected part of speech, for example, is more likely to be selected than one that does not. 
       FIG. 3  is a flow diagram illustrating an embodiment of a process to configure a system to perform part of speech tagging. In the example shown, an annotated corpus (or multiple corpora) of text is ingested and analyzed ( 302 ). The annotation identifies, for example, part of speech and/or other features of words and phrases as used in text comprising the corpus. In some embodiments, a commercially available corpus is used. In some embodiments, the commercially available corpus is supplemented by additional content annotated manually. For example, content from less traditional sources such as blog entries, online comments, and stauts updates or other text posted via online social networks are ingested and annotated, and then included in an augmented corpus of annotated (for example, part of speech tagged) text. The corpus is analyzed to build a statistical language model ( 304 ). The model is used in various embodiments, for example, to determine for a word or phrase as used in an arbitrary sentence, given knowledge of where the word or phrase occurs in a sentence, for example, and/or other features of the word or phrase, a statistical likelihood that the word or phrase corresponds to a particular part of speech, or comprises a named entity, etc. A system, such as a computer, is configured to store the statistical model and to use the model to analyze and tag text as entered ( 306 ). 
       FIG. 4  is a flow diagram illustrating an embodiment of a process of performing part of speech tagging. In the example shown, as arbitrary text is entered it is parsed to identify word, phrase, and sentence boundaries ( 402 ). As word and phrase boundaries are recognized ( 404 ), words and phrases are evaluated in context (e.g., of the sentence in which they occur) to determine a corresponding part of speech (and/or other attribute) and to tag the associated word or phrase as having that attribute ( 406 ). The process continues until done ( 408 ), e.g., text is no longer being entered. 
       FIG. 5  is a flow diagram illustrating an embodiment of a process of auto-correction and/or completion of entered text. In the example shown, one or more replacement candidates for an entered text, such as an entered string, word, and/or phrase, are determined and/or received ( 502 ). In some embodiments, conventional techniques such as dictionaries of commonly mistyped and/or misspelled words or phrases, keyboard geometry based techniques, etc. are used to determine replacement candidates. In some embodiments, replacement candidates may be received from an external service, such as a spell check or other service. The service in some embodiments may be remotely located, e.g., across a network. Expected part of speech and/or other contextually determined attribute information is evaluated to determine a degree of confidence that a particular replacement candidate should be selected ( 504 ). For example, in some embodiments a replacement candidate that matches a statistically expected part of speech or other attribute (e.g., gerund, named entity, particular word sense, etc.) is assigned a higher confidence score than if the candidate did not match the expected attribute. In some embodiments, the confidence score is increased by an amount that is proportional to a statistically determined likelihood that the entered text is expected to have the attribute. If a threshold to suggest a replacement candidate is satisfied ( 506 ), for example a confidence score reaches or exceeds a prescribed threshold, the associated replacement candidate is suggested to replace the entered text ( 508 ). 
       FIG. 6  is a block diagram illustrating an embodiment of a network environment comprising systems configured to perform auto-correction and/or completion. In the example shown, a mobile device  602  and a wired client system  604  are connected via a network  606 , such as the Internet and/or a mobile or other telecommunications network, to a server  608 . If configured, text entered on mobile device  602  and/or client  604  is analyzed as described herein to determine based at least in part on context one or more expected attributes of the entered text, such as an entered partial word, word, and/or phrase. Replacement candidates are retrieved from server  608 , for example by sending a word or phrase selected by a user or identified by the system at which it was entered as potentially requiring replacement, and evaluated at the mobile system  602  or client  604 , as applicable, in light of the contextually determined expected attribute, to determine whether the replacement candidate(s) should be suggested to replace the entered text. In some alternative embodiments, replacement candidates are determined locally at the system at which text (potentially) to be replaced is entered. 
     Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.