JP2009009583A - Method for segmenting non-segmented text using syntactic parse - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a method for segmenting a text with orthographic variation by using syntactic parse. <P>SOLUTION: The method segments the text by providing orthographic and inflectional variations 308 to a syntactic parser 316. Possible segments are first identified in the sequence of characters. At least two of the identified segments overlap each other. For at least one of the segments, an alternative sequence of characters is identified. In some cases, this alternative sequence is formed through inflectional morphology 306, which identifies a different lexical form for a word identified by the segment. In some cases, the alternative sequence represents an orthographic variant 308 of a word identified by the segment. The identified segments and the alternative segments are then passed to a syntactic analyzer 316, which produces one or more syntactic parses. The segments found in the resulting parses represent the segmentation of the input sequence of characters. <P>COPYRIGHT: (C)2009,JPO&INPIT

Description

  The present invention relates generally to computer-based methods for identifying text. More particularly, the present invention relates to a method for segmenting text having orthographic variations using syntactic parsing.

(Background of the Invention)
Word segmentation is the process of identifying individual words that make up a linguistic expression, such as text. Word segmentation is useful for spelling and grammar checking, text-to-speech synthesis, performing natural language understanding, and searching for specific words or phrases in a set of documents.

  In English text, word segmentation is fairly straightforward because spaces and punctuation marks generally separate individual words in the text. However, in unsegmented text such as Japanese and Chinese, word boundaries are implicit and not explicit. That is, unsegmented text usually does not include spaces or punctuation between words. Therefore, segmentation cannot be performed in these languages in the same way as English segmentation.

  Most prior art systems use simple word breaks to segment text. In these word breaks, a plurality of characters are grouped into possible segment groups, and segments are searched for in the glossary. If a segment is found in the glossary, it is retained as part of the possible segmentation of the text.

  A glossary approach can be used to identify many segments that overlap each other, and therefore these segments cannot exist within the same segmentation result. In order to identify which of these competing segments are the actual segments of text, some prior art systems use simple syntax rules. However, these simple rules apply only to characters that appear in the original text string. These do not correspond to orthographic variations in the original text that would have a different syntax if not properly identified. Japanese has many orthographic variations, especially for the same word, and it is difficult to segment Japanese text using a syntactic parser. Many of these variations are caused by the fact that Japanese uses four types of scripts: Kanji, Hiragana, Katakana, and English, and the same word can be spelled using different scripts or combinations of scripts. .

  Therefore, the segmentation system requires a segmentation system that properly explains orthographic variations while taking advantage of segmentation in parsing. In addition to solving this and other problems, the present invention has advantages over the prior art.

(Summary of Invention)
Embodiments of the present invention provide a method and apparatus for segmenting text by sending orthographic and refraction language variations to a syntax parser. In the present invention, possible segments are first identified in the string. At least two of the identified segments overlap each other. Other character strings are identified for at least one of the segments. In some cases, this other string is formed by a refraction morphology that identifies different lexical forms of the words identified by the segment. Other character strings may represent orthographic variations of words identified in the segment.

  The identified segment and other segments are then passed to the syntax parser to output a complete syntax parse. The resulting segment in the parse represents the segmentation of the input string.

Detailed Description of Exemplary Embodiments
FIG. 1 illustrates an example of a suitable computer system environment 100 on which the invention may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. This computing environment 100 should not be construed as dependent on or necessary for any one or combination of components illustrated in the exemplary operating environment 100.

  The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and / or configurations that may be suitable for use with the present invention include personal computers, server computers, portable or laptop devices, multiprocessor systems, microprocessors Base systems, set-top boxes, programmable home appliances, network PCs, minicomputers, mainframe computers, distributed computing environments including, but not limited to, the systems or devices described above.

