Best data structure for representing English verb forms

Question

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?

Answer 1

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.

Answer 2

An map/association of sets/enums?

Each key is the verb form. Base/infinitive can be a special case, outside the map. Each value is a set of what conjugations it represents.

• for an arbitrary form answer the question what conjugations the form represents.

That's a lookup of the key, returns the set of conjugations.

• for an arbitrary conjugation and a form answer the question whether the form represents the given conjugation or not?

That's the same lookup, and a lookup of the conjugation in the resulting set.

What data structure would be efficient, accurate yet unambiguous [...]

Efficient in time or space? Depending on the implementation, a map/hash/assoc and set lookup can be very efficient.

For space, there'll be overhead on every entry, and redundancy in storing similar strings can be further taken out (something like ropes, maybe).

Accurate Yes.

Unambiguous Ambiguity may arise only when introducing data.

This seems like the simple thing to do, but it won't be as efficient in other use cases, such as: - answering what form a verb takes in a particular conjugation (that's a search on possibly all keys and set elements) - answering all forms for a particular time OR person, disregarding the other (t

Answer 3

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.

Answer 4

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.