Despite its name, many programmers have never heard of
dynamic programming. In all fairness, it is not really programming in that sense of the word, rather it is a mathematical method for dividing problems into smaller subproblems and then combing those parts to form an optimal solution. The "programming" portion of "dynamic programming" probably shares more in common with "television programming," since they both involve using tables to organize data. The technique is taught in advanced computer science classes, so computer scientists and software engineers should be familiar with the technique.
Dynamic programming is a general technique which involves four basic steps: determine the structure of an optimal solution; recursively define values of the optimal solution; compute the optimal solution; and, if you need to know the optimal path in addition to the computed optimal solution value, construct the value formed by the path. The code on this page shows all of these parts, so it may help in understanding the technique.
I have read articles which explain complicated methods for doing
fuzzy string matching that could possibly be replaced by dynamic programming techniques. Dynamic programming certainly brings its own overhead, so it would be interesting to perform empirical analysis on both techniques and compare the results. Since I presently lack the time to perform such an analysis, I decided to share a small, rough example that I created in JavaScript for doing string matching with a dynamic programming algorithm. The code below is essentially a simplified implementation of
A Dynamic Programming Algorithm for Name Matching, which was published in the IEEE by Top, Dowla, and Gansemer.
Here is one example of how to use the code. This example uses searchValueA and searchValueB to generate an html table which shows how the dynamic programming matrix should look.
nm = new nameMatch(searchValueA, true, '#html_div_result');
nm.score(searchValueB);
And, here is the JavaScript class/object (continued on the next page):
/**
* A Dynamic Programming Algorithm for Name Matching
* Top, P.; Dowla, F.; Gansemer, J.;
* Sch. of Electr. & Comput. Eng., Purdue Univ., West Lafayette, IN
*
* Variation in JavaScript
* Copyright © 2011, Christopher Stoll
*
* @constructor
* @param {String} [pNameSource=''] The source name, the name of interest
* @param {Boolean} [pDebug=false] The instance is in debugging mode
* @param {String} [pDebugOutputArea=''] Where to put debuging output
*/
function nameMatch(pNameSource, pDebug, pDebugOutputArea){
var tNameSource = pNameSource || '';
if(tNameSource){
if(tNameSource.indexOf(',') > 0){
var tIndex = tNameSource.indexOf(','),
tFirst = tNameSource.slice(tIndex+1),
tLast = tNameSource.slice(0, tIndex);
tNameSource = tFirst + ' ' + tLast;
}
tNameSource = tNameSource.toLowerCase();
tNameSource = tNameSource.replace(/[.'"]/ig, ' ');
tNameSource = tNameSource.replace(/\s{2,}/g, ' ');
}
// debug variables
this.DEBUG = pDebug || false;
this.DEBUG_AREA = pDebugOutputArea;
// y axis in matrix, the name in question
this.nameSource = tNameSource;
this.nameSourceLength = this.nameSource.length + 1;
this.nameSourceScore = 0;
this._reset();
}