The invention can be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules can be located in both local and remote computer storage media including memory storage devices.

  With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer 110. The components of the computer 110 include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 has several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus that use various bus architectures. Examples include, but are not limited to, the Industry Standard Architecture (ISA) bus, the Micro Channel Architecture (MCA) bus, the Enhanced ISA (EISA) bus, and the Video Electronics Standard Acades Standard Acades Standard Acades Standard A bus). And the Peripheral Component Interconnect (PCI) bus, also referred to as the Mezzanine bus.

  Computer 110 typically includes a number of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. For example, computer readable media include, but are not limited to, computer storage media and communication media. Computer storage media includes both volatile and non-volatile removable and non-removable media, and is a method or technique for storing information such as computer-readable instructions, data structures, program modules, or other data. Has been implemented. Computer storage media includes RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disc (DVD), or other optical disk storage, magnetic cassette, magnetic tape, magnetic disk storage or There are other magnetic storage devices or other media that can be used to store information of interest and that can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modular data signal such as a carrier wave or other transport mechanism and includes information delivery media. A “modulated data signal” is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. For example, without limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media. Combinations of the above will also be included within the scope of computer-readable media.

  The system memory 130 includes computer storage media in the form of volatile or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input / output system 133 (BIOS) that includes basic routines that help to transfer information between elements within the computer 110, such as during startup, is typically stored in the ROM 131. RAM 132 typically includes data and / or program modules that are immediately accessible to and / or presently being operated on to processing unit 120. In the example, although not limited thereto, FIG. 1 shows an operating system 134, an application program 135, other program modules 136, and program data 137.

  Computer 110 may also include other removable / non-removable, volatile / nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads and writes to a non-removable non-volatile magnetic medium, a magnetic disk drive 151 that reads and writes to a removable non-volatile magnetic disk 152, and a CD-ROM or other 1 shows an optical disk drive 155 that reads from and writes to a removable non-volatile optical disk 156, such as an optical medium. Other removable / non-removable volatile / nonvolatile computer storage media that can be used in the example operating environment include magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, semiconductor RAM, semiconductor ROM, etc. is there. The hard disk drive 141 is normally connected to the system bus 121 through a non-removable memory interface such as the interface 140, and the magnetic disk drive 151 and the optical disk drive 155 are usually connected to the system bus 121 through a removable memory interface such as the interface 150. The

  The drives and associated computer storage media shown in FIG. 1 described above store computer readable instructions, data structures, program modules, and other data for computer 110. In FIG. 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. These components may be the same as or different from operating system 134, application program 135, other program modules 136, and program data 137. The operating system 144, the application program 145, the other program modules 146, and the program data 147 are given different numbers here to indicate that they are at least different copies.

  A user may enter commands and information into the computer 110 through input devices such as a keyboard 162, a microphone 163, and a pointing device 161, such as a mouse, trackball or touch pad. Other input devices (not shown) include a joystick, a game pad, a satellite dish, a scanner, and the like. These and other input devices are often connected to the processing unit 120 via a user input interface 160 coupled to the system bus, but may be a parallel port, game port, or universal serial bus (USB). Other interface and bus structures can also be used. A monitor 191 and other types of display devices are also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, the computer also has other peripheral output devices such as speakers 197 and printer 196 that can be connected via the output peripheral interface 190.

  Computer 110 may also operate in a network environment using logical connections to one or more computers, such as remote computer 180. Remote computer 180 may be a personal computer, handheld device, server, router, network PC, peer device, or other common network node and typically includes many or all of the elements described above associated with computer 110. The logical connections shown in FIG. 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may include other networks. Such networking environments are common in offices, enterprise-wide computer networks, intranets and the Internet.

  When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or network adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172 may be internal or external, but can be connected to the system bus 121 via the user input interface 160 or other suitable mechanism. In a network environment, program modules described with respect to computer 110 or portions thereof may be stored on a remote memory storage medium. By way of example, but not limited to, FIG. 1 shows a remote application program 185 that resides on a remote computer 180. It will be appreciated that the network connections shown in the figures are examples and other means can be used to establish a communications link between the computers.

  FIG. 2 is a block diagram of a mobile device 200, which is an example of a computing environment. The mobile device 200 includes a microprocessor 202, a memory 204, an input / output (I / O) component 206, and a communication interface 208 for communicating with a remote computer or other mobile device. In one embodiment, the aforementioned components are coupled so that they can communicate with each other over a suitable bus 210.

  The memory 204 is implemented as a non-volatile electronic memory such as a random access memory (RAM) with a battery backup module (not shown in the figure), and information stored in the memory 204 is stored by the general power supply of the mobile device 200. It is not lost even if it is shut down. Some of the memory 204 is preferably allocated as addressable memory for program execution, while other parts of the memory 204 are preferably used for storage, such as simulating storage on a disk drive.

  The memory 204 stores an operating system 212, application programs 214, and an object store 216. In operation, operating system 212 is preferably executed by processor 202 from memory 204. In one preferred embodiment, operating system 212 is a Windows® CE brand operating system commercially available from Microsoft Corporation. The operating system 212 is preferably designed for mobile devices and implements database functionality available to the application 214 through a set of public application programming interfaces and methods. Objects in object store 216 are maintained by application 214 and operating system 212, and at least in part respond to calls to published application programming interfaces and methods.

  Communication interface 208 represents a number of devices and technologies for transmitting and receiving information with mobile device 200. Examples of these devices include wired and wireless modems, satellite broadcast receivers, and broadcast tuners. Mobile device 200 can also be connected directly to a computer to exchange data. In such a case, the communication interface 208 can be an infrared transceiver or a serial or parallel communication connection, but all can transmit streaming information.

  Input / output components 206 include various output devices such as touch-sensitive screens, buttons, rollers, and microphones, as well as audio generators, vibration devices, and displays. The above devices are examples and need not all exist in the mobile device 200. Furthermore, other input / output devices may be connected to or present with the mobile device 200 within the scope of the present invention.

  Embodiments of the present invention provide a method and apparatus for segmenting text by sending orthographic and refraction language variations to a syntax parser. FIG. 3 is a block diagram of various components of one embodiment of the present invention. FIG. 4 is a flow diagram of a method according to an embodiment of the invention that uses the components of FIG.

  In step 400 of FIG. 4, the word breaker of FIG. 3 identifies consecutive character combinations in the input text 300 that appear in a small lexical record set 304. The vocabulary record set 304 is small in the sense that the amount of grammatical information for each word is limited. The vocabulary record set 304 does not necessarily contain a small number of words, and indeed, in some embodiments, the small vocabulary record set 304 includes a large number of words.

  In one embodiment of the present invention, the word breaker 302 searches for words in a small vocabulary record set 304 using a data structure called trie. In a trie, words are not displayed in order, but instead are represented by a chain of states. Each state represents an individual character and includes one or more child states, each child state including a character that appears after the current state character of at least one word in the small vocabulary record set 304. Each state also indicates whether the current character appears as the last character in the word formed by the chain of states preceding the current character.

  Using the trie data structure, possible words in a string such as ABCD can be determined in parallel. For example, the system starts with the state associated with the letter A. If the condition indicates that the letter A appears alone as a word in the small vocabulary record set 304, “A” is identified as a possible segment of the string. The system then checks to see if there is a child state for character B extending from the state for character A. If there is a B child state, the B state is checked to see if the character B is the last character of the word. If it is the last character, the character string AB is identified as a possible segment. The system then checks to see if there is a child state for character C that extends from the state for character B. If there is no child state of the letter C extending from the current state, the system stops tracking the current chain and starts tracking a new chain starting with the letter B. Repeat the process of starting a new chain for each character in the input string, testing each character as a possible beginning of the chain.

  Once the words stored in the small vocabulary record set 304 are identified at step 400, the method of FIG. 4 continues at step 402, where the word breaker 302 uses the inflectional morphology rule 306 to reduce the Although it cannot be stored in the vocabulary record set 304, its lemma identifies a word that can be stored in the small vocabulary record set 304. This headword is a standard form of a word used when stored in a dictionary or vocabulary database. For example, the substring ABC is found in the text string, the substring BC indicates the past tense of some verbs, takes the previous string of the substring BC and combines it with the new letter Q If the refraction morphological rule stipulates that the headword of the verb can be formed, the refraction morphology can identify the headword AQ from the partial character string ABC. In some embodiments of the present invention, the derivative morphology analysis rules described below in connection with step 408 are also applied at step 402.

  Before adding an entry word to the word lattice, the system searches a small vocabulary record set 304 to verify that the entry word is a single word in the language. If the headword is a word in the language, the headword is added to the word lattice, the vocabulary information of the headword is stored in the record set 304, and information about the word is given by the refraction morphology. For example, a record placed in the word lattice may indicate the tense of the headword found in the input text string. The records placed in the word lattice for the headword further indicate the start and end positions of the character string in the input string used to find the headword. For example, if 4 characters are used to represent the past tense of an entry word containing only 2 characters, the entry word record will be occupied by 4 characters instead of the entry word being occupied by only 2 characters of the entry word. Indicates that the area to be filled is filled. This allows the headword to be combined with other segments in the character sequence even though the headword is a different number of character strings than the character string used to find the headword.

  While performing refraction morphology, the method of FIG. 4 further performs orthographic normalization to normalize different spellings of words. By performing this normalization, it is not necessary to store all the spellings in the small vocabulary record set 304. Instead, only one preferred spell is stored in a small vocabulary record set.

  To normalize the orthography of the string, the word breaker 302 accesses the data structure 308 and links the selected word in each preferred orthographic form to the orthographic variation of that word. Using data structure 308, word breaker 302 searches for strings that are found within possible segments of the input text. Upon finding the string in the data structure 308, the word breaker 302 uses the data structure 308 to identify the preferred form of the word. This preferred form is then inserted into the word lattice along with the associated lexical information of the word and the start and end positions of the normalized segment.

  Note that the normalized form of the word may have more or less characters than the original segment on which it is based, and the characters may be different from the original segment. In the present invention, by storing the start position and end position of the original segment in a record in a normalized format, the normalized format can be combined with other segments in the input string to complete the input string. Segmentation can be identified.

  In the Japanese embodiment, part of orthographic normalization requires the selection of a preferred combination of the four types of scripts commonly used in Japanese: Kanji, Hiragana, Katakana, and English. Kanji is a collection of Japanese characters that are borrowed from Chinese and look quite complicated. There are thousands of these characters in Japanese, and each character may have multiple “readings” (ie pronunciations). Hiragana is a Japanese syllable character used to write words based on pronunciation. Katakana is another syllable character that is mainly used for the representation of foreign words and the emphasis of words in sentences. Hiragana and katakana are sometimes collectively referred to as kana.

  In one embodiment of the present invention, orthographic structure 308 takes the form of a set of orthographic lattices, each lattice representing a word. For each word, the lattice indicates all of the orthographic forms of the word and the preferred orthographic form of the word.

  An example of such a lattice 500 is shown in FIG. Lattice 500 is divided into three word element fields 502, 504, and 506, shown in parentheses, to hold data representing a single element of the word. A single element within each parenthesis can be represented by a single character or multiple characters. Although a three word element is shown in FIG. 5, one skilled in the art will recognize that there can be any number of word elements in the lattice. Note also that if there is no substitution for a word element, it will appear as itself in the lattice without parentheses.

  Each word element data field includes two subfields, a preferred field 508 and an alternative field 510. The preferred field 508 contains the main or preferred form of the corresponding word element. In most Japanese embodiments, the preferred field 508 includes Chinese characters. The substitution field 510 includes data representing an alternative form of the corresponding word element. In most Japanese embodiments, the alternate field 510 includes one or more kana characters. Any number of characters can be placed in either the preferred field 508 or the alternate field 510.

  For example, the orthographic lattice [W: ab] [X: cd] specifies a word that can be written as “WX”, “Wcd”, “abX”, or “abcd”, with uppercase letters being the preferred representation of each element Lowercase letters indicate alternative representations of each element.

  In the embodiment of Japanese in which kanji is preferred over ordinary kana, a “feed” variation is also provided in the lattice of the present invention. A advance is one or more kana characters that can optionally be added to a kanji in some spelling variations, but must be added to the kanji substitution. Therefore, when “X” is a Chinese character, “a” is a substitute kana character for X, and “b” is an optional character, variations “Xb” and “ab” are valid, but “a” without “b” is Not valid. The advance is represented by a comma in the lattice. Thus, in the lattice [W: a, b] [X: c], the orthographic forms “WX”, “WbX”, “Wc”, “Wbc”, “abX”, and “abc” are allowed, but “aX "Or" ac "is not allowed. Multiple feeds of a single word element are represented by separating each of the feeds with a comma. For example, in the lattice [W: a] [X: b, c, d], allowable variations “WX”, “WXd”, “WXc”, “Wbcd”, “aX”, “aXd”, “aXc” , And “abcd” can be used.

  In one embodiment, the compiled lattice structure is used directly to convert possible word segments into the preferred orthographic form. In this embodiment, the received character input is compared to the first word element of each orthographic lattice. If the received character input matches the preferred or alternative form of the first word element of a particular lattice, then the subsequent characters in the input string are further compared with the word elements in the particular lattice to correspond to the particular lattice Check whether the orthographic form of the vocabulary input to be present exists in the input string. If the input string matches a combination of word elements in the lattice, a normalized representation of the input string is generated that includes the preferred form of each word element in the orthographic lattice. The normalized form is then inserted into the word lattice being generated by the word breaker 302.

  In some Japanese embodiments, additional structures are used in conjunction with the above lattice to reduce the computation time associated with accessing the lattice. This data structure contains one entry for each word, each entry having a kana field and a preferred format field. In the all kana field, words represented only by kana characters are stored. The preferred format field stores the preferred orthographic form of the word to be included in the word lattice. With this additional structure, an input character string including only kana characters can be looked up at high speed. Instead of accessing a relatively complex orthographic lattice structure, the word breaker 302 instead performs a simple lookup within the kana structure to find all preferred forms of the kana string. In some embodiments, the kana structure is organized as a trie structure similar to the trie structure described above.

  In some embodiments, the lattice and all kana data structures are augmented with a look-back data structure to further reduce the computation time associated with operations that access the lattice. Because the lookback data structure allows the lattice to be indexed based only on preferred characters, the initial search for matching lattices compares only the preferred characters and not the substitute characters. In this embodiment, if the input string begins with a preferred character, words that begin with the preferred character are searched directly in the orthographic lattice using the preferred character of the word. However, if the input string begins with a non-preferred (alternative) character, the lookback data structure is searched using the first preferred character appearing in the input string. For example, when the input character string is “abXc”, if “a”, “b”, “c” are alternative characters and “X” is a preferred character, an entry whose lookback data structure corresponds to “X” Searched for.

  Each lookback entry corresponds to a particular orthographic form of the word. This is indexed based on the first preferred character in orthographic form. Each entry also indicates the number of alternative characters before this first preferred character in orthographic format and the ID of the first alternative character in this format. For example, for the orthographic form “abcYdef”, the entry indicates that three alternative characters precede the preferred character and the first alternative character is “a”. This entry also indicates which preferred character is first in the preferred orthographic form of the word. For example, if “VXYZ” was the preferred orthographic form of the word “abcYdef”, the entry indicates that “V” is the first preferred letter of the preferred form of the word.

  As mentioned above, the lookback data structure is accessed when the input string does not start with a preferred character but contains a preferred character. The first preferred character in the input string is used to search the lookback structure to find an entry for that character. Evaluate the characters in the input string that precede the search character by the difference indicated by the lookback indicator. If the evaluated character matches an alternative character stored in the lookback entry, the preferred form of the first word element in the lookback entry is used to search the orthographic lattice. For each entry in the orthographic lattice starting with this preferred format, the word breaker 302 compares the original input string with the lattice entry to see if the orthographic format in the entry matches the input string. If there is a match, the preferred orthographic form of the word is inserted into the word lattice.

  In some embodiments, some first preferred characters of the lookback entry are part of a word element that includes a sequence of preferred characters. In such an embodiment, each character in the input string after the input character that is used to search the lookback structure is compared with the preferred characters that make up the elements in the entry. If these values do not match, the lattice search is not performed.

  After word breaker 302 performs refraction morphology and orthographic normalization in step 402, the word lattice is composed of words that can be formed directly by segmenting characters in the input text and variations of words in the input text. Is done. As described above, the number of characters of these variations may be greater or less than the word from which the variation is based, and may include characters that are not present in the input text. Accordingly, the word lattice generated by the word breaker 302 can include characters that are different from those present in the input text.

  The word lattice generated by the word breaker 302 is sent to a vocabulary lookup unit 310 that has access to a large vocabulary record set 312. The large vocabulary record set 312 includes more vocabulary information than the small vocabulary record set 304. In fact, in many embodiments, a small vocabulary record set 304 is constructed with reference to the large vocabulary record set 312 and updated regularly.

  The vocabulary lookup unit 310 uses the large vocabulary record set 312 to increase the amount of vocabulary information stored in the word lattice for each word in the lattice at step 406 of FIG. Such additional information includes items such as the origin of the word, whether the word can be used in an appropriate noun, and the word and other vocabulary and grammatical details.

  The word lattice is passed from the vocabulary lookup 310 to the derived morphology 314 along with the expanded vocabulary information. In step 408 of FIG. 4, the derived morphology 314 combines consecutive segments of characters in the word lattice to form a larger multi-segment word. For example, the derived morphological component 314 may add, insert, or prepend suffix strings, infix strings, and prefix strings to other segments. Can do. In some embodiments, some or all of these derived morphological rules are applied at step 402 by the word breaker 302 rather than at step 408 by the morphological component 314. However, the application of the morphological component 314 has the advantage that a wealth of information can be used in the large vocabulary record set that is entered into the derived morphological rules. In addition, the derived morphological component 314 provides segments to identify and extract named entities such as names of people, facilities, and geographical locations and other proper nouns, and other units such as dates and times. Can be combined.

  The large word constructed by the derived morphology 314 is added to the word lattice along with the lexical information of the large word. In most embodiments, large words composed of derived morphologies 314 do not replace small segments, but instead are placed in the lattice in addition to small segments.

  The expanded word lattice generated by the derived morphology 314 typically includes one or more overlapping segments. Such overlapping segments include segments that are derived directly from an input string having one or more characters in common. Overlapping segments further include variations formed through refraction morphology or orthographic normalization generated from segments in the input string that overlap with one or more other segments.

  The expanded word lattice generated by the derived morphology 314 is sent to the syntax parser 316, where parsing is performed using the word lattice expanded in step 410 of FIG. In one embodiment, parsing is performed using a bottom-up chart parse that outputs a syntactic parse by incrementally building large phrases from small words and phrases. To construct a large phrase, the syntax parser 316 applies grammar rules that examine the vocabulary specification of the word or phrase and determine how to combine to form a large word or phrase. In one embodiment, a binary grammar that examines two adjacent words or phrases is used to determine how to combine them.

  The parsing performed by the syntax parser 316 considers all segments in the expanded word lattice. The syntax parser is constrained to combine only segments representing adjacent characters in the original input text and target the entire input text in the final analysis. Thus, the syntax parser cannot generate a valid parse with two overlapping segments or a valid parse result for a group of segments that does not represent the entire input string.

  In one embodiment, the syntax parser 316 generates a single parse at its output. This single parse identifies relationships between groups of words that are in the word lattice. Because refraction morphology and orthographic normalization are performed to build the word lattice, this valid parse can include words that were not originally in the input text. The resulting valid parse includes a valid segmentation of the input text selected from a plurality of possible segmentations found in the word lattice. Since the syntax parser essentially selects one segmentation from a group of overlapping segments, the present invention does not require another segmentation unit to identify the appropriate segmentation before the syntax parser. Instead, the syntax parser itself selects the most likely segmentation of the input text.

  The segmentation generated by the present invention is more sophisticated than the prior art segmentation because the syntax parser operates on characters that were not necessarily present in the input text itself. Thus, the segmentation results obtained from the syntax parser are based on word formats that were not considered in prior art segmentation systems that were not present in the input text.

  In other embodiments, the syntax parser 316 generates a plurality of valid syntax parses, each representing a separate valid segmentation of the input text. In one embodiment, each of these valid parses is passed to a logical form generator 318 that identifies the semantic relationships within each parse. Semantic relationships can then be used to select which valid syntactic parses are the correct parses of the input string. This semantic identification is shown as step 412 in FIG.

  Although the invention has been described with reference to particular embodiments, it will be apparent to those skilled in the art that changes can be made in form and detail without departing from the spirit and scope of the invention.

1 is a block diagram of a general purpose computer system embodiment suitable for implementing the present invention. 1 is a block diagram of a handheld device in which the present invention can be implemented. FIG. 3 is a detailed block diagram of elements of an embodiment of the present invention. 4 is a flow diagram of a method for segmenting using parsing according to an exemplary embodiment of the present invention. FIG. 3 is an orthographic lattice used in an embodiment of the present invention.

Claims (2)

A method of segmenting an input string in an unsegmented language,
Identifying possible segments in the string, wherein at least two of the possible segments overlap each other;
Identifying an alternative string for at least one of the possible segments, wherein the alternative string forms an alternative segment;
Performing a plurality of parsings using the possible segment and the alternative segment, the parsing helping to segment the input string;
Providing a complete parsing that results in a segmentation of the input string. A system for identifying syntax in strings in non-segmented languages,
A word breaker for a processor that generates a set of words from the input string, wherein the set of words includes at least two words that are partially derived from the same character in the string, the word breaker But,
A vocabulary record set stored in system memory that is used to obtain words for the set of words that are taken directly from the string;
A variation constructor stored in system memory used by the processor to obtain word variations of words found in the string, each word variation being added to the set of words, each word variation being its A word using a variation constructor having a character string different from the character string related to the word in the character string that is the source of variation, and each word variation having a different orthographic form or refraction form from the word of the character string With a breaker,
And a syntax parser of the processor that performs a syntax analysis using a set of words generated by the word breaker and generates a syntax parse indicating the syntax of the character string.

Images