Alan.B (1/10/2013)

---

I agree that I should have used a tally table. I've been writing CTE's for counting for awhile and can do so while sleeping. I still fumble around with the tally table and, in this case was in a hury to post my code. I just updated my query to include the tally table as you showed above: 303 reads is now 146 reads.

Sean Lange (1/10/2013)

---

You might want to take a look at this article.

http://www.sqlservercentral.com/articles/T-SQL/74118/

-- strings to compare
DECLARE	@s1 varchar(8000)='diner',
		@s2 varchar(8000)='dinerr';

DECLARE @ld int=ABS(LEN(@s1)-LEN(@s2));

IF ((@s1=@s2) OR ((ISNULL(LEN(@s1)*LEN(@s2),0)=0))) BEGIN GOTO LD END;

	DECLARE	@minlen int=CASE WHEN LEN(@s1)>LEN(@s2) THEN LEN(@s2) ELSE LEN(@s1) END;

	;WITH 
	nums(n) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) FROM [master].dbo.spt_values Tally),
	matrix  AS (SELECT SUBSTRING(@s1,n,1) s1, SUBSTRING(@s2,n,1) s2 FROM nums WHERE n<=@minlen)
	SELECT @ld+=COUNT(*) FROM matrix WHERE s1<>s2;
LD:
SELECT @ld AS LD;

Alan.B
(just for fun because it's something I've never seen done

Alan.B (1/10/2013)

---

[quote]This morning before work for example, after a lot of effort, I finally figured out how to get the Levenshtein Edit Distance between 2 strings without a loop (just for fun because it's something I've never seen done).

Jeff Moden (1/10/2013)

---

Heh... if that's how you warm up for the day, then you've got me beat by a mile.

You can just bet I'm going to do a deep dive on your rendition of this famous problem... especially since you did it with a Tally Table. Thanks for doing it and thanks for posting it.

dwain.c
I for one have never heard of this famous "Levenshtein Edit Distance" problem, but you can rest assured that now I'm going to have to take a look at it as well!

Alan.B
I came up with this:

-- strings to compare
DECLARE	@s1 varchar(8000)='diner',
		@s2 varchar(8000)='dinerr';

DECLARE @ld int=ABS(LEN(@s1)-LEN(@s2));

IF ((@s1=@s2) OR ((ISNULL(LEN(@s1)*LEN(@s2),0)=0))) BEGIN GOTO LD END;

	DECLARE	@minlen int=CASE WHEN LEN(@s1)>LEN(@s2) THEN LEN(@s2) ELSE LEN(@s1) END;

	;WITH 
	nums(n) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) FROM [master].dbo.spt_values Tally),
	matrix  AS (SELECT SUBSTRING(@s1,n,1) s1, SUBSTRING(@s2,n,1) s2 FROM nums WHERE n<=@minlen)
	SELECT @ld+=COUNT(*) FROM matrix WHERE s1<>s2;
LD:
SELECT @ld AS LD;

Greg Snidow (1/11/2013)

---

I guess you're really busy Dwain (is that the Jeopardy theme in the background?), since you've not come back with anything yet.

dwain.c
Looks like you may have beaten me to it.

Greg Snidow (1/11/2013)

---

Alan, I had never heard of this either. If the Wiki description Dwain posted is to be trusted, I think you might want to re-visit this. For example, for the two strings you provided, 'diner' and 'dinerr', the output is 1. This makes sense, because all you have to do is delete the second 'r' in string 2 (or the first 'r' for that matter), and you end up with the same two strings. Next, let's say I change the 'd' in string 1 to 'a'. The code returns 2, which I think is correct, since all I have to do is substitute 'a' in string 1 to 'd', then delete one of the 'r' in string 2, and I have two of the same string. Now, consider this: let's say I insert the 'a' in string 1, but leave the rest intact, leaving me with 'adiner' for string 1, and I leave string 2 as 'dinerr'. The code returns a value of 5. This does not make sense, again, if Wiki is to be trusted, as it states the allowable actions are single character insertions, deletions, and substitutions. So, in order to make 'adiner' = 'dinerr', I only need two actions: delete the 'a' in 'adiner', and delete one of the 'r' in 'dinerr'. Does that make sense, or am I missing something? (the latter is entirely possible.) (maybe even likely).