# US 7,610,189 B2 · Method and apparatus for efficient segmentation of compound words using probabilistic breakpoint traversal

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,610,189 B2
- Document ID: US7610189B2
- Status: Granted
- Kind: B2
- Application number: 10/042,528
- Filed: 2001-10-18
- Published: 2003-05-22
- Granted: 2009-10-27
- Earliest claimed: 2001-10-18
- Assignees: Nuance Communications, Inc.
- Inventors: Andrew William Mackie
- Web page: https://patentgrep.com/patent/US7610189B2

## CPC

- G06F 40/268: Morphological analysis
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for segmenting a compound word in an unrestricted natural-language input is disclosed. The method comprises receiving a natural-language input consisting of a plurality of characters. Next, a set of probabilistic breakpoints based on a probabilistic breakpoint analysis is constructed in the natural-language input. A plurality of linkable components is identified by traversal of substrings of the natural-language input delimited by the set of probabilistic breakpoints. Finally, a segmented string consisting of a plurality of linkable components spanning the natural-language input is returned. The segmented string can be interpreted as a compound word.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein the augmented breakpoint-delimited substring tester generates one of:
the segmented string; and
a failure signal.

### Claim 6 (depends on 5)

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

### Claim 7 (depends on 1)

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

### Claim 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.

### Claim 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.

### Claim 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.