Take the 2-minute tour ×
Linguistics Stack Exchange is a question and answer site for professional linguists and others with an interest in linguistic research and theory. It's 100% free, no registration required.

Most algorithms for splitting text into sentences which I've found rely on punctuation being correct. However, in many real world applications, there will be substantial numbers of punctuation errors (missing periods, extraneous periods, etc.) Are there sentence-splitting algorithms which deal with this?

share|improve this question
1  
For English speech, yes; intonation gives it away. For English spelling, no, not really. Not only doesn't English record intonational information reliably in its orthography, but what little does leak through into punctuation is quite inconsistently applied, and that's never going to change. Get used to culling ambiguous parse options of text through non-syntactic information. Like frames, for instance. –  jlawler Feb 4 '13 at 18:51
    
I was in fact imagining something like "if the likelihood of a sentence as given is too low, try splitting it in different reasonable places (or joining with next/previous sentence). If one of these splits increases likelihood substantially, repeat." –  Alexey Romanov Feb 5 '13 at 7:46
    
Or just trying to select and run a suitable machine learning algorithm, which would presumably assign high weights to punctuation and to capital letters, but could detect ends of sentence even if they are missing. The question is if this achieves enough accuracy... –  Alexey Romanov Feb 5 '13 at 7:57
1  
It'll give you enough semantics to translate roughly, but it's unlikely to give sentence boundaries. At least as they writer intended them. –  jlawler Feb 5 '13 at 23:20
1  
The more I think about it, though, just the change in number of options should give you most constituent boundaries, including sentences, regardless of punctuation. But you couldn't distinguish sentence boundaries from other constituent boundaries without more processing of the kinds of options. –  jlawler Feb 10 '13 at 23:58

1 Answer 1

up vote 2 down vote accepted

Here's how such a sentence boundary algorithm could be built.

The crucial thing is to come up with sequences of words (n-grams) that have a high likelihood of occurring at the end of a sentence or at the start of a sentence and a small likelihood of occurring within a sentence.

A list of these n-grams could be compiled with a large corpus such as the written part of the British National Corpus. Once the list is complete, the algorithm would go through the text without punctuation and for every word boundary look up the preceding n-grams in the list. For example, in a sequence of words such as

have you seen it it's incredible

once the algorithm is at have you seen it it would look up seen it in the list and give you a score such as: Occurred 56 times at the end of sentences and 22 times within a sentence, i.e. a score of 56/22 = 2.5. There should also be a list of three-word sequences, so look up you seen it, which might have a score of 13/2=6.5, then go on with a four-word list. Now average all scores and if it passes a certain threshold (which would need to be determined empirically) the algorithm sets a sentence boundary.

The same could be done with n-grams/word sequences occurring sentence-initially, and n-grams which occur at sentence boundaries.

Edit: As @P Elliott pointed out in the comments, a somewhat similar algorithm has been implemented and has high accuracy.

share|improve this answer
    
,Your answer is very interesting,Have you done any experiment on what you describe as an algorithm?Or any other body has done experiment on it?And why do you not write down an explicit algorithm in the form we usually read or encounter? –  XL _at_China Aug 12 '13 at 12:30
1  
,As far as I know,there is no algorithm for the question now.You know computer science is not like traditional linguistics,it has to be based on proof or experiment.We can not present an algorithm by imagination.I begin to know why my answer on the forum usually be downvoted . –  XL _at_China Aug 12 '13 at 12:40
1  
In fact, if it's simple as this, i'd be frankly amazed if it hadn't been implemented. The algorithm described in this paper sounds similar to what you have in mind: aclweb.org/anthology-new/A/A97/A97-1004.pdf. –  P Elliott Aug 12 '13 at 13:33
1  
Well, so far it seems that no such algorithm exists (and if somebody comes up with one I'll be happy to upvote that answer). So technically the answer should be "No, there is none". Suggesting a way such an algorithm could work is surely more helpful than that. Also, this kind of pattern learning is often used in NLP, for example to train parsers. And evaluation (short of actual implementation) is possible in the sense that I can think of other algorithms for the problem that seem less likely to succeed, given previous NLP algorithms. –  robert Aug 12 '13 at 13:34
1  
No problem @robert - i hope i didn't sound too critical, your answer was interesting and well articulated. One difference between the algorithm i've linked to and the one you describe is that theirs only really looks at bigrams. They found that looking at larger contexts didn't meaningfully improve performance. Their model also focuses on existing punctuation in the text, and deciding on whether it marks a sentence boundary or not, rather than looking at every single word-boundary. The way that you've described it, i'd think that your algorithm might end up being computationally intractable. –  P Elliott Aug 12 '13 at 13:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.