GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Add category String & Edit Distance Algorithm · smartoarif/AlgorithmVisualizer@548c2fd

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • string/edit_distance
      • desc.json
      • dynamic_programming
        • code.js
        • data.js
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,12 @@
2727
"heap" : "Heap Sort"
2828
}
2929
},
30+
"string": {
31+
"name": "String",
32+
"list": {
33+
"edit_distance": "Edit Distance"
34+
}
35+
},
3036
"etc": {
3137
"name": "Uncategorized",
3238
"list": {
Collapse file

‎algorithm/string/edit_distance/desc.json‎

Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff 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+
}
Collapse file

‎algorithm/string/edit_distance/dynamic_programming/code.js‎

Copy file name to clipboard
+40Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff 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);
Collapse file

‎algorithm/string/edit_distance/dynamic_programming/data.js‎

Copy file name to clipboard
+10Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff 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

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.