algorithm - Proof of correct of the dynamic programming approach to min edit distance -

-

to calculate min edit distance (the minimum amount of insertions, deletions , substitutions required transform 1 word another), dynamic programming solution based on recurrence relation, last character of both string examined. details in https://en.wikipedia.org/wiki/wagner%e2%80%93fischer_algorithm.

the description of algorithm everywhere on internet when comes edit distance, of them asserts correctness without proof. definition of edit distance, can insert, delete or substitute characters in middle, not @ end. how prove recurrence relation holds?

use induction prove recursive algorithms correct

first, said in comment, can view dynamic programming way speed recursion, , easiest way prove recursive algorithm correct induction: show it's correct on small base case(s), , show that, assuming correct problem of size n, correct problem of size n+1. way proof closely mirrors recursive structure.

the usual recursion problem breaks problem "find minimum cost edit string string b" (|a|+1)(|b|+1) subproblems "find minimum cost edit first characters of string first j characters of string b", 0 <= <= |a| , 0 <= j <= |b|.

choosing base cases

usually induction, can pick small number of simple base cases (perhaps one), show can compute correct answers them, , it's obvious how correctness of other cases implied correctness of base cases, because regardless of case start with, there single "chain" of assumptions needs satisfied, , chain must end @ 1 of our base cases. particular problem, show algorithm solves (i, j) subproblem optimally, need first assume solves (i-1, j), (i, j-1) , (i-1, j-1) subproblems optimally (since if of answers subproblems incorrect, compute totally wrong answer (i, j) subproblem). require more complicated induction usual: instead of single "chain" of assumptions need satisfied, have branching "tree" of assumptions, (up to) 3 children @ each point. need pick base cases in such way any (i, j), entire tree of assumptions "stops", i.e., every path in hits base case assumptions satisfied.

to recap: prove our solution (i, j) optimal, must assume have optimal solutions (i-1, j), (i, j-1), , (i-1, j-1); satisfy assumption for, say, (i-1, j) (that is, prove our solution (i-1, j) optimal), need assume have optimal solutions (i-2, j), (i-1, j-1) , (i-2, j-1), etc., etc. how choose base case(s) work? while traversing down tree, i.e., in going proving our solution subproblem (i, j) correct proving our solution 1 of "child" subproblems (i', j') correct, notice that:

  1. at least 1 of i' < or j' < j holds.
  2. we never "skip over" subproblems -- is, never have i-i' >= 2, or j-j' >= 2.

basically, if take single step down tree, @ least 1 of our 2 "subproblem co-ordinates" (i or j) decreases, never more 1. means if keep descending through tree, regardless of particular "children" subproblems pick on way down, must hit subproblem 0 (at least) 1 of co-ordinates -- i.e. (i'', 0) subproblem 0 <= i'' <= |a| or (0, j'') subproblem 0 <= j'' <= |b|. , means if make those subproblems our base cases, can ensure every path in induction tree hits base case assumptions satisfied , can therefore stop.

luckily, these base cases indeed easy compute optimal answers to. consider problem (i, 0): problem asks minimum cost required change first characters of string first 0 characters of string b. best (only!) way delete characters in prefix of a, cost of i. likewise problem (0, j) asks minimum cost required change first 0 characters of first j characters of b: clearly, best way insert j characters in prefix of b, cost of j.

inductive step

all remains inductive step: showing compute answer (i, j) subproblem correctly, under assumption have computed answers (i-1, j), (i, j-1) , (i-1, j-1) subproblems correctly. trick see in every possible way of editing first characters of first j characters of b, there 3 possible things last character in each of these prefixes (that is, i-th character in , j-th character in b):

  • pair a[i] b[j]. either match (cost 0) or not (cost 1), either way, total cost of pairing must cost (either 0 or 1), plus smallest possible cost of editing rest of prefix of (a[1 .. i-1]) rest of prefix of b (b[1 .. j-1]) -- which, assumption, have calculated correctly!
  • delete a[i]. costs 1, total cost of doing must 1 plus smallest possible cost of editing rest of prefix of (a[1 .. i-1]) entire prefix of b (b[1 .. j]) -- which, assumption, have calculated correctly!
  • insert b[j]. costs 1, total cost of doing must 1 plus smallest possible cost of editing entire prefix of (a[1 .. i]) rest of prefix of b (b[1 .. j-1]) -- which, assumption, have calculated correctly!

since 3 things only possible things do, , each of 3 have calculated overall lowest cost of doing thing, overall best thing must best of 3 of them. proves correctly calculate lowest cost needed edit first characters of first j characters of b, any , j -- in particular, it's true = |a| , j = |b|, is, editing complete string complete string b.


Comments

Post a Comment

Popular posts from this blog

java - Run spring boot application error: Cannot instantiate interface org.springframework.context.ApplicationListener -

-
i have spring project , try make use spring boot , run @ embadded tomcat following : https://spring.io/guides/gs/rest-service/ this application //@configuration //@enableaspectjautoproxy @springbootapplication @componentscan(basepackages = "gux.prome") public class application { public static void main(string[] args) { springapplication.run(application.class, args); } } if use maven command: mvn spring-boot:run , project starts fine, need debug , run main method @ intelij, exception occurs: exception in thread "main" java.lang.illegalargumentexception: cannot instantiate interface org.springframework.context.applicationlistener : org.springframework.boot.logging.classpathloggingapplicationlistener @ org.springframework.boot.springapplication.createspringfactoriesinstances(springapplication.java:414) @ org.springframework.boot.springapplication.getspringfactoriesinstances(springapplication.java:394) @ org.springframework.bo...
Read more

reactjs - React router and this.props.children - how to pass state to this.props.children -

-
i'm using react-router first time , don't know how think in yet. here's how i'm loading components in nested routes. entry point .js reactdom.render( <router history={hashhistory} > <route path="/" component={app}> <route path="models" component={content}> </route> </router>, document.getelementbyid('app') ); app.js render: function() { return ( <div> <header /> {this.props.children} </div> ); } so child of app content component sent in. i'm using flux , app.js has state , listens changes, don't know how pass state down this.props.children. before using react-router app.js defines children explicitly, passing state natural don't see how now. using couple of react helper methods can add state, props , whatever else this.props.children render: function() { var children = react.ch...
Read more

Excel VBA "Microsoft Windows Common Controls 6.0 (SP6)" Location Changes -

-
i have excel workbook used generate quotations customers. there main page user inputs data, , there buttons generate various pdfs , send them customer. however, 1 user consistently getting error preventing generating , sending pdfs. i beleive "microsoft windows common controls 6.0 (sp6)". it's installed on users' computers. on mine, location "c:\windows\syswow64\mscomctl.ocx" on others "c:\windows\system32\mscomctl.ocx" the user experiencing issues on 32-bit machine, "mscomctl.ocx" file should in system32. have manually put in there, , pointed common controls reference in vba it. issue seems keep reverting looking in syswow64. since folder doesn't exist, can't find it, , can't produce pdfs. i thought perhaps issue user running older version of office (2007) there users on 2013 , 2016. thought perhaps mixture of 64-bit , 32-bit users. user gets sent workbook other users (as quotation process goes further, gets passed ...
Read more