Segmentation from 97% to 100%: Is It Time for Some Linguistics?

D 2012

Segmentation from 97% to 100%: Is It Time for Some Linguistics?

SOJKA, Petr

Basic information

Original name

Segmentation from 97% to 100%: Is It Time for Some Linguistics?

Name in Czech

Segmentace z 97% na 100%: není čas pro trochu lingvistiky?

Authors

SOJKA, Petr (203 Czech Republic, guarantor, belonging to the institution)

Edition

první. Brno, Sixth Workshop on Recent Advances in Slavonic Natural Languages Processing, RASLAN 2012, p. 121--131, 11 pp. 2012

Publisher

Tribun EU

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

Slides full paper in PDF Workshop web page

RIV identification code

RIV/00216224:14330/12:00062085

Organization unit

Faculty of Informatics

ISBN

978-80-263-0313-8

Keywords (in Czech)

soutěživé vzory;segmentace;dělení slov;NP úplné problémy;generování vzorů;patgen;kontextově závislé vzory;strojové učení;jazykové inženýrství;EuDML

Keywords in English

competing patterns;segmentation;hyphenation;NP problems;pattern generation;patgen;context-sensitive patterns;machine learning;natural language engineering;EuDML

Abstract

V originále

Many tasks in natural language processing (NLP) require \emph{segmentation} algorithms: segmentation of paragraph into sentences, segmentation of sentences into words is needed in languages like Chinese or Thai, segmentation of words into syllables (\emph{hyphenation}) or into morphological parts (e.g.\ getting word stem for indexing), and many other tasks (e.g.\ tagging) could be formulated as segmentation problems. We evaluate methodology of using \emph{competing patterns} for these tasks and decide on the complexity of creation of space-optimal (minimal) patterns that completely (100\,\%) implement the segmentation task. We formally define this task and prove that it is in the class of \emph{non-polynomial} optimization problems. However, finding space-efficient competing patterns for real NLP tasks is feasible and gives efficient scalable solutions of segmentation task: segmentation is done in \emph{constant} time with respect to the size of segmented dictionary. Constant time of access to segmentations makes competing patterns attractive data structure for many NLP tasks.

Links

LA09016, research and development project

Name: Účast ČR v European Research Consortium for Informatics and Mathematics (ERCIM) (Acronym: ERCIM)

Investor: Ministry of Education, Youth and Sports of the CR, Czech Republic membership in the European Research Consortium for Informatics and Mathematics

250503, interní kód MU

Name: The European Digital Mathematics Library (Acronym: EuDML)

Investor: European Union

Citovat

SOJKA, Petr. Segmentation from 97% to 100%: Is It Time for Some Linguistics? In Aleš Horák, Pavel Rychlý. Sixth Workshop on Recent Advances in Slavonic Natural Languages Processing, RASLAN 2012. první. Brno: Tribun EU, 2012, p. 121--131. ISBN 978-80-263-0313-8.

@inproceedings{1075316,
   author = {Sojka, Petr},
   address = {Brno},
   booktitle = {Sixth Workshop on Recent Advances in Slavonic Natural Languages Processing, RASLAN 2012},
   edition = {první},
   editor = {Aleš Horák, Pavel Rychlý},
   keywords = {competing patterns;segmentation;hyphenation;NP problems;pattern generation;patgen;context-sensitive patterns;machine learning;natural language engineering;EuDML},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Brno},
   isbn = {978-80-263-0313-8},
   pages = {121--131},
   publisher = {Tribun EU},
   title = {Segmentation from 97% to 100%: Is It Time for Some Linguistics?},
   url = {http://www.fi.muni.cz/usr/sojka/presentations/sojka-raslan-pres2012.pdf},
   year = {2012}
}

TY  - JOUR
ID  - 1075316
AU  - Sojka, Petr
PY  - 2012
TI  - Segmentation from 97% to 100%: Is It Time for Some Linguistics?
PB  - Tribun EU
CY  - Brno
SN  - 9788026303138
KW  - competing patterns;segmentation;hyphenation;NP problems;pattern generation;patgen;context-sensitive patterns;machine learning;natural language engineering;EuDML
UR  - http://www.fi.muni.cz/usr/sojka/presentations/sojka-raslan-pres2012.pdf
L2  - http://www.fi.muni.cz/usr/sojka/papers/sojka-raslan2012.pdf
N2  - Many tasks in natural language processing (NLP) require \emph{segmentation} algorithms: segmentation of paragraph into sentences, segmentation of sentences into words is needed in languages like Chinese or Thai, segmentation of words into syllables (\emph{hyphenation}) or into morphological parts (e.g.\ getting word stem for indexing), and many other tasks (e.g.\ tagging) could be formulated as segmentation problems. We evaluate methodology of using \emph{competing patterns} for these tasks and decide on the complexity of creation of space-optimal (minimal) patterns that completely (100\,\%) implement the segmentation task. We formally define this task and prove that it is in the class of \emph{non-polynomial} optimization problems. However, finding space-efficient competing patterns for real NLP tasks is feasible and gives efficient scalable solutions of segmentation task: segmentation is done in \emph{constant} time with respect to the size of segmented dictionary. Constant time of access to segmentations makes competing patterns attractive data structure for many NLP tasks.
ER  -

SOJKA, Petr. Segmentation from 97\%{} to 100\%{}: Is It Time for Some Linguistics? In Aleš Horák, Pavel Rychlý. \textit{Sixth Workshop on Recent Advances in Slavonic Natural Languages Processing, RASLAN 2012}. první. Brno: Tribun EU, 2012, p.~121--131. ISBN~978-80-263-0313-8.

Detailed Information on Publication Record