Elamur Research⌕
☰
home / papers / 1996 / A Stochastic Finite-State Word-Segmentation Algorithm for Chinese

A Stochastic Finite-State Word-Segmentation Algorithm for Chinese

Summary

Written Chinese does not mark word boundaries with spaces, so any downstream system, such as text-to-speech, translation, or retrieval, must first recover words from strings of hanzi. Sproat and colleagues at Bell Laboratories frame segmentation as a search over weighted finite-state transducers. The model combines a static dictionary with sub-models for words that no word list can fully cover: morphological derivatives, Chinese personal names, and transliterated foreign names. Costs for unseen items of these types are estimated with the Good-Turing method. Resources include a text corpus from United Informatics, the BDC 'Behavior Chinese-English Electronic Dictionary', and name corpora. Because the system was built for the Bell Labs Mandarin TTS system, it also outputs pronunciations. Its segmentations were compared against those of several human annotators, who themselves disagree on a single correct segmentation, and the system was judged to perform well (the exact figures fall in the portion of the text not provided). The work matters because it shows that segmentation can sit in one uniform, extensible weighted-FST framework that plugs directly into larger speech and language pipelines.

Key points

  • Segmentation matters for Mandarin TTS for several reasons:
    • homographic hanzi are pronounced differently depending on the word they belong to;
    • Third Tone Sandhi and Northern-dialect tone neutralization apply at the word level;
    • part-of-speech-based prosody requires word units.
  • The Good-Turing method assigns likelihoods to unseen derived words and personal names, so the segmenter handles items absent from the lexicon.
  • As deployed within Bell Labs' Mandarin TTS, the transducer contains roughly 32,000 states and 209,000 arcs. Inverting it, so that it maps phonemes to hanzi, makes it usable for speech recognition.
  • Reduplication patterns cannot be modeled directly by finite-state machinery and must be pre-expanded into the lexicon. These include A-not-A questions (e.g., gaol-bu4-gaol-xing4) and AABB adverbs.
  • By comparison, Gan's earlier system was tested with only a few hundred lexicon words and thirty sentences. The authors argue that its classifier and modal-verb cues could be approximated with finite-state local grammars.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Tokenization & segmentation

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@article{sproat1996stochastic,
  title = {{A Stochastic Finite-State Word-Segmentation Algorithm for Chinese}},
  author = {Sproat, Richard W. and Shih, Chilin and Gale, William and Chang, Nancy},
  journal = {Computational Linguistics},
  year = {1996},
  doi = {10.3115/981732.981742},
  url = {https://doi.org/10.3115/981732.981742}
}

References

52 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Antworth, Evan. 1990. PC-KIMMO: A Two-Level Processor for Morphological Analysis. Occasional Publications in Academic Computing, 16. Summer Institute of Linguistics, Dallas, TX. find
  2. Baayen, Harald. 1989. A Corpus-Based Approach to Morphological Productivity: Statistical Analysis and Psycholinguistic Interpretation. Ph.D. thesis, Free University, Amsterdam. find
  3. Becker, Richard, John Chambers, and Allan Wilks. 1988. The New S Language. Wadsworth and Brooks, Pacific Grove. find
  4. Chang, Chao-Huang and Cheng-Der Chen. 1993. A study on integrating Chinese word segmentation and part-of-speech tagging. Communications of the Chinese and Oriental Languages Information Processing Society, 3(2):69-77. find
  5. Chang, Jyun-Shen, C.-D. Chen, and Shun-De Chen. 1991. Xianzhishi manzu ji jilu zuijiahua de zhongwen duanci fangfa [Chinese word segmentation through constraint satisfaction and statistical optimization]. In Proceedings of ROCLING IV, pages 147-165, Taipei. ROCLING. find
  6. Chang, Jyun-Shen, Shun-De Chen, Ying Zheng, Xian-Zhong Liu, and Shu-Jin Ke. 1992. Large-corpus-based methods for Chinese personal name recognition. find
  7. Journal of Chinese Information Processing, 6(3):7-15. find
  8. Chao, Yuen-Ren. 1968. A Grammar of Spoken Chinese. University of California Press, Berkeley, CA. find
  9. Chen, Keh-Jiann and Shing-Huan Liu. 1992. Word identification for Mandarin Chinese sentences. In Proceedings of COLING-92, pages 101-107. COLING. find
  10. Church, Kenneth and William Gale. 1991. A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech and Language, 5(1):19-54. find
  11. Church, Kenneth and Patrick Hanks. 1989. Word association norms, mutual information and lexicography. In 27th Annual Meeting of the Association for Computational Linguistics, pages 76-83, Morristown, NJ. Association for Computational Linguistics. find our card
  12. DeFrancis, John. 1984. The Chinese Language. University of Hawaii Press, Honolulu. find
  13. Fan, C.-K. and W.-H. Tsai. 1988. Automatic word identification in Chinese sentences by the relaxation technique. Computer Processing of Chinese and Oriental Languages, 4:33-56. find
  14. Fung, Pascale and Dekai Wu. 1994. Statistical augmentation of a Chinese machine-readable dictionary. In WVLC-94, Second Annual Workshop on Very Large Corpora. find
  15. Gan, Kok-Wee. 1994. Integrating Word Boundary Disambiguation with Sentence Understanding. Ph.D. thesis, National University of Singapore. find
  16. Gu, Ping and Yuhang Mao. 1994. Hanyu zidong fenci de jinlin pipei suanfa ji qi zai QHFY hanying jiqi fanyi xitong zhong de shixian [The adjacent matching algorithm of Chinese automatic word segmentation and its implementation in the QHFY Chinese-English system]. In International Conference on Chines… find
  17. Hirschberg, Julia. 1993. Pitch accent in context: Predicting intonational prominence from text. Art~'cial Intelligence, 63:305-340. find
  18. Huang, Chu-Ren, Kathleen Ahrens, and Keh-jiann Chen. 1993. A data-driven approach to psychological reality of the mental lexicon: Two studies on Chinese corpus linguistics. Presented at the conference on Language and its Psychobiological Bases, December. find
  19. Kaplan, Ronald and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20:331-378. find
  20. Karttunen, Lauri, Ronald Kaplan, and Annie Zaenen. 1992. Two-level morphology with composition. In COLING-92, pages 141-148. COLING. find
  21. Koskenniemi, Kimmo. 1983. Two-Level Morphology: A General Computational Model for Word-Form Recognition and Production. Ph.D. thesis, University of Helsinki, Helsinki. find
  22. Kupiec, Julian. 1992. Robust part-of-speech tagging using a hidden Markov model. Computer Speech and Language. Submitted. find
  23. Li, B.Y., S. Lin, C.F. Sun, and M.S. Sun. 1991. Yi zhong zhuyao shiyong yuliaoku biaoji jinxing qiyi jiaozheng de zuida pipei hanyu zidong fenci suanfa sheji [A maximum-matching word segmentation algorithm using corpus tags for disambiguation]. In ROCLING IV, pages 135-146, Taipei. ROCLING. find
  24. Li, Charles and Sandra Thompson. 1981. Mandarin Chinese: A Functional Reference Grammar. University of California Press, Berkeley, CA. find
  25. Liang, Nanyuan. 1986. Shumian hanyu zidong fenci xitong-CDWS [A written Chinese automatic segmentation system-CDWS]. Journal of Chinese Information Processing, 1(1):44-52. find
  26. Lin, Ming-Yu, Tung-Hui Chiang, and Keh-Yi Su. 1993. A preliminary study on unknown word problem in Chinese word segmentation. In ROCLING 6, pages 119-141. ROCLING. find
  27. Mohri, Mehryar. 1993. Analyse et representation par automates de structures syntaxiques compos~es. Ph.D. thesis, University of Paris 7, Paris. find
  28. Mohri, Mehryar. 1995. Minimization algorithms for sequential transducers. Theoretical Computer Science. Submitted. find
  29. Nagata, Masaaki. 1994. A stochastic Japanese morphological analyzer using a forward-DP backward A* N-best search algorithm. In Proceedings of COLING-94, pages 201-207. COLING. find
  30. Nie, Jian-Yun, Wanying Jin, and Marie-Louise Hannan. 1994. A hybrid approach to unknown word detection and segmentation of Chinese. In International Conference on Chinese Computing, Singapore. find
  31. Peng, Z.-Y. and J-S. Chang. 1993. Zhongwen cihui qiyi zhi yanjiu--duanci yu cixing biaoshi [Research on Chinese lexical ambiguity--segmentation and part-of-speech tagging]. In ROCLING 6, pages 173-193. ROCLING. find
  32. Pereira, Fernando, Michael Riley, and Richard Sproat. 1994. Weighted rational transductions and their application to human language processing. In ARPA Workshop on Human Language Technology, pages 249-254. Advanced Research Projects Agency, March 8-11. find
  33. PRCNSC, 1994. Contemporary Chinese Language Word Segmentation SpecS'cation for Information Processing. People's Republic of China National Standards Committee. In Chinese. find
  34. ROCLING. 1993. Jisuan yuyanxue tongxun [Computational linguistics communications]. Newsletter of the Republic of China Computational Linguistics Society (ROCLING), April. In Chinese. find
  35. Shih, Chilin. 1986. The Prosodic Domain of Tone Sandhi in Chinese. Ph.D. thesis, UCSD, La Jolla, CA. find
  36. Sproat, Richard. 1992. Morphology and Computation. MIT Press, Cambridge, MA. find
  37. Sproat, Richard. 1994. English noun-phrase accent prediction for text-to-speech. Computer Speech and Language, 8:79-94. find
  38. Sproat, Richard. 1995. A finite-state architecture for tokenization and grapheme-to-phoneme conversion for multilingual text analysis. In Susan Armstrong and Evelyne Tzoukermann, editors, Proceedings of the EACL SIGDAT Workshop, pages 65-72, Dublin, Ireland. Association for Computational Linguistics… find
  39. Sproat, Richard and Chilin Shih. 1990. A statistical method for finding word boundaries in Chinese text. Computer Processing of Chinese and Oriental Languages, 4:336-351. find
  40. Sproat, Richard and Chilin Shih. 1995. A corpus-based analysis of Mandarin nominal root compounds. Journal of East Asian Linguistics, 4(1):1-23. find
  41. Tang, Ting-Chih. 1988. Hanyu Cifa Jura Lunji [Studies on Chinese Morphology and Syntax], volume 2. Student Book Company, Taipei. In Chinese. find
  42. Tang, Ting-Chih. 1989. Hanyu Cifa Jura X~qi [Studies on Chinese Morphology and Syntax: 2], volume 2. Student Book Company, Taipei. In Chinese. find
  43. Torgerson, Warren. 1958. Theory and Methods of Scaling. Wiley, New York. find
  44. Tzoukermann, Evelyne and Mark Liberman. 1990. A finite-state morphological processor for Spanish. In COLING-90, Volume 3, pages 3: 277-286. COLING. find
  45. Wang, Liang-Jyh, Wei-Chuan Li, and Chao-Huang Chang. 1992. Recognizing unregistered names for Mandarin word identification. In Proceedings of COLING-92, pages 1239-1243. COLING. find
  46. Wang, Michelle and Julia Hirschberg. 1992. Automatic classification of intonational phrase boundaries. Computer Speech and Language, 6:175-196. find
  47. Wang, Yongheng, Haiju Su, and Yan Mo. 1990. Automatic processing of Chinese words. Journal of Chinese Information Processing, 4(4):1-11. find
  48. Wieger, L. 1965. Chinese Characters. Dover, New York. Republication of second edition, published 1927 by Catholic Mission Press. find
  49. Wu, Dekai and Pascale Fung. 1994. Improving Chinese tokenization with linguistic filters on statistical lexical acquisition. In Proceedings of the Fourth Conference on Applied Natural Language Processing, pages 180-181, Stuttgart, October. find
  50. Wu, Zimin and Gwyneth Tseng. 1993. Chinese text segmentation for text retrieval: Achievements and problems. find
  51. Journal of the American Society for Information Science, 44(9):532-542. find
  52. Yeh, Ching-long and Hsi-Jian Lee. 1991. Rule-based word identification for Mandarin Chinese sentences--a unification approach. Computer Processing of Chinese and Oriental Languages, 5(2):97-118. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sproat-1996-stochastic-finite-state-word-segmentation/