#question.Write a program that computes the edit distance (also called the Levenshtein distance, for its creator Vladimir
Levenshtein) between two words. The edit distance between two strings is the minimum number of operations that
are needed to transform one string into the other. For this program, an operation is a substitution of a single character,
such as from “brisk” to “brick”. The edit distance between the words “dog” and “cat” is 3, following the chain of
“dot”, “cot”, and “cat” to transform “dog” into “cat”. When you compute the edit distance between two words, each
intermediate word must be an actual valid word. Edit distances are useful in applications that need to determine how
similar two strings are, such as spelling checkers.
Read your input from a dictionary text file. From this file, compute a map from every word to its immediate neighbors,
that is, the words that have an edit distance of 1 from it. Once this map is built, you can walk it to find paths
from one word to another.
A good way to process paths to walk the neighbor map is to use a linked list of words to visit, starting with the
beginning word, such as “dog”. Your algorithm should repeatedly remove the front word of the list and add all of its
neighbors to the end of the list, until the ending word (such as “cat”) is found or until the list becomes empty, which
indicates that no path exists between the two words.

Posted Date: 4/19/2013 4:25:54 AM | Location : Denmark

Ask an Expert

Related Discussions:- Java collection framework., Assignment Help, Ask Question on Java collection framework., Get Answer, Expert's Help, Java collection framework. Discussions

Write discussion on Java collection framework.
Your posts are moderated

Write your message here..

Related Questions

List down the analytical engine''s elements name, List down the Analytical ... List down the Analytical Engine's elements name An analytical engine elements are as follows: Input Memory Processor Output.

How we declaring arrays in java language, How we Declaring Arrays in java l... How we Declaring Arrays in java language? Like all other variables in Java, an array must have a exact type such as byte, int, String or double. Just variables of the appropria

Text Analyser, Hi anybody there Hi anybody there

Develop a supply chain management, Develop a Supply Chain Management Pro... Develop a Supply Chain Management Project Description: Supply Chain Management from HK and China Skills required is Java

Program with fibonacci sequence of first 20 terms, Program 1. Write a J... Program 1. Write a Java program to display the first 20 Fibonacci numbers Program with Fibonacci sequence of first 20 terms Output 2. Write an applet progr

I need social mobile application, Project Description: I'm using a php s... Project Description: I'm using a php script called phpfox on my site its work as social network . So I need is to use this script as CMS for my application. What users wil

Please answer this, Assignment Help >> JAVA Programming Learning Outcomes:... Assignment Help >> JAVA Programming Learning Outcomes: 1. Use different program control statements in a programming language 2. Demonstrate the use of arrays with a programming

Logical operators, Logical Operators Operator ... Logical Operators Operator Functionality E x ample/ Explanation     && Looks at 2 expressions & returns a

Prepare a small android application, Android App Project Description: ... Android App Project Description: I am seeking an experienced individual to prepare a small android application The only difference is that I would like movement to be done

Homography matrix, Open A java applet should appear on your screen. C... Open A java applet should appear on your screen. Click on File, OpenImage and select Asterix. Check Homography box. By clicking on the images you can select points. The c