5

I have a requirement to provide a suggested match between data in two database tables. The basic requirement is; - A "match" should be suggested for the highest number of matched words (irrespective of order) between the two columns in question.

For example, given the data;

   Table A                           Table B
1,'What other text in here'      5,'Other text in here'
2,'What am I doing here'         6,'I am doing what here'
3,'I need to find another job'   7,'Purple unicorns'
4,'Other text in here'           8,'What are you doing in here'

Ideally, my desired matches would look as follows;
1 -> 8   (3 words matched)
2 -> 6   (5 words matched)
3 -> Nothing
4 -> 5   (4 words matched)

I've found word count functions that look promising, but I can't think of how to use it in a SQL statement, that will give me my desired match. Also, the linked function isn't quite what I need as it uses charindex which I think searches for a word within a word (ie. 'in' will match 'bin').

Can anyone help me out with this??

Thanks.

Mr Moose
  • 5,946
  • 7
  • 34
  • 69
  • 3 matches 6. Both have the word "I". And 1 matches 5 better than 8. They share 4 words in common. – Martin Smith Mar 31 '11 at 15:08
  • You are right, but I forgot to mention that there should be no duplicates in the matches. Once a given row is matched, it can't be matched again. You are right about 5 matching 8 also, but as I just commented on your answer, it ideally should take into consideration the percentage of overall words that matched also. – Mr Moose Mar 31 '11 at 15:17

1 Answers1

5

I've used sys.dm_fts_parser below to split the sentences into words. There are plenty of TSQL split functions around if you are not on SQL Server 2008 or find this isn't suitable for some reason.

The requirement that each A.id can only be paired with a B.id that hadn't been used previously and vice-versa isn't one I could think of an efficient set based solution for.

;WITH A(Id, sentence) As
(
  SELECT 1,'What other text in here'    UNION ALL
  SELECT 2,'What am I doing here'       UNION ALL 
  SELECT 3,'I need to find another job' UNION ALL 
  SELECT 4,'Other text in here'         
),
B(Id, sentence) As
(
 SELECT  5,'Other text in here'          UNION ALL
 SELECT  6,'I am doing what here'        UNION ALL
 SELECT  7,'Purple unicorns'             UNION ALL
 SELECT  8,'What are you doing in here'
),  A_Split
     AS (SELECT Id AS A_Id,
                display_term,
                COUNT(*) OVER (PARTITION BY Id) AS A_Cnt
         FROM   A
                CROSS APPLY 
                   sys.dm_fts_parser('"' + REPLACE(sentence, '"', '""')+'"',1033, 0,0)),

     B_Split
     AS (SELECT Id AS B_Id,
                display_term,
                COUNT(*) OVER (PARTITION BY Id) AS B_Cnt
         FROM   B
                CROSS APPLY 
                   sys.dm_fts_parser('"' + REPLACE(sentence, '"', '""')+'"',1033, 0,0)),
     Joined
     As (SELECT A_Id,
                B_Id,
                B_Cnt,
                Cnt = COUNT(*),
                CAST(COUNT(*) as FLOAT)/B_Cnt AS PctMatchBToA,
                CAST(COUNT(*) as FLOAT)/A_Cnt AS PctMatchAToB
         from   A_Split A
                JOIN B_Split B
                  ON A.display_term = B.display_term
         GROUP  BY A_Id,
                   B_Id,
                   B_Cnt,
                   A_Cnt)
SELECT IDENTITY(int, 1, 1) as id, *
INTO   #IntermediateResults
FROM   Joined
ORDER  BY PctMatchBToA DESC,
          PctMatchAToB DESC

DECLARE @A_Id INT,
        @B_Id INT,
        @Cnt  INT

DECLARE @Results TABLE (
  A_Id INT,
  B_Id INT,
  Cnt  INT)

SELECT TOP(1) @A_Id = A_Id,
              @B_Id = B_Id,
              @Cnt = Cnt
FROM   #IntermediateResults
ORDER  BY id

WHILE ( @@ROWCOUNT > 0 )
  BEGIN

      INSERT INTO @Results
      SELECT @A_Id,
             @B_Id,
             @Cnt

      DELETE FROM #IntermediateResults
      WHERE  A_Id = @A_Id
              OR B_Id = @B_Id

      SELECT TOP(1) @A_Id = A_Id,
                    @B_Id = B_Id,
                    @Cnt = Cnt
      FROM   #IntermediateResults
      ORDER  BY id
  END

DROP TABLE #IntermediateResults

SELECT *
FROM   @Results
ORDER  BY A_Id  

Returns

A_Id        B_Id        Cnt
----------- ----------- -----------
1           8           3
2           6           5
4           5           4
Community
  • 1
  • 1
Martin Smith
  • 438,706
  • 87
  • 741
  • 845
  • Wow! I thought a knew a thing or two about SQL, but you've just pointed out that there are plenty of things I don't know :) This is certainly really helpful. One thing I forgot to mention though is that there should be no duplicates in the matches. Really the match with the highest percentage of matched words should take precedence. This is why in my example, I had 4 matching to 5 as the text is equal (100% match), and therefore leaves 1 to match with 8 as it is the next best match. I really like your answer though. It is great food for thought. +1 for you....if I had any reputation. – Mr Moose Mar 31 '11 at 15:13
  • @Mr Moose: Haven't you? :) @Martin: Although it has since been stated that a row can only be matched no more than once, I still think your solution is useful. And even if you are not going to rework it, it's a good one to start with. – Andriy M Mar 31 '11 at 16:05
  • @Andriy - Thanks. I might rework it. Its easy enough to do `ROW_NUMBER() OVER (PARTITION BY A_Id ...` to get the TOP 1 per A. And `ROW_NUMBER() OVER (PARTITION BY B_Id ...` to get the TOP 1 per B but its escaping me at the moment of a good way of combining the two. – Martin Smith Mar 31 '11 at 16:23
  • Thanks so much for such an awesome answer. I really appreciate the effort you've gone to. I'll now run it against some test data (hundreds of records per table) and see how it performs. +1 for you now that I am able (Thanks @Andriy M for pointing that out.) – Mr Moose Apr 01 '11 at 02:21