Search-based word segmentation method and device for language without word boundary tag

• US 8,131,539 B2
• Filed: 03/07/2008
• Issued: 03/06/2012
• Est. Priority Date: 03/07/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Wen, Qin, Yong, Wang, Xin Jing
• Primary Examiner(s): Neway, Samuel G
• Application Number:
  US12/044,258
• Publication Number:
  US 20080221863A1
• Time in Patent Office: 1,460 Days
• Field of Search: 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

The present invention discloses a search-based segmentation method and device for a language without a word boundary tag. The inventive method includes the steps of: a. providing at least one search engine with a segment of a text including at least one segment; b. searching for the segment through the at least one search engine, and returning search results; and c. selecting a word segmentation approach for the segment in accordance with at least part of the returned search results. The invention solves the problems of word segmentation for a language without a word boundary tag, and thus combat the limitations of the prior art in terms of flexibility, dependence upon coverage of dictionaries, available training data corpuses, processing of a new word, etc.

Claims

1. A search-based word segmentation method for a language without a word boundary tag, comprising the steps of:

a. providing at least one search engine with a segment of a text comprising at least one segment;

b. searching for the segment through the at least one search engine, and returning search results each including candidate word segmentation units; and

c. determining a word segmentation approach for the segment in accordance with at least part of the returned search results by performing steps of;

extracting, from the at least part of the returned search results, all candidate word segmentation units appearing in the segment;

scoring the extracted candidate word segmentation units;

ranking subsets of extracted candidate word segmentation units in accordance with the scoring, wherein the candidate word segmentation units in each subset sequentially form the segment; and

selecting a highest-ranked subset as the word segmentation approach for the segment.

2. The method according to claim 1, wherein the at least part of the returned search results are top-ranked search results.

3. The method according to claim 1, wherein the step c further comprises the step of filtering out, from the extracted candidate word segmentation units, an invalid candidate word segmentation unit, which is one of a unigram or a word segmentation unit that does not appear in the segment.

4. The method according to claim 1, wherein the method for scoring the candidate word segmentation units is frequency-based, and for the part of the search results, a ratio of the number of occurrences of the scored candidate word segmentation units to the total number of occurrences of all the candidate segmentation units is taken as the score for each of the scored candidate word segmentation units.

5. The method according to claim 1, wherein the method for scoring the candidate word segmentation units is SVM (Support Vector Machine)-based, using an SVM classifier or an SVM regression model to score each candidate word segmentation unit;

and representing the candidate word segmentation units, which are data points, as feature vectors so as to train the SVM classifier and the SVM regression model.

6. The method according to claim 5, wherein a feature extracted for each candidate word segmentation unit comprises one or a combination of the following features:

a number of characters in the candidate word segmentation unit;

an average occurrence rate, which is a number of times that the candidate word segmentation unit appears, divided by a number of documents in the search results returned by the search engine; and

a document frequency, which is a number of search results containing the candidate word segmentation unit.

7. The method according to claim 4, wherein a subset of candidate word segmentation units with a highest average score of candidate word segmentation units is selected as the word segmentation approach for the segment.

8. The method according to claim 1, wherein the extracting of candidate word segmentation units from the returned search results is implemented via extracting highlighted phrases in returned snippets.

9. The method according to claim 1, wherein, when the search engine is a self-maintained search engine, a word segmentation unit is obtained by viewing adjacencies of positions of terms in a document using information provided from an indexing table.

10. A search-based word segmentation device for a language without a word boundary tag, comprising:

at least one search engine, adapted to receive a segment of a text comprising at least one segment, to search in a search network for the segment, and to return search results each including candidate word segmentation units; and

a word segmentation result generating means, adapted to select a word segmentation approach for the segment in accordance with at least part of the returned search results by extracting, from the at least part of the returned search results, all candidate word segmentation units appearing in the segment;

scoring the extracted candidate word segmentation units;

ranking subsets of extracted candidate word segmentation units in accordance with the scoring, wherein the candidate word segmentation units in each subset sequentially form the segment; and

selecting a highest-ranked subset as the word segmentation approach for the segment.

11. The device according to claim 10, wherein the at least part of the search results returned by the at least one search engine are top-ranked search results.

12. The device according to claim 10, wherein the word segmentation result generating means is further adapted to filter out, from the extracted candidate word segmentation units, an invalid candidate word segmentation unit, which is one of a unigram or a word segmentation unit that does not appear in the segment.

13. The device according to claim 10, wherein the word segmentation result generating means scores the candidate word segmentation units in a frequency-based manner, and the word segmentation result generating means is further adapted to:

for the part of the search results, take a ratio of the number of occurrences of the scored candidate word segmentation units to the total number of occurrences of all the candidate segmentation units as the score for each of the scored candidate word segmentation units.

14. The device according to claim 10, wherein the word segmentation result generating means scores the candidate word segmentation units in a SVM (Support Vector Machine)-based manner, uses an SVM classifier or an SVM regression model to score each candidate word segmentation unit, and represents the candidate word segmentation units, which are data points, as feature vectors so as to train the SVM classifier and the SVM regression model.

15. The device according to claim 14, wherein a feature extracted for each candidate word segmentation unit comprises one or a combination of the following features:

a number of characters in the candidate word segmentation unit;

an average occurrence rate, which is a number of times that the candidate word segmentation unit appears, divided by a number of documents in the search results returned by the search engine; and

a document frequency, which is a number of search results containing the candidate word segmentation unit.

16. The device according to claim 13, wherein the word segmentation result generating means is further adapted to select a subset of candidate word segmentation units with a highest average score of candidate word segmentation units as the word segmentation approach for the segment.

17. The device according to claim 10, wherein the word segmentation result generating means extracts candidate word segmentation units from the returned search results by extracting highlighted phrases in returned snippets.

18. The device according to claim 10, wherein, when the search engine is a self-maintained search engine, the word segmentation result generating means is adapted to use information provided from an indexing table to view adjacencies of positions of terms in a document to obtain a word segmentation unit.

19. A computer program product stored on a non-transitory computer readable storage medium and executed by a computer to perform a search-based word segmentation method for a language without a word boundary tag, wherein said method comprises the steps of:

a. providing at least one search engine with a segment of a text comprising at least one segment;

b. searching for the segment through the at least one search engine, and returning search results each including candidate word segmentation units; and

c. determining a word segmentation approach for the segment in accordance with at least part of the returned search results by extracting, from the at least part of the returned search results, all candidate word segmentation units appearing in the segment;

scoring the extracted candidate word segmentation units;

ranking subsets of extracted candidate word segmentation units in accordance with the scoring, wherein the candidate word segmentation units in each subset sequentially form the segment; and

selecting a highest-ranked subset as the word segmentation approach for the segment.