Automatic segmentation of texts comprising chunks without separators

• US 7,536,296 B2
• Filed: 05/28/2003
• Issued: 05/19/2009
• Est. Priority Date: 05/28/2003
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Loquendo SpA (Microsoft Corporation)
• Inventors: Badino, Leonardo
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Neway; Samuel G
• Application Number:
  US10/556,940
• Publication Number:
  US 20070118356A1
• Time in Patent Office: 2,183 Days
• Field of Search: 704/1, 704/2, 704/3, 704/4, 704/5, 704/7, 704/8, 704/9, 704/10, 704/207, 704/211, 704/231, 704/235, 704/236, 704/240, 704/242, 704/243, 704/246, 704/249, 704/251, 704/252, 704/254, 704/255, 704/256, 704/257, 704/258, 704/260, 704/266, 704/267, 704/270, 704/275, 704/276, 704/277, 704/E13.011, 704/E13.012, 704/E13.013, 704/E15.003, 704/E15.004, 704/E15.005, 704/E15.008, 704/E15.014, 704/E15.018, 704/E15.02, 704/E15.022, 704/E15.023, 704/E15.024, 704/E15.025, 704/E15.028, 704/E15.04, 704/E15.045, 717/114, 707/2, 707/3, 707/4, 707/5, 707/6, 707/10, 707/102, 707/104.1, 707/E17.039, 707/E17.058, 707/E17.084, 707/E17.103, 400/109, 400/110, 400/484, 400/486, 400/487, 400/489, 382/177, 382/181, 382/185, 382/186, 382/187, 382/189, 382/228, 382/229, 345/156, 345/157, 345/168, 345/171, 345/173, 345/467, 345/471, 345/472.3
• US Class Current: 704/9
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Syntagms of a text including individual elements written without separators are segmented into chunks having strings including at least one individual element, such as an ideogram of the Mandarin Chinese language. A lexicon is defined including a set of strings, each string having at least one of the individual elements. The syntagm, being segmented, is orderly searched on an element-by-element basis by searching within the lexicon strings corresponding to any of the chunks. In the case of a positive search result, the corresponding chunk located is stored with an associated cost. A check is made as to whether the chunk located was already present in the lexicon. If the chunk located was already present, the cost associated therewith is reduced. A plurality of candidate segmentation sequences are thus generated, each corresponding to a respective segmentation pattern having associated a corresponding accrued cost. The candidate sequence having the lowest associated cost is selected as the final result of segmentation.

Claims

1. A method of segmenting into chunks syntagms of a text including individual elements written without separators, said chunks comprising strings including at least one of said individual elements, including the steps of:

defining a lexicon including a set of strings, each string comprising at least one of said individual elements, wherein the strings in said lexicon are at least partly representative of said chunks, the lexicon also including a dynamic lexicon and a static lexicon;

orderly searching the syntagm being segmented on an element-by-element basis by searching, within said lexicon, strings corresponding to any of said chunks, wherein, in the case of a positive search result, the corresponding chunk located is stored with an associated cost;

checking whether the chunk located was already present in at least the dynamic lexicon and, in the case where the chunk located was already present, reducing the cost associated therewith;

storing in a computer memory, as a result of said orderly searching, a plurality of candidate segmentation sequences, each corresponding to a respective segmentation pattern and having an associated corresponding accrued cost;

selecting as the final result of segmentation the candidate sequence having the lowest associated accrued cost, and

increasing said associated cost by a constant value at each new step in said searching on an element-by-element basis.

2. The method of claim 1, wherein, in the presence of two candidate sequences having the same associated cost, further comprising the step of selecting as a result of segmentation the candidate sequence selected from the group consisting of:

the sequence having the longer first chunk, and

the sequence having the lower length variance.

3. The method of claim 1, wherein, when at least one syntagm in said text has been previously segmented, further comprising the steps of determining at least one of:

the number of chunks located in the instant syntagm that were already present in said at least one previously segmented syntagm, and

the count of the chunks already found during the previous segmentation process.

4. The method of claim 3, wherein said sequence having the minimum associated cost is selected on the basis of a cost function including at least one of said number of chunks and said count.

5. The method of claim 3, wherein said sequence having the minimum associated cost is selected on the basis of a cost function including the ratio of said number of chunks and said count.

6. The method of claim 1, comprising the step of dispensing with those chunks having a cost higher than a given threshold when said associated cost is increased.

7. The method of claim 1, comprising, in the case of a positive search result, the step of shortening the string searched by eliminating one of the end elements thereof, the search being then repeated on the basis of said shortened string.

8. The method of claim 7, comprising the step of shortening said string by eliminating the rightmost element thereof.

9. The method of claim 1, comprising the step of managing the dynamic lexicon, said managing comprising the steps of:

if the chunk located was already present in the dynamic lexicon, reducing by a constant value the cost associated thereto,

if the chunk located was previously absent from the dynamic lexicon, checking whether the dynamic lexicon is full, and

i) if the dynamic lexicon is not full, inserting the chunk located in the dynamic lexicon with the respective cost decreased by a constant value, and

ii) if the dynamic lexicon is full, searching in the dynamic lexicon for any chunk having an associated cost higher than a given cost threshold and, if such a chunk is found, substituting the chunk located for such a chunk.

10. The method of claim 1, comprising the steps of:

defining at least a part of said set of strings in said lexicon (LEX) as representative of special chunks corresponding to defined rules;

orderly searching the syntagm being segmented on an element-by-element basis by searching within said lexicon at least one of;

(A) the longest string corresponding to any of said special chunks, wherein, in the case of a positive search result, the corresponding chunk located is stored with an associated first cost (CF), and

(B) the longest string corresponding to any of the other strings in said lexicon, wherein, in the case of a positive search result, the corresponding chunk located is stored with an associated second cost (CM), said second cost (CM) being higher than said first cost (CF),

wherein if neither of said searches under (A) and (B) leads to a positive result, the individual element used as the starting element of the search is stored with an associated third cost (CS), said third cost (CS) being higher than said second cost (CM).

11. The method of claim 10, comprising the step of increasing said first, second and third costs by a constant value at each new step in said at least one search on an element-by-element basis.

12. The method of claim 11, comprising the step of dispensing with those chunks having a cost higher than a given threshold when said costs are increased.

13. The method of claim 12, wherein said given threshold is selected equal to said second cost.

14. The method of claim 10, wherein at least one syntagm in said text has been previously segmented, and comprises the steps of:

determining the number (NOL) of chunks located in the instant syntagm that were already present in said at least one previously segmented syntagm and the count (NW) of the chunks already found during the segmentation process;

selecting said sequence having the minimum associated cost on the basis of a cost function defined as follows;

i) if the chunk located was not previously included in said lexicon

Cost W_ij=CSLEX

ii) otherwise,

CostW_ij=CSLEX+(Cfs−

CSLEX)*(1−

NOL/NW)/K

wherein Cfs is equal to said second cost (CM) or said first cost (CF) depending on whether the word considered was located by means of said second search (B) or said first search (A), K is a constant value, CSLEX is the cost associated with the chunk W_ij in said lexicon, and NOL and NW are said number and said count, respectively.

15. The method of claim 1, comprising the step of coding said individual elements to bit strings using to at least one of an ISO standard, or Unicode, GB or BIG5 coding techniques.

16. The method of claim 1, wherein said individual elements correspond to ideograms.

17. The method of claim 16, wherein said ideograms are ideograms of Mandarin Chinese language.

18. The method of claim 17, comprising the step of transliterating said ideograms into pinyin phonetic transliteration before said syntagms are segmented.

19. The method of claim 10, wherein said special chunks are selected from the group:

dates, hours and numbers.

20. A segmentator for segmenting into chunks syntagms of a text including individual elements written without separators, said chunks comprising strings including at least one of said individual elements, the segmentator including a data processing structure configured for carrying out the method of claim 1.

21. A text-to-speech synthesis system comprising:

a text source for generating at least one text syntagm to be segmented into chunks, said syntagm including individual elements written without separators, said chunks comprising strings including at least one of said individual elements;

a segmentator for receiving said at least one text syntagm, the segmentator including a data processing structure configured for carrying out the method of claim 1, thus generating as the final result of segmentation said candidate sequence having the lowest associated cost; and

a speech signal generator for converting said sequence resulting from segmentation into a corresponding audio speech signal.

22. A computer memory encoded with a computer program product, the computer program product including software code portions for performing the steps of the method of any one of claims 1 to 5 and 6 to 16.