11

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?

5
  • 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, 2013 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." Feb 5, 2013 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... Feb 5, 2013 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, 2013 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, 2013 at 23:58

2 Answers 2

7

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 (A Maximum Entropy Approach to Identifying Sentence Boundaries) and has high accuracy.

10
  • ,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? Aug 12, 2013 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 . Aug 12, 2013 at 12:40
  • 2
    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, 2013 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, 2013 at 13:34
  • 2
    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, 2013 at 13:47
2

I built a sentence segmenter that works excellently on unpunctuated or partially punctuated text too. You can find it at https://github.com/bedapudi6788/deepsegment .

This models is based on the idea that Named Entity Recognition can be used for sentence boundary (i.e: beginning of a sentence or ending of a sentence). I utilised data from tatoeba for generating the training data and trained a BiLSTM+CRF model with glove embeddings and character level for this task.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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