{"id":12607,"date":"2021-11-14T19:52:40","date_gmt":"2021-11-15T00:52:40","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12607"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-95-recognition-of-noisy-subsequences-using-constrained-edit-distances","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1986\/tr-95-recognition-of-noisy-subsequences-using-constrained-edit-distances\/","title":{"rendered":"TR-95: Recognition of Noisy Subsequences Using Constrained Edit Distances"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-95: Recognition of Noisy Subsequences Using Constrained Edit Distances\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1986\/\">Technical Report<\/a> <strong>TR-95<\/strong><br>\nJune 1986<\/p>\n\n\n\n<h2 id=\"recognition-of-noisy-subsequences-using-constrained-edit-distances\" class=\"wp-block-heading tr_t1\">Recognition of Noisy Subsequences Using Constrained Edit Distances<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">B. John Oommen<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>Let X be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X . We consider the problem of estimating X by processing Y which is a noisy version of U. We do this by defining the constrained edit distance between XE H and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit 9istance has been presented. Although in general the algorithm has a cubic time complexity, within the framework of our solution the algorithm possesses a quadratic time complexity. Recognition using the constrained edit distance as a criterion demonstrates a remarkable accuracy. Experimental results which involve strings of lengths between 40 and 80 and which contain an average of 26.547 errors per string demonstrates that the scheme has about 99.5% accuracy.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-095.pdf\">TR-095.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-95 June 1986 Recognition of Noisy Subsequences Using Constrained Edit Distances B. John Oommen Abstract Let X be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X . We consider the problem of estimating X by processing Y which is a noisy version of [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11825,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-12607","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12607","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12607"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12607\/revisions"}],"predecessor-version":[{"id":12608,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12607\/revisions\/12608"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11825"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12607"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}