4

I need an algorithm to detect incorrect answers in memorization of sentences. Confused? Let me show you. I need to repeat the following sentence by memorization:

The quick brown fox jumps over the lazy dog.

My memorized version (this is an example, people) is this:

Quick the brown fox jumped over my lazy fat dog.

If YOU compare the following sentences, you would say that out of 10 possible points (number of words), I would miss 4 points (6/10). First, I switched "quick" and "the" around, misspelled "jumps" as "jumped", misspelled "the" as "my", and added the extra word "fat". Now what I am looking for is a sequence, or algorithm, for a computer to do this. At first I though removing each of the words that was found, regardless of their position, and then taking the higher number of words left on the correct and incorrect side, like this. Below would be left after removing the found words.

___ _____ _____ ___ jumps ____ the ____ ___. (correct side)

_____ __ _____ ___ jumped ____ my ____ fat ___. (incorrect side)

This algorithm would tell me I missed 3 points, since the incorrect side had 3 words left. It missed the swap of "quick" and "the".

If I demanded that each word be in the right place, the following would happen:

The quick _____ ___ jumps ____ the ____ dog.

Quick the _____ ___ jumped ____ my ____ fat dog.

I would have lost 6 points for this, instead of 4. Notice how it does not catch the swap of "the" and "quick", as well as the offset of "dog" just because I added a word, I lost 2 points for that one.

A couple more tests for you, if you do find an algorithm: (my answers)

Brown quick foxes jump over the dog. (miss 5)

The quick and fast fox jumps over my incredibly lazy dog. (miss 4)

Dog lazy the over jumps fox brown quick the. (miss 9, I misplaced all except for one of them as the anchor).

As well, if you think there's a better "grading method" when memorizing sentences, make them known.

  • 5
    You're probably looking for some variation on Hamming Distance or Levenshtein Distance. – Robert Harvey Sep 25 '15 at 17:34
  • 1
    There are a whole bunch of string matching algorihtims on Wikipedia. Which one works best for you is really up to you to define 'best'. Any of them can be modified from 'words' to 'letters' by considering each 'word' a different 'letter' in another alphabet (none of the algorithms are tied to any given alphabet) though some are optimized for certain sized alphabets (the alphabet of 'ACGT' is particularly well studied). – user40980 Sep 25 '15 at 19:23
  • 1
    Also look at diff algorithms. en.m.wikipedia.org/wiki/Diff – Erik Eidt Sep 26 '15 at 4:18
1

This will end up being domain specific. It is likely to be a set of different engines each contributing part of the score.

You can compute weights to "is this misspelled" by Soundex or double metaphone. Alternately, look at Norvig's blog.

You then answer questions like "how close is the word order" (Levingston or Hamming), are unusual words present (meaning "lazy" but not "the"), and so on. Apply a scoring value to the output. For extra credit, see who then uses the underlying knowledge correctly and feed it back into the weighting algorithm.

The weighting must be domain specific. For example, in the Nuclear War domain, you want nuclear launch codes to exactly perfect, targeting lat/long needs the several few digits to be accurate, but the target city name just needs to be understood, e.g., "Saint Pete's" is fine for "St. Petersburg, Russia". The precision needed is what is needed for "success".

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.