I am trying to leverage NLTK and Python to perform some sentence completion. The sentences I'm working with are incomplete and pretty much just read as garbage. An example sentence would be something like this:

The red dog absolutely always.

I would like to use NLTK to turn the above sentence into something more like this:

The red dog will absolutely love you always.

It doesn't need to be this exactly, but something along the lines to make the first sentence actually have meaning.

I am new to NLP and am unsure of how to move forward with this. I figure I could use something like POS tagging and cross reference with a set of training data that could then fill in the missing parts of speech to make the sentence syntactically correct.

Is there a corpus that is used for this? Is my approach to this reasonable?

Thanks for any help!

  • You could parse the sentence with an adapted grammar and alter the parse tree (insert nodes for the verb etc.). Of course it will be very nondeterministic. What's your motivation?
    – Atamiri
    Commented Jan 30, 2014 at 17:46
  • I'm sorry, I'm not very familiar with the terminology. What is an "adapted grammar"? We have a program that generates a bunch of synthetic twitter tweets. However, these tweets are like the first sentence, most of them don't make any sense. So I'm trying to figure out how to turn our synthetic tweets into something more realistic.
    – Josh
    Commented Jan 30, 2014 at 18:22
  • You could create a grammar that accepts the tweets in the form they are generated. Then you could alter the parse tree and linearize it. As for your data-driven approach, you could use shallow parsing to recognize patterns in the tweets and convert them into something more complex (the "more complex" patterns could come from a corpus). But I'd suggest to change your "program that generates tweets" because it doesn't make much sense to generate nonsense and try to improve it subsequently.
    – Atamiri
    Commented Jan 30, 2014 at 20:38
  • Markov chains are often used for word prediction. Since you don't want prediction, but insertion, perhaps you could find ways of splitting your input sequence into fragments, and then feed the fragments into a word prediction stage? I think it would help if you told us why exactly you wish to do what you described...
    – prash
    Commented Jan 30, 2014 at 21:44
  • @prash I think deep parsing the sequences as incomplete sentences can give you a way of preserving fully what is there, while having complete syntactic determination of all the ways to complete the missing parts of speech. Then you can use probabilistic information, for example such as provided by Markov chains to further refine possibilities, and even take the full context into account. Would otherwise Markov chains alone garantee syntactic correctness and consistency with the initial incomplete sequence.
    – babou
    Commented Mar 7, 2014 at 23:11

1 Answer 1


The issue of completing incomplete sentences has actually been adressed formally. There are many way to view it. Modifying the grammar is a possibility, but not the best method in my opinion, at least if you are too crude about it. There are very generic techniques for ill-formed input that can be used to modify in various ways a non-grammatical input sentence, so as to make it grammatical. It can even use weights on the types of modifications considered so as to choose modifications with the smallest weight.

Your problem is a special case. Existing general CF parsing algorithms (not necessarily as currently implemented) can handle that for you without any modification of the grammar. Instead, to explain it succintly, you can modify the sentence by adding automatically special wildcard symbols between words that can stand either for any part of speech, or for a sequence of parts of speech of arbitrary length, wherever you wish to allow for more words. Then a chart parser can actually parse this input and produce a parse forest that represents all the possible sentences that would fit your sequence of words, with the necessary additions where you allowed it. Actually this parse forest is a grammar of the language specialized so that it generates only grammatical sentences that fit your initial pattern. Any small sentence that you generate with that grammar will be an answer to your problem.

It sounds a bit too easy, but it really is, and it works. It is a very general technique for correcting ill-formed input, and actually subsumes several specialized techniques that have been proposed in the literature.

You can find a description of this technique in a rather old paper: Parsing Incomplete Sentences - B. Lang - Coling 88 (see section 4). It can also be found in the Grune-Jacobs book on parsing techniques in the chapter "Parsing as Intersection". The general idea regarding ill-formed input is also described succintly in a paper on parsing as intersection: "Recognition can be harder than parsing".

The original technical description of the chart parsing technique may seem too mathematical or a bit outdated, and the description by Grune and Jacobs may be simpler to read.

If you want to understand it more simply, think of your initial sequence augmented with wild cards as a finite state automaton that generates all sequences of words that you would consider acceptable if they were grammatical.

For example, with the notation of the paper where ? stands for a single part of speech and * stands for any sequence, the sequence:

The red dog ? absolutely * always

may be read as an automaton with a linear structure, except for a loop (on the state between absolutely and always) that can generate an arbitrary number of parts of speech.

                                             / \
   The     red    dog      ?     absolutely  \ /   always
o ----> o ----> o ----> o ---> o ---------->  o  --------> O

Then chart parsing can be applied to such an automaton to produce a shared forest for all the grammatical sequences in the language of the finite state automaton.

Of course, you may actually put more special symbols than you actually need. This will only result in more candidate sentences.

Applying a chart parser to such an automaton can be done in the same way that chart parsers can be applied to word lattices in speech recognition. A word lattice can also be viewed as a finite state automaton.

Indeed, all this falls into a more general framework that understands parsing as a way of computing the intersection of a phrase structure language (not necessarily Context-Free) and a finite state automaton representing a set of candidate sentences. The result is a parse forest for all the grammatically acceptable sentences that can be generated by the (non necessarily deterministic) finite state automaton.

This represent a basic skeleton for the sentence completion procedure. Then you may have to use other devices to actually choose the words you want to insert in place of the missing parts of speech. But that may depend on your lexicon and semantic issues. It become more an issue of sentence generation, based on the result of an initial parse of what is given to you. You may have to worry about semantics, but syntactic correctness is ensured.

Regarding the use of NLTK and Python for the purpose, I am not sure of the adequacy of it as currently programmed, since I am not a user of NLTK. However, since NLTK contains a general context-free parser, it should be possible to modify it to get the result described above, as general CF parsers all work more or less on the same principles. There may be one subtle point about handling "input loops", which amounts to handling infinite ambiguity, often ignored by general CF parsers.

Your Answer

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

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