{"id":14583,"date":"2022-05-10T21:55:32","date_gmt":"2022-05-11T01:55:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14583"},"modified":"2026-06-02T14:59:22","modified_gmt":"2026-06-02T18:59:22","slug":"tr-14-a-common-basis-for-similarity-measures-involving-two-strings","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1983\/tr-14-a-common-basis-for-similarity-measures-involving-two-strings\/","title":{"rendered":"TR-14: A Common Basis for Similarity Measures Involving Two Strings"},"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-14: A Common Basis for Similarity Measures Involving Two Strings\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-1983\/\">Technical Report<\/a> <strong>TR-14<\/strong><br>\nJanuary 1983<\/p>\n\n\n\n<h2 id=\"a-common-basis-for-similarity-measures-involving-two-strings\" class=\"wp-block-heading tr_t1\">A Common Basis for Similarity Measures Involving Two Strings<\/h2>\n\n\n\n<p>R.L. Kashyap &amp; B.J. Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Many numerical indices which quantify the similarity and dissimilarity between a pair of strings, X and Y, have been defined in the literature. Some of these include the length of their longest Common subsequence (LLCS(X,Y)), the length of their Shortest common supersequence (LSCSCX,Y)), and their Generalized Levenshtein Distance (GLD(X,V)). Some non-numerical indices relating the strings are the set of their common subsequences, the set of their common supersequences and the set of their shuffles. In this paper, we consider an abstract measure between X and V, written as D(X,V), defined in terms of two abstract operators i and 8 and a binary function d(\u2022,\u2022) whose arguments are symbols of an alphabet A. Depending on the vari\u00adous concrete operators used fort and@ and the specific function used for d(\u00b7,\u00b7), all the quantities discussed above can be seen to be particular cases of D(X,Y). We have presented an algorithm to recursively compute D(X,V), which can serve to be a common scheme to compute all these quanti\u00adties. Many new results are obtained using this abstract formulation, such as an explicit linear relationship between the LLCS and the LSCS between two strings.<\/p>\n\n\n\n<h3 id=\"download\" class=\"wp-block-heading\">Download<\/h3>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-14.pdf\">TR-14.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-14 January 1983 A Common Basis for Similarity Measures Involving Two Strings R.L. Kashyap &amp; B.J. Oommen Abstract Many numerical indices which quantify the similarity and dissimilarity between a pair of strings, X and Y, have been defined in the literature. Some of these include the length of their longest Common [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11785,"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-14583","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\/14583","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=14583"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14583\/revisions"}],"predecessor-version":[{"id":14585,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14583\/revisions\/14585"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11785"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14583"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14583"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}