Progress: Dynamic programming and the Parser

by Peter Chapman

Dynamic Programming is a method for solving complex problems by breaking them down into simpler sub-problems. A similar concept is “chunking” used to create estimates where you break the problem set down into chunks where you have enough personal experience to make a reasonable estimate for a particular chunk of work.

I applied a similar concept to the parser. I wanted to take certain known words and derive their meaning very early on. For instance, US telephone numbers are in the form (xxx)-xxx-xxxx. English has lots of specific patterns that have a very high likelihood of a particular meaning. These include things like email addresses, URLs, zip codes, file locations, money, times, dates and units. Rather than later have to deal with these after the parser and re-assemble them, I decided to deal with as a pre-processor step.

Hence the sentence: “Peter needs a 10mm wrench by 10:30” has pre-processed the “10mm” as a unit and 10:30 as a time.