I am curious if there is an automated way to detect if a given string, representing a sentence, is an 'incomplete' sentence. By this I mean that either the text is not grammatically correct, or is missing words, or doesn't make much sense.

Previous research shows how to fill in missing tokens into a text that is incomplete, which is interesting, but I am looking to just detect if what is given as input is a complete sentence or not.

I am sure that there are many edge cases with something like this, but I am just looking for either state of the art implementations or ideas on how to do this manually, with nltk, opennlp or the stanford tools. Thanks in advance for any thoughts or advice!

  • Uh, you say it is known how to fill in missing tokens to make an incomplete sentence complete, so if you want to tell whether a sentence is complete, why don't you just check to see if any tokens must be added to make it complete? If so, it was incomplete. – Greg Lee Feb 11 '15 at 20:45
  • Parse the sentence with any rule-based parser. If it fails, the sentence is ill-formed (with respect to the used grammar). The sentence is incomplete (that is, missing "something") if an obligatory valency slot is empty. – Atamiri Feb 11 '15 at 21:28
  • @GregLee Thanks for the suggestion. What I was referring to was something like the answer on this question: linguistics.stackexchange.com/questions/6519/…. Initially, it seemed like you needed to know where the missing tokens would be; I figured even a correct sentence could potentially have words added and keep it correct. Anyway, I should spend sometime reading the paper referenced. – mrquintopolous Feb 12 '15 at 3:49
  • @Atamiri: Do you have any recommendations for rule-based parsers that work well in our experience? – mrquintopolous Feb 12 '15 at 3:54
  • It depends on what you want to parse. LFG is a good choice in most cases. – Atamiri Feb 12 '15 at 8:04

The way to do it is to have an editing automaton, which is actually a GSM (Generalized sequentil machine) that can do modifications on the string. Each modification can have an associated cost. You can include it in the parsing process, using a chart parser, to get parses up to some modification, each with a weight accounting for the number and types of modification. This will slow down the parser, but it does not change its complexity, because the editing GSM is a finite state machine, an thus does not change the language class.

When you get a parse with weight 0, it means that the input string could be parsed without any editing.

This is very briefly addressed in this answer on another SE site.

  • See also this answer to the question Natural Language Parser that can handle syntactic and lexical errors and this other answer to the question Computing the closest match of an automaton and a string. You can also search for "levenshtein distance". – babou Feb 14 '15 at 8:58
  • Thank you for all the lists. I will review all the links you sent me, but it sounds like a good approach. Do you have any suggestions for a GSM that I can use to play with some examples? – mrquintopolous Feb 16 '15 at 18:17
  • @mrquintopolous I have no idea what is ready-made on the web, if any. A good way to start is to use a simple GSM that modifies its input token string by inserting an arbitrary token anywhere, non-deterministically, between any two tokens of the input string. Whenever a token is inserted, you increase the weight of the corresponding parses by one. To keep the parsing cost down, you can ignore any parse that starts exceeding a given weight (i.e. a given number of corrections). This will work only for missing tokens. But the same technique can deal with many other types of ill-formedness. – babou Feb 16 '15 at 22:11
  • I will be working on this in the next few weeks, so hopefully I will be able to try out everyone's suggestions then. For now, I'll give you the answer :) – mrquintopolous Feb 20 '15 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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