Word segmentation in chinese text

A method in a computer system for identifying individual words occurring in a sentence of text of an unsegmented language, the method comprising the steps of:

• for each of a plurality of textual characters:
• storing a first indication of a set of characters that occur in the second position of words that begin with the character;
• and
• storing a second indication of a set of positions in which the character occurs in words;
• for each of a plurality of contiguous groups of characters occurring in the sentence:
• determining whether the character occurring in the second position of the group is indicated to occur in words that begin with the character occurring in the first position of the group from the first indication;
• if it is determined that the character occurring in the second position of the group is indicated to occur in words that begin with the character occurring in the first position of the group, determining whether every character of the group is indicated to occur in words in the position in which it occurs in the group from the second indication;
• if it is determined that every character of the group is indicated to occur in words in the position in which it occurs in the group, comparing the group of characters to a list of words to determine whether the group of characters is a word;
• submitting the groups of characters determined to be words to a syntactic parser;
• receiving from the syntactic parser a parse structure identifying the syntactic structure of the sentence, the parse structure specifying a subset of the submitted groups of characters as being part of the syntactic structure of the sentence;
• and
• identifying the groups of characters specified by the parse structure as words occurring in the sentence.

A method in a computer system for identifying individual words occurring in a sentence of text, the method comprising the steps of:

• for each of a plurality of textual characters:
• storing a first indication of a set of characters that occur in the second position of words that begin with the character;
• and
• storing a second indication of a set of positions in which the character occurs in words;
• for each of a plurality of contiguous groups of characters occurring in the sentence:
• determining whether the character occurring in the second position of the group is indicated to occur in words that begin with the character occurring in the first position of the group from the first indication;
• if it is determined that the character occurring in the second position of the group is indicated to occur in words that begin with the character occurring in the first position of the group, determining whether every character of the group is indicated to occur in words in the position in which it occurs in the group from the second indication;
• if it is determined that every character of the group is indicated to occur in words in the position in which it occurs in the group, comparing the group of characters to a list of words to determine whether the group of characters is a word;
• submitting the groups of characters determined to be words to a syntactic parser;
• receiving from the syntactic parser a parse structure identifying the syntactic structure of the sentence, the parse structure specifying a subset of the submitted groups of characters as being part of the syntactic structure of the sentence;
• and
• identifying the groups of characters specified by the parse structure as words occurring in the sentence.

A method in a computer system for identifying the words of which a body of natural language text is comprised, the body of natural language text comprising an ordered sequence of characters starting with a first character, ending with a last character, and containing a selected interior character between the first and last characters, the method comprising the steps of:

• identifying within the sequence of characters a first word containing the first character and the selected interior character;
• identifying within the sequence of characters a second word containing the last character but not the selected interior character, such that the first and second words may be concatenated to form the sequence of characters;
• identifying within the sequence of characters a third word containing the first character but not the selected interior character;
• identifying within the sequence of characters a fourth word containing the selected interior character and the last character, such that the third and fourth words may be concatenated to form the sequence of characters;
• submitting the first, second, third, and fourth words to a syntactic parser to generate a parse tree representing the syntactic structure of the sequence of characters, the parse tree containing either the first and second words or the third and fourth words;
• if the parse tree contains the first and second words, indicating that the first and second words comprise the body of natural language text;
• and
• if the parse tree contains the third and fourth words, indicating that the third and fourth words comprise the body of natural language text.

A computer-readable medium whose contents cause a computer system to identify the words of which a body of natural language text is comprised, the body of natural language text comprising an ordered sequence of characters starting with a first character, ending with a last character, and containing a selected interior character between the first and last characters, by performing the steps of:

• identifying within the sequence of characters a first word containing the first character and the selected interior character;
• identifying within the sequence of characters a second word containing the last character but not the selected interior character, such that the first and second words may be concatenated to form the sequence of characters;
• identifying within the sequence of characters a third word containing the first character but not the selected interior character;
• identifying within the sequence of characters a fourth word containing the selected interior character and the last character, such that the third and fourth words may be concatenated to form the sequence of characters;
• submitting the first, second, third, and fourth words to a syntactic parser to generate a parse tree representing the syntactic structure of the sequence of characters, the parse tree containing either the first and second words or the third and fourth words;
• if the parse tree contains the first and second words, indicating that the first and second words comprise the body of natural language text;
• and
• if the parse tree contains the third and fourth words, indicating that the third and fourth words comprise the body of natural language text.

A method in a computer system for selecting from a sequence of natural language characters combinations of characters that may be words using indications for each of a plurality of characters of the characters that occur in the second position of words that begin with the character and of the positions in which the character occurs in words, the method comprising the steps of, for each of a plurality of contiguous combination of characters occurring in the sequence:

• determining whether the character occurring in the second position of the combination is indicated to occur in words that begin with the character occurring in the first position of the combination by accessing a first stored indication indicating a set of characters that occur in the second position of words that begin with the character occurring in the first position of the combination;
• if it is determined that the character occurring in the second position of the combination is indicated to occur in words that begin with the character occurring in the first position of the combination, determining whether every character of the combination is indicated to occur in words in the position in which it occurs in the combination by accessing a second stored indication indicating a set of positions in which the respective character occurs in words;
• and
• if it is determined that every character of the combination is indicated to occur in words in the position in which it occurs in the combination, determining that the combination of characters may be a word.

A computer-readable medium whose contents cause a computer system to select from a sequence of natural language characters combinations of characters that may be words using indications for each of a plurality of characters of the characters that occur in the second position of words that begin with the character and of the positions in which the character occurs in words, by performing the steps of, for each of a plurality of contiguous combinations of characters occurring in the sequence:

• determining whether the character occurring in the second position of the combination is indicated to occur in words that begin with the character occurring in the first position of the combination by accessing a first stored indication indicating a set of characters that occur in the second position of words that begin with the character occurring in the first position of the combination;
• if it is determined that the character occurring in the second position of the combination is indicated to occur in words that begin with the character occurring in the first position of the combination, determining whether every character of the combination is indicated to occur in words in the position in which it occurs in the combination by accessing a second stored indication indicating a set of positions in which the respective character occurs in words;
• and
• if it determined that every character of the combination is indicated to occur in words in the position in which it occurs in the combination, determining that the combination of characters may be a word.

For a selected sequence of characters comprising a single selected Chinese word, a method in a computer system for determining whether the selected sequence of characters may also comprise a series of two or more words, the method comprising the steps of:

• if the selected sequence of characters is at least four characters long, determining that the selected sequence of characters may not also comprise a series of two or more words;
• if all of the characters of the selected sequence do not constitute single-character words, determining that the selected sequence of characters may not also comprise a series of two or more words;
• if the word contains a word commonly used as a derivational affix, determining that the selected sequence of characters may not also comprise a series of two or more words;
• and
• if it not determined that the selected sequence of characters may not also comprise a series of two or more words, determining that the selected sequence of characters may also comprise a series of two or more words.

For a selected sequence of characters comprising a single selected natural language word, a computer-readable medium whose contents cause a computer system to determine whether the selected sequence of characters may also comprise a series of two or more words by performing the steps of:

• if the selected sequence of characters is at least four characters long, determining that the selected sequence of characters may not also comprise a series of two or more words;
• if all of the characters of the selected sequence do not constitute single-character words, determining that the selected sequence of characters may not also comprise a series of two or more words;
• if the word contains a word commonly used as a derivational affix, determining that the selected sequence of characters may not also comprise a series of two or more words;
• and
• if it not determined that the selected sequence of characters may not also comprise a series of two or more words, determining that the selected sequence of characters may also comprise a series of two or more words.

A method of identifying a segmentation for a sequence of characters from a non-segmented language, the method comprising:

• identifying a pair of contiguous words in the sequence of characters;
• identifying an overlapping word comprising at least one character from each word in the pair of contiguous words;
• submitting indications of the contiguous words and the overlapping word to a syntactic parser;
• and
• performing a full syntactic parse to generate a parse tree, the parse tree implicitly segmenting the sequence of characters by including either the pair of contiguous words or the overlapping word but not both.

A method in a computer system for identifying individual words occurring in a sentence of text, the method comprising the steps of:

• for each of a plurality of contiguous groups of characters occurring in the sentence:
• determining overlapping possible words;
• ascertaining probability of each possible word by accessing a stored indication of probability of whether the word occurs in natural language text as a function of adjacent characters;
• and
• submitting the groups of characters determined to be possible words to a parser with an indication of probability.

A computer readable medium storing instructions for a computer system for identifying individual words occurring in a sentence of text, the instructions comprising the steps of:

• for each of a plurality of contiguous groups of characters occurring in the sentence:
• determining overlapping possible words;
• ascertaining probability of each possible word by accessing a stored indication of probability of whether the word occurs in natural language text as a function of adjacent characters;
• and
• submitting the groups of characters determined to be possible words to a parser with an indication of probability.

A computer comprising:

• computer memory comprising:
• instructions to identify individual words occurring in natural language text;
• and
• a word segmentation data structure for use in identifying individual words occurring in natural language text, the data structure having a plurality at records, each record comprising:
• a first field including a word;
• and
• a second field associated with the first field and including an indication of whether the sequence of characters that comprises the word in the first field may also comprise a series of shorter words, such that, when the word is encountered while word segmenting natural language text, it may be determined with reference to the indication for the word whether to investigate whether the word should be segmented into shorter words;
• and
• a processor operable with the computer memory and adapted to process the instructions and the data structure to identify individual words occurring in natural language text.

A computer comprising:

• computer memory comprising:
• instructions to identify individual words occurring in natural language text;
• and
• a word segmentation data structure for use in identifying individual words occurring in natural language text, the data structure having a plurality of records, each record comprising:
• a first field including a word;
• and
• a second field associated with the first field and including an indication of probability of whether the word occurs in natural language text as a function of adjacent characters in the word of the corresponding first field;
• and
• a processor operable with the computer memory and adapted to process the instructions and the data structure to identify individual words occurring in natural language text.