Commit dc6901c
committed
Merge pull request algorithm-visualizer#29 from duaraghav8/master
Add category String & Edit Distance Algorithm4 files changed
Lines changed: 74 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -27,6 +27,12 @@ | |||
| 27 | 27 | "heap" : "Heap Sort" | |
| 28 | 28 | } | |
| 29 | 29 | }, | |
| 30 | + "string": { | ||
| 31 | + "name": "String", | ||
| 32 | + "list": { | ||
| 33 | + "edit_distance": "Edit Distance" | ||
| 34 | + } | ||
| 35 | + }, | ||
| 30 | 36 | "etc": { | |
| 31 | 37 | "name": "Uncategorized", | |
| 32 | 38 | "list": { | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,18 @@ | |||
| 1 | + { | ||
| 2 | + "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", | ||
| 3 | + "Applications": [ | ||
| 4 | + "Displaing Near-Proximity Words", | ||
| 5 | + "Information Retrieval (eg- Lucene API)", | ||
| 6 | + "Natural Language Processing" | ||
| 7 | + ], | ||
| 8 | + "Complexity": { | ||
| 9 | + "time": "worst O(|M|.|N|)", | ||
| 10 | + "space": "worst O(|M|.|N|)" | ||
| 11 | + }, | ||
| 12 | + "References": [ | ||
| 13 | + "<a href='https://en.wikipedia.org/wiki/Edit_distance'>Wikipedia</a>" | ||
| 14 | + ], | ||
| 15 | + "files": { | ||
| 16 | + "dynamic_programming": "Distance from str1 to str2 using Dynamic Programming (2D Array method)" | ||
| 17 | + } | ||
| 18 | + } | ||
Lines changed: 40 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,40 @@ | |||
| 1 | + tracer._pace (200); | ||
| 2 | + tracer._print ('Initialized DP Table'); | ||
| 3 | + tracer._print ('Y-Axis (Top to Bottom): ' + str1); | ||
| 4 | + tracer._print ('X-Axis (Left to Right): ' + str2); | ||
| 5 | + | ||
| 6 | + var dist = (function editDistance (str1, str2, table) { | ||
| 7 | + //display grid with words | ||
| 8 | + tracer._print ('*** ' + str2.split ('').join (' ')); | ||
| 9 | + table.forEach (function (item, index) { | ||
| 10 | + var character = (index === 0) ? '*' : str1 [index-1]; | ||
| 11 | + tracer._print (character + '\t' + item); | ||
| 12 | + }); | ||
| 13 | + | ||
| 14 | + //begin ED execution | ||
| 15 | + for (var i = 1; i < str1.length+1; i++) { | ||
| 16 | + for (var j = 1; j < str2.length+1; j++) { | ||
| 17 | + if (str1 [i-1] === str2 [j-1]) { | ||
| 18 | + tracer._select (i-1, j-1); | ||
| 19 | + table [i] [j] = table [i-1] [j-1]; | ||
| 20 | + tracer._notify (i, j); | ||
| 21 | + tracer._deselect (i-1, j-1); | ||
| 22 | + } | ||
| 23 | + else { | ||
| 24 | + tracer._select (i-1, j); | ||
| 25 | + tracer._select (i, j-1); | ||
| 26 | + tracer._select (i-1, j-1); | ||
| 27 | + table [i] [j] = Math.min (table [i-1] [j], table [i] [j-1], table [i-1] [j-1]) + 1; | ||
| 28 | + tracer._notify (i, j); | ||
| 29 | + tracer._deselect (i-1, j); | ||
| 30 | + tracer._deselect (i, j-1); | ||
| 31 | + tracer._deselect (i-1, j-1); | ||
| 32 | + } | ||
| 33 | + } | ||
| 34 | + } | ||
| 35 | + | ||
| 36 | + tracer._select (str1.length, str2.length); | ||
| 37 | + return table [str1.length] [str2.length]; | ||
| 38 | + }) (str1, str2, table); | ||
| 39 | + | ||
| 40 | + tracer._print ('Minimum Edit Distance: ' + dist); | ||
Lines changed: 10 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,10 @@ | |||
| 1 | + var tracer = new Array2DTracer (); | ||
| 2 | + var str1 = 'stack', str2 = 'racket', table = new Array (str1.length + 1); | ||
| 3 | + | ||
| 4 | + table [0] = Array.apply (null, {length: str2.length + 1}).map (Number.call, Number); | ||
| 5 | + for (var i = 1; i < str1.length+1; i++) { | ||
| 6 | + table [i] = Array.apply (null, Array (str2.length+1)).map (Number.prototype.valueOf, -1); | ||
| 7 | + table [i] [0] = i | ||
| 8 | + } | ||
| 9 | + | ||
| 10 | + tracer._setData (table); | ||
0 commit comments