Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
Complete the following graph by drawing the 21 edges that join words at Levenshtein distance 1. lake take taken ake like make like ace mike pike ☐make ice mice spike (pace What is the distance (length of shortest path) in this graph between lake and like lake and pace. lake and spike. lake and make □pace space Assign a weight to each edge in the graph above based on the likelihood of making the substitution, addition, or deletion. For substitutions, base the weights on proximity of keys on a keyboard: For example, P is 4 keys away from N; Fis 5 keys away from 0; and D is one key away from E. For additions or deletions use weight 3. spice What is the weighted distance (minimal weight of a path) in this graph between lake and pace. lake and like lake and make lake and spike If lake was mistakenly typed, use Part (d) to decide which of the following 4 words was most likely the intended word. ☐spike

Complete the following graph by drawing the 21 edges that join words at Levenshtein distance 1. lake take taken ake like make like ace mike pike ☐make ice mice spike (pace What is the distance (length of shortest path) in this graph between lake and like lake and pace. lake and spike. lake and make □pace space Assign a weight to each edge in the graph above based on the likelihood of making the substitution, addition, or deletion. For substitutions, base the weights on proximity of keys on a keyboard: For example, P is 4 keys away from N; Fis 5 keys away from 0; and D is one key away from E. For additions or deletions use weight 3. spice What is the weighted distance (minimal weight of a path) in this graph between lake and pace. lake and like lake and make lake and spike If lake was mistakenly typed, use Part (d) to decide which of the following 4 words was most likely the intended word. ☐spike

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question
100%
Written Assignment 3: The Levenshtein Distance x For example, the words spit and spot are a distance of 1 apart; changing spit to spot requires one substitution (i for o). Likewise, spit is distance 1 from pit since the change requires one deletion (the s). The word spite is also distance 1 from spit since it requires one addition (the e). The word soot is distance 2 from spit since two substitutions would be required (i for o and p for o). This situation can be represented using the graph below whose vertices are the words and the edges connect words at distance one. spite A spell checker is a word processing program that makes suggestions when it finds a word not in the dictionary. To determine what words to suggest, it tries to find similar words. One measure of word similarity is the Levenshtein distance, which measures the number of substitutions, additions, or deletions that are required to change one word into another. aid spit aed pit Here is another example. There are several words at distance 1 from the misspelled word "aed": aid, and, led, med. These words are included in the following graph, together with the words mad and let that are at distance 2 from aed. Note that the three words aed, aid, and and only differ by the middle letter. So they are all at distance 1 from each other forming a 'triangle' in the graph. led and spot med soot let mad
Transcribed Image Text:Written Assignment 3: The Levenshtein Distance x For example, the words spit and spot are a distance of 1 apart; changing spit to spot requires one substitution (i for o). Likewise, spit is distance 1 from pit since the change requires one deletion (the s). The word spite is also distance 1 from spit since it requires one addition (the e). The word soot is distance 2 from spit since two substitutions would be required (i for o and p for o). This situation can be represented using the graph below whose vertices are the words and the edges connect words at distance one. spite A spell checker is a word processing program that makes suggestions when it finds a word not in the dictionary. To determine what words to suggest, it tries to find similar words. One measure of word similarity is the Levenshtein distance, which measures the number of substitutions, additions, or deletions that are required to change one word into another. aid spit aed pit Here is another example. There are several words at distance 1 from the misspelled word "aed": aid, and, led, med. These words are included in the following graph, together with the words mad and let that are at distance 2 from aed. Note that the three words aed, aid, and and only differ by the middle letter. So they are all at distance 1 from each other forming a 'triangle' in the graph. led and spot med soot let mad
a. Complete the following graph by drawing the 21 edges that join words at Levenshtein distance 1. lake take taken lake and make ake ☐like make like ace mike pike make ice b. What is the distance (length of shortest path) in this graph between lake and like lake and pace. lake and spike lake and pace. lake and spike mice spike c. Assign a weight to each edge in the graph above based on the likelihood of making the substitution, addition, or deletion. For substitutions, base the weights on proximity of keys on a keyboard: For example, P is 4 keys away from N; F is 5 keys away from O; and D is one key away from E. For additions or deletions use weight 3. □pace pace d. What is the weighted distance (minimal weight of a path) in this graph between lake and like lake and make 53 space spice e. If lake was mistakenly typed, use Part (d) to decide which of the following 4 words was most likely the intended word. ☐spike
Transcribed Image Text:a. Complete the following graph by drawing the 21 edges that join words at Levenshtein distance 1. lake take taken lake and make ake ☐like make like ace mike pike make ice b. What is the distance (length of shortest path) in this graph between lake and like lake and pace. lake and spike lake and pace. lake and spike mice spike c. Assign a weight to each edge in the graph above based on the likelihood of making the substitution, addition, or deletion. For substitutions, base the weights on proximity of keys on a keyboard: For example, P is 4 keys away from N; F is 5 keys away from O; and D is one key away from E. For additions or deletions use weight 3. □pace pace d. What is the weighted distance (minimal weight of a path) in this graph between lake and like lake and make 53 space spice e. If lake was mistakenly typed, use Part (d) to decide which of the following 4 words was most likely the intended word. ☐spike
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 5 steps with 4 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS