Skip to content

Add category String & Edit Distance Algorithm #29

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
May 23, 2016
Merged

Add category String & Edit Distance Algorithm #29

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 6 additions & 0 deletions algorithm/category.json
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,6 +27,12 @@
"heap" : "Heap Sort"
}
},
"string": {
"name": "String",
"list": {
"edit_distance": "Edit Distance"
}
},
"etc": {
"name": "Uncategorized",
"list": {
Expand Down
18 changes: 18 additions & 0 deletions algorithm/string/edit_distance/desc.json
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,18 @@
{
"Edit-Distance": "Given two strings str1 (length M) and str2 (length N) and below operations that can performed on str1. Find minimum number of edits (operations) required to convert str1 into str2.<br />Insert<br />Remove<br />Replace<br />All of the above operations are of equal cost",
"Applications": [
"Displaing Near-Proximity Words",
"Information Retrieval (eg- Lucene API)",
"Natural Language Processing"
],
"Complexity": {
"time": "worst O(|M|.|N|)",
"space": "worst O(|M|.|N|)"
},
"References": [
"<a href='https://en.wikipedia.org/wiki/Edit_distance'>Wikipedia</a>"
],
"files": {
"dynamic_programming": "Distance from str1 to str2 using Dynamic Programming (2D Array method)"
}
}
40 changes: 40 additions & 0 deletions algorithm/string/edit_distance/dynamic_programming/code.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,40 @@
tracer._pace (200);
tracer._print ('Initialized DP Table');
tracer._print ('Y-Axis (Top to Bottom): ' + str1);
tracer._print ('X-Axis (Left to Right): ' + str2);

var dist = (function editDistance (str1, str2, table) {
//display grid with words
tracer._print ('*** ' + str2.split ('').join (' '));
table.forEach (function (item, index) {
var character = (index === 0) ? '*' : str1 [index-1];
tracer._print (character + '\t' + item);
});

//begin ED execution
for (var i = 1; i < str1.length+1; i++) {
for (var j = 1; j < str2.length+1; j++) {
if (str1 [i-1] === str2 [j-1]) {
tracer._select (i-1, j-1);
table [i] [j] = table [i-1] [j-1];
tracer._notify (i, j);
tracer._deselect (i-1, j-1);
}
else {
tracer._select (i-1, j);
tracer._select (i, j-1);
tracer._select (i-1, j-1);
table [i] [j] = Math.min (table [i-1] [j], table [i] [j-1], table [i-1] [j-1]) + 1;
tracer._notify (i, j);
tracer._deselect (i-1, j);
tracer._deselect (i, j-1);
tracer._deselect (i-1, j-1);
}
}
}

tracer._select (str1.length, str2.length);
return table [str1.length] [str2.length];
}) (str1, str2, table);

tracer._print ('Minimum Edit Distance: ' + dist);
10 changes: 10 additions & 0 deletions algorithm/string/edit_distance/dynamic_programming/data.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,10 @@
var tracer = new Array2DTracer ();
var str1 = 'stack', str2 = 'racket', table = new Array (str1.length + 1);

table [0] = Array.apply (null, {length: str2.length + 1}).map (Number.call, Number);
for (var i = 1; i < str1.length+1; i++) {
table [i] = Array.apply (null, Array (str2.length+1)).map (Number.prototype.valueOf, -1);
table [i] [0] = i
}

tracer._setData (table);