Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need to come up with a data structure to keep information about English verb forms. In most cases a verb can be in one of 4 forms: base, present participle, past participle and past simple, for example:

  • take
  • taking
  • taken
  • took

It's seemingly easy to define 4 types for each form and be over with it. However there are few exceptions that ruin this simple idea.

  1. Present single third person form, which is in our example would be "takes".
  2. Copular verb "to be" has multiple irregular forms in the present tense: "am", "is", "are" and "was" and "were" in the past tense
  3. Verbs like "may" that don't inflect in the present single third person form: "she may".

What data structure would be efficient, accurate yet unambiguous for representing such information (with exceptional cases) given the following requirements have to be met:

  • for an arbitrary form answer the question what conjugations the form represents
  • for an arbitrary conjugation and a form answer the question whether the form represents the given conjugation or not?
share|improve this question
add comment

3 Answers

You need to consider the uses to which your data will be put. For example, if you want to do real-time deep semantic analysis of English texts or if you are trying to do machine translation of linguistic texts you will probably want to have an entry for each conjugated form that a verb can take in the language(s) of interest.

You can consider the infinitive form of a verb to be the base form and the base form should have links to all variant forms, so from the infinitive you can enumerate and access all the grammatical uses associated with the verb. Similarly, the variant forms should link back to the infinitive form.

Data structures of this type will minimize the computational load required to identify the possible grammatical uses of each verb form that you can encounter in natural language text.

share|improve this answer
    
sounds like you're describing a tree structure with a set of indexes for each type of verb to speed up access. –  omouse Jul 22 '13 at 19:26
add comment

In the case where there are a lot of exceptions to the rules of how your data can be organized, you will have to relate them in a light and shallow way. In this case, you can use a "tag"-like system.

Your objects could store two things: the base form (as a string), as well as a map of "tags." This map would hold an enum value as its key and a word string as its value. The enum would list all the types of forms that are possible.

Using this method, your object is required to have a base form, but can then have either 0 or 1 of each of the other types of forms. If it doesn't have a certain form associated with it, you simply don't include it, and it would be your language's equivalent of null.

share|improve this answer
add comment

You might model the base forms and then add any number of exceptions by coding the conjugation (an enumeration) and the form (a string).

E.g.

typedef struct {
    verb_t *verb;
    char    *base;
    char    *pres_part;
    char    *past_part;
    char    *past_simple;
    EXCEPT  **exception; // NULL-terminated
}

and the exception would be

typedef struct tag_exception {
    conj_t  conjugation;           // Enum: CONJ_3S for third person singular
    char    *form;                 // "is"
}

Then you should model some "rules" for the other cases. For example, say that our "rule" is that third person singular is made by adding a -s. Then not having an exception for take, 3S means that it is takes. A verb such as be would have an exception, is.

To answer the first question, you scan the base forms, scan the exceptions if any, and generate the remaining "rule" forms.

To answer the second question, you basically do the same, except that you check if the form ID matches.

share|improve this answer
add comment

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.