The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
37 views

An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance}$, the spelling checker should suggest $\mathsf{occurence}$, which belongs to the dictionary. Similarity between words such as $\mathsf{occurrence}$ and $\mathsf{occurrance}$ is quantified in terms of $alignment$.

An alignment between two strings $w1$ and $w2$ (over the alphabet $\{ \mathsf{a, b, c, ...., z} \}$) is obtained by inserting hyphens in the two strings such that the modified strings $align$ (i.e.,the modified strings are of equal length, and at each position, either both strings have the same letter or one of the strings has a hyphen).

here are three examples of alignments. The first is between $\mathsf{ocurrance}$ and $\mathsf{occurrence}$ and the second and third are between $\mathsf{ctatg}$ and $\mathsf{ttaagc}$.

(1)

oc-urr-ance

occurre-nce

(2)

ct-at-g-

-tta-agc

(3)

ctat---g-

---ttaagc

A $mismatch$ in an alignment is a position where one of modified strings has  a hyphen and the other does not. There are three mismatches in the first alignment given above, five mismatches in the second, and seven mismatches in the third.

use dynamic programming to give an efficient algorithm that takes two strings $x$ and $y$ (over teh alphabet $\{ \mathsf{a, b, c, ... , z} \}$ as its input, and computes the minimum number of mismatches among all alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y$)?

asked in Others by Veteran (99.8k points) | 37 views

1 Answer

0 votes

let us store element of w1 in the array a[w1] and that of w2 in array b[w2] let C[w1*w2] be our new array where we sore results 

Algorithm  

1$\leq i\leq w1$ 1$\leq j\leq w2$  C[i-1,j-1]=0

c[i][j]=$\left\{\begin{matrix} c[i-1,j-1]& a[i]=b[j], i=j\\ 1+c[i-1,j-1] & a[i]="-",b[j]="-",a[i]!=b[j],i=j\\ c[i-1,j]& i<j\\ 0 & i>j\\ c[i-1,j-1] & otherwise \end{matrix}\right.$ 

answer will be last entry c[w1,w2]

eg let

w1= t-sl-

w2=-es-a

  t - s l -
- 1 1 1 1 1
e 0 2 2 2 2
s 0 0 2 2 2
- 0 0 0 3 3
a 0 0 0 0 4

minimum mismatch is 4 

Time Complexiy is O(w1*w2)

answered by Boss (16.2k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,115 questions
45,622 answers
132,333 comments
49,306 users