{"id":7872,"date":"2018-04-27T23:17:34","date_gmt":"2018-04-27T23:17:34","guid":{"rendered":"http:\/\/fx2.com.uy\/?p=7872"},"modified":"2019-12-06T15:25:25","modified_gmt":"2019-12-06T18:25:25","slug":"distancia_strings_t_sql","status":"publish","type":"post","link":"https:\/\/fx2.com.uy\/es\/blog\/distancia_strings_t_sql\/","title":{"rendered":"Comparar (distancia) de dos palabras con T-SQL."},"content":{"rendered":"<h4><strong>Comparar (distancia) de dos palabras con T-SQL.<\/strong><\/h4>\n<p>Post: By Marcos Ezquerra, CEO de <a href=\"http:\/\/fx2.com.uy\">Fx2<\/a><\/p>\n<p>Desde hace alg\u00fan tiempo se nos ha vuelto bastante necesario comparar que tan cercanos son dos strings (textos o cadenas de caracteres).<\/p>\n<p>En algunos casos es bastante simple, por ej. MARCOS y MARCO se parecen mucho, solo una letra de diferencia. El problema es mas complejo cuando comparamos MARCOS vs MACROS, son las mismas letras, pero dos de ellas cambiadas de lugar.<\/p>\n<p>En realidad, lo que se necesita resolver es que tan cercanas son dos palabras. El caso concreto es la comparaci\u00f3n de matriculas para el producto <em><strong><a href=\"http:\/\/viewparking.net\/\">ViewParking<\/a><\/strong><\/em>.<\/p>\n<ul>\n<li>Distancia\u00a0 (\u201cMARCOS\u201d , \u201cMARCOS\u201d) = 0<\/li>\n<li>Distancia\u00a0 (\u201cMARCOS\u201d , \u201cMACROS\u201d) = 2<\/li>\n<li>Distancia (\u201cNCP1940\u201d , \u201cNCB1940\u201d) = 1<\/li>\n<li>Distancia (\u201cAAJ779\u201d , \u201cAAJ7792\u201d) = 1<\/li>\n<li>Distancia (\u201cAAR8486\u201d , \u201cAAR886\u201d) = 1<\/li>\n<\/ul>\n<p>En <strong>T-SQL<\/strong> exsite la funci\u00f3n <a href=\"https:\/\/docs.microsoft.com\/en-us\/sql\/t-sql\/functions\/soundex-transact-sql?view=sql-server-2017\">SOUNDEX<\/a>, que ayuda a definir que tan similares suenan dos palabras. Si bien es un modelo de aproximaci\u00f3n no es una soluci\u00f3n buena cuando se trata de cadenas de caracteres alfanum\u00e9ricos.<\/p>\n<p>Lo que se quiere medir es: \u201cmedir la distancia de una cadena de caracteres en cuantos caracteres necesitamos mover o adicionar para que ambas cadenas sean iguales&#8221;.<\/p>\n<p>En el CLR estas funciones est\u00e1n provistas por terceros, pero en T-SQL esto no es tan sencillo.<\/p>\n<p>Un algoritmo que permite definir una medida de distancia es el \u201c<a href=\"https:\/\/en.wikipedia.org\/wiki\/Levenshtein_distance\">Algoritmo de Levenshtein<\/a>\u201d o \u201cDistancia de Levenshtein\u201d<\/p>\n<p>Desarrollado por Vladimir Levenshtein en 1965, este algoritmo, que algunos vimos durante el pasaje por la Universidad, permite medir la diferencia de edici\u00f3n o distancia entre dos palabras.<\/p>\n<p>Una versi\u00f3n m\u00e1s elaborada es la del algoritmo <a href=\"https:\/\/en.wikipedia.org\/wiki\/Damerau%E2%80%93Levenshtein_distance\">Damerau-Levenshtein<\/a> que tiene consideraciones en cuanto a dos caracteres en posiciones invertidas, por ejemplo.<\/p>\n<p>Comparto una implementaci\u00f3n de Levenshtein, que entre otras cosas fue revisada y publicada por el blog de RedGate.<\/p>\n<p><strong>Importante: en esta versi\u00f3n he restringido he restringido el largo del string (cadena) para mejorar el rendimiento, en la versi\u00f3n original soporte NVARCHAR (MAX), pero es bastante m\u00e1s lenta.<\/strong><\/p>\n<hr \/>\n<p>CREATE function LEVENSHTEIN ( @SourceString nvarchar(100), @TargetString nvarchar(100) )<br \/>\n&#8211;Returns the Levenshtein Distance between @SourceString string and @TargetString<br \/>\n&#8211;Translated to TSQL by Joseph Gama<br \/>\n&#8211;Updated slightly by Phil Factor<br \/>\nreturns int<br \/>\nas<br \/>\nBEGIN<br \/>\nDECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int,<br \/>\n@ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int,<br \/>\n@Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells int<br \/>\n&#8212; Step 1: Set n to be the length of s. Set m to be the length of t.<br \/>\n&#8212; If n = 0, return m and exit.<br \/>\n&#8212; If m = 0, return n and exit.<br \/>\n&#8212; Construct a matrix containing 0..m rows and 0..n columns.<br \/>\nif @SourceString is null or @TargetString is null return null<br \/>\nSelect @SourceStringLength=LEN(@SourceString),<br \/>\n@TargetStringLength=LEN(@TargetString),<br \/>\n@Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1))<br \/>\nIf @SourceStringLength = 0 return @TargetStringLength<br \/>\nIf @TargetStringLength = 0 return @SourceStringLength<br \/>\nif (@TargetStringLength+1)*(@SourceStringLength+1)&gt; 4000 return -1<br \/>\n&#8211;Step 2: Initialize the first row to 0..n.<br \/>\n&#8212; Initialize the first column to 0..m.<br \/>\nSET @ii=0<br \/>\nWHILE @ii&lt;=@SourceStringLength<br \/>\nBEGIN<br \/>\nSET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))&#8211;d(i, 0) = i<br \/>\nSET @ii=@ii+1<br \/>\nEND<br \/>\nSET @ii=0<br \/>\nWHILE @ii&lt;=@TargetStringLength<br \/>\nBEGIN<br \/>\nSET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))&#8211;d(0, j) = j<br \/>\nSET @ii=@ii+1<br \/>\nEND<br \/>\n&#8211;Step 3 Examine each character of s (i from 1 to n).<br \/>\nSET @ii=1<br \/>\nWHILE @ii&lt;=@SourceStringLength<br \/>\nBEGIN<\/p>\n<p>&#8211;Step 4 Examine each character of t (j from 1 to m).<br \/>\nSET @jj=1<br \/>\nWHILE @jj&lt;=@TargetStringLength<br \/>\nBEGIN<br \/>\n&#8211;Step 5 and 6<br \/>\nSelect<br \/>\n&#8211;Set cell d[i,j] of the matrix equal to the minimum of:<br \/>\n&#8211;a. The cell immediately above plus 1: d[i-1,j] + 1.<br \/>\n&#8211;b. The cell immediately to the left plus 1: d[i,j-1] + 1.<br \/>\n&#8211;c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost<br \/>\n@Above=unicode(substring(@Matrix,@jj*(@SourceStringLength+1)+@ii-1+1,1))+1,<br \/>\n@ToTheLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1,1))+1,<br \/>\n@AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1))<br \/>\n+ case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1))<br \/>\nthen 0 else 1 end&#8211;the cost<br \/>\n&#8212; If s[i] equals t[j], the cost is 0.<br \/>\n&#8212; If s[i] doesn&#8217;t equal t[j], the cost is 1.<br \/>\n&#8212; now calculate the minimum value of the three<br \/>\nif (@Above &lt; @ToTheLeft) AND (@Above &lt; @AboveAndToLeft)<br \/>\nselect @MinimumValueOfCells=@Above<br \/>\nelse if (@ToTheLeft &lt; @Above) AND (@ToTheLeft &lt; @AboveAndToLeft)<br \/>\nselect @MinimumValueOfCells=@ToTheLeft<br \/>\nelse<br \/>\nselect @MinimumValueOfCells=@AboveAndToLeft<br \/>\nSelect @Matrix=STUFF(@Matrix,<br \/>\n@jj*(@SourceStringLength+1)+@ii+1,1,<br \/>\nnchar(@MinimumValueOfCells)),<br \/>\n@jj=@jj+1<br \/>\nEND<br \/>\nSET @ii=@ii+1<br \/>\nEND<br \/>\n&#8211;Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m]<br \/>\nreturn unicode(substring(<br \/>\n@Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1<br \/>\n))<br \/>\nEND<br \/>\ngo<\/p>\n<hr \/>\n<p>&nbsp;\t\t<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Comparar (distancia) de dos palabras con T-SQL. Post: By Marcos Ezquerra, CEO de Fx2 Desde hace alg\u00fan tiempo se nos ha vuelto bastante necesario comparar que tan cercanos son dos strings (textos o cadenas de caracteres). En algunos casos es bastante simple, por ej. MARCOS y MARCO se parecen mucho, solo una letra de diferencia. [&hellip;]<\/p>\n","protected":false},"author":4,"featured_media":7878,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[96],"tags":[157,97],"_links":{"self":[{"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/posts\/7872"}],"collection":[{"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/comments?post=7872"}],"version-history":[{"count":1,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/posts\/7872\/revisions"}],"predecessor-version":[{"id":13925,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/posts\/7872\/revisions\/13925"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/media\/7878"}],"wp:attachment":[{"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/media?parent=7872"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/categories?post=7872"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fx2.com.uy\/es\/wp-json\/wp\/v2\/tags?post=7872"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}