#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

???, ??? ???

User defined key class in the hashtables aur hashmap, You should override ... You should override the hashCode() and equals() functions from the Object class. The default implementation of the hashcode() and equals(), which are inherited from the java.

State the java programmer efficiency, State the Java Programmer Efficiency ... State the Java Programmer Efficiency Faster Development Building an application in Java takes about 50% less time than in C or C++. So, faster time to market Java is said to

What are the different scopes for java variables, What are the different sc... What are the different scopes for Java variables? The scope of a Java variable is explained by the context in which the variable is declared. Therefore a java variable can have

What is jdbc abstraction and dao module, Using this module we can keep up t... Using this module we can keep up the database code clean and easy, and prevent problems that result from a failure to close database resources. A new layer of meaningful exceptions

Application to upload dicom files from cd to dropbox, Application or websit... Application or website to upload DICOM files from CD to Drop box etc Project Description: I need a website code or application to make patients put a cd or DVD to their disk

Java, Write a program called Power that displays the positive powers of 2. ... Write a program called Power that displays the positive powers of 2. When the user enters the exponent at a prompt, the program displays 2 to that power. The program halts when the

Recursive Division Maze Generation, can you tell me what the code for a 2d ... can you tell me what the code for a 2d random java array using Recursive Division Maze Generation

Program implement class which have main string method, Implement the Money ... Implement the Money class discussed in class. This class should represent a dollar and cents amount with 0-99 cents and the cents being the same sign as the dollars. The class shou

Write code in a java for automaton distributed in class, Write a code in a ... Write a code in a c++/java  for the automaton distributed in the class that accepts keywords(cat,bat,cab). Create an input file along with these words may be two or three copies of