Method and apparatus for efficient segmentation of compound words using probabilistic breakpoint traversal

1. An apparatus for segmenting compound words in a natural-language input, the apparatus comprising:

a startpoint probability matrix;

a endpoint probability matrix;

a probabilistic breakpoint analyzer having access to the startpoint probability matrix, the endpoint probability matrix and the natural-language input, the probabilistic breakpoint analyzer being operative to generate a breakpoint-annotated input from the natural-language input; and

a probabilistic breakpoint processor coupled to the probabilistic breakpoint analyzer, the probabilistic breakpoint processor being operative to generate a segmented string for the compound words in the natural-language input in response to the breakpoint-annotated input.

2. The apparatus of claim 1 , further comprising a word-boundary analyzer having access to a lexicon and a memory unit, the word-boundary analyzer being operative to generate the startpoint probability matrix and the endpoint probability matrix.

3. The apparatus of claim 1 , wherein the probabilistic breakpoint processor comprises:

a lexicon;

a chart; and

a breakpoint-delimited substring tester having access to the lexicon and the chart, the substring tester being operative to receive the breakpoint-annotated input and generate a segmented string in response thereto.

4. The apparatus of claim 1 , wherein the probabilistic breakpoint processor is an augmented probabilistic breakpoint processor comprising:

a lexicon;

a chart;

an augmented breakpoint-delimited substring tester having access to the chart and the lexicon, the substring tester being operative to identify a plurality of linkable components; and

a chart analyzer coupled to the substring tester and having access to the chaff, the chart analyzer being operative to generate the segmented string.

5. The apparatus of claim 4 , wherein the augmented breakpoint-delimited substring tester generates one of:

the segmented string; and

a failure signal.

6. The apparatus of claim 5 , wherein the chart analyzer is coupled to receive the failure signal from the augmented breakpoint-delimited substring tester.

7. The apparatus of claim 1 , wherein the apparatus is configured as a computer readable program code run on a computer usable medium.

8. A method for segmenting compound words in an unrestricted natural-language input, the method comprising:

receiving a natural-language input consisting of a plurality of characters;

constructing a set of breakpoints in the natural-language input;

combining weights of trigraph contexts that precede and follow each breakpoint to assign a weight to the breakpoint in the natural-language input;

traversing substrings of the natural-language input in an order determined by the weights assigned to the breakpoints;

identifying a plurality of linkable components by the traversal of substrings wherein a linkable component is identified by locating the component in a lexicon; and

returning a segmented string consisting of a plurality of linkable components spanning the natural-language input, wherein the segmented string is interpreted as a compound word.

9. A method for segmenting compound words in an unrestricted natural-language input, the method comprising:

receiving a natural-language input consisting of a plurality of characters;

constructing a set of breakpoints in the natural-language input;

combining weights of bigraph contexts that precede and follow each breakpoint to assign a weight to the breakpoint in the natural-language input;

traversing substrings of the natural-language input in an order determined by the weights assigned to the breakpoints;

identifying a plurality of linkable components by the traversal of substrings wherein a linkable component is identified by locating the component in a lexicon; and

returning a segmented string consisting of a plurality of linkable components spanning the natural-language input, wherein the segmented string is interpreted as a compound word.

10. A method for segmenting compound words in an unrestricted natural-language input, the method comprising:

receiving a natural-language input consisting of a plurality of characters;

constructing a set of breakpoints in the natural-language input;

combining weights of tetragraph contexts that precede and follow each breakpoint to assign a weight to the breakpoint in the natural-language input;

traversing substrings of the natural-language input in an order determined by the weights assigned to the breakpoints;

identifying a plurality of linkable components by the traversal of substrings wherein a linkable component is identified by locating the component in a lexicon; and

returning a segmented string consisting of a plurality of linkable components spanning the natural-language input, wherein the segmented string is interpreted as a compound word.