Find Levenshtein distance with AS3

From Wikipedia: The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.

In real world, one of the most common uses of this distance is the suggestion Google throws when it thinks you mispelled your search.

When you search for an uncommon word that is similar to a popular search, Google suggests the word it supposes you were looking for.

This is probably made with Levenshtein distance. Some languages such as PHP have their native function to determine the distance between two string, but Actionscript 3 does not have any function to accomplish this task.

That’s why I am showing you how to do it

The Levenshtein algorithm

Giving two string made by respectively n and m characters, we create a m*n matrix this way:

This is the starting matrix, with all cells close to the strings set at their n-th character and the remaining ones at zero.

Then, we must fill the matrix from the upper left to the lower right corner starting from cell 1,1 (second row, second column) in this way:

I fill the x,y cell, with the minimum value among

* x-1,y cell value + 1
* x,y-1 cell value + 1
* x-1,y-1 cell value + d

where d = 0 if the xth character of the second string is the same as the yth character of the first string, and 1 if such characters are different.

So in our case the first line of the matrix will be filled this way:

The red value is determined by the minimum value among 2 (leftmost cell value plus one), 2 (upper cell value plus one) and 1 (upper left diagonal cell value plus one because T and F aren’t the same character)

The green value is determined by the minimum value among 2 (leftmost cell value plus one), 2 (upper cell value plus one) and 2 (upper left diagonal cell value plus one because O and F aren’t the same character)

Apply this principle to the entire matrix and you will get

The red number at the lower right of the matrix is the distance.

Here it is translated into AS3:

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.text.TextFieldType;
	import flash.text.TextFormat;
	import flash.events.Event;
	public class levenshtein extends Sprite {
		var from:TextField=new TextField();
		var to:TextField=new TextField();
		var lev:TextField=new TextField();
		var text_format:TextFormat = new TextFormat();
		public function levenshtein():void {
			text_format.color=0x000000;
			text_format.size=24;
			addChild(from);
			with (from) {
				type=TextFieldType.INPUT;
				x=20;
				y=20;
				width=460;
				height=30;
				text="from";
				border=true;
				setTextFormat(text_format);
				addEventListener(Event.CHANGE,on_change);
			}
			addChild(to);
			with (to) {
				type=TextFieldType.INPUT;
				x=20;
				y=70;
				width=460;
				height=30;
				text="to";
				border=true;
				setTextFormat(text_format);
				addEventListener(Event.CHANGE,on_change);
			}
			addChild(lev);
			with (lev) {
				x=20;
				y=120;
				width=460;
				height=30;
				text="distance = "+distance(from.text,to.text);
				setTextFormat(text_format);
			}
		}
		public function on_change(e:Event):void {
			lev.text="distance = "+distance(from.text,to.text);
			lev.setTextFormat(text_format);
		}
		public function distance(string_1:String, string_2:String):int {
			var matrix:Array=new Array();
			var dist:int;
			for (var i:int=0; i<=string_1.length; i++) {
				matrix[i]=new Array();
				for (var j:int=0; j<=string_2.length; j++) {
					if (i!=0) {
						matrix[i].push(0);
					} else {
						matrix[i].push(j);
					}
				}
				matrix[i][0]=i;
			}
			for (i=1; i<=string_1.length; i++) {
				for (j=1; j<=string_2.length; j++) {
					if (string_1.charAt(i-1)==string_2.charAt(j-1)) {
						dist=0;
					} else {
						dist=1;
					}
					matrix[i][j]=Math.min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+dist);
				}
			}
			return matrix[string_1.length][string_2.length];
		}
	}
}

And this is the result:

Type anything you want in both text areas and see the Levenshtein distance in real time

Download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

214 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers