Books and articles about SQL Rambler's Top100 Сменить язык на: Русский 09 December 2021 11:15:27


www.sql-ex.ru
Skip Navigation Links  

 

Print  Версия для печати

На главную страницу

Количественное определение различий текста на T-SQL

William Brewer (оригинал: Quantifying Text differences in T-SQL)
Перевод Моисеенко С.И.

В T-SQL имеются ограниченные возможности по сравнению текстовых строк. Они являются либо равными, либо нет. Рано или поздно, обычно при очистке данных, требуется нечто более тонкое!

Когда Вы сравниваете два фрагмента текста или две строки в выражении на SQL Server, Вы получите только значение 'true', которое возвращается, если эти два фрагмента совпадают, 'false', если - нет, или 'null' ('unknown' - прим. переводчика), если один из сравниваемых фрагментов был null.

Всего лишь одного лишнего символа пробела достаточно, чтобы склонить чашу весов. Это весьма не похоже на действительность - если мы смотрим на два фрагмента текста, мы оцениваем их как одинаковые, почти одинаковые, близкие, совсем непохожие, и еще много промежуточных оттенков. Итак, нам нужно оценить различия?

Алгоритмы различия текста столько же стары, как холмы, но не в T-SQL

В приложениях ИТ есть несколько случаев, когда нам нужно больше мер различия текстов, чем просто 'да, они одинаковы / нет, они не одинаковы'. Типичная проблема состоит в обнаружении дубликатов в записях базы данных, где понимание 'дубликата' учитывает незначительные различия. Построение надежного алгоритма для количественного определения подобия текстов весьма сложно, особенно алгоритма, основанного на теории множеств. T-SQL не имеет никаких естественных средств для использования регулярных выражений и других средств, которые бы сделали жизнь проще при выполнении такого рода работы

Я нахожу эту проблему весьма интригующей, но я не могу претендовать на то, чтобы предложить решение, которое является в какой-либо степени совершенным. Я хотел бы предложить это решение для обсуждения нашим читателям, поскольку хорошее решение было бы необычайно полезным. Меня совсем не вдохновляют алгоритмы 'soundex', они, кажется, мало чему помогают. Я имел виды на получение хорошего решения для количественной оценки различий между блоками текста, но не достиг идеала.

Я нахожу, что решение, счетчик различий, которое я привожу ниже, достаточно хорошо для моих целей, хотя иногда дает счет различий, который мне не нравится. Испытайте его сами на множестве вариантов строк, и вы увидите, что это довольно неплохая попытка. Он, конечно, медленный из-за скучного разбиения текста на слова и разделители. Обычно это только делается только один раз при импорте текста в базу данных - в таблицу 'inversion'. Можно использовать эти данные, чтобы проверить подобие оригинального текста, что будет намного быстрее. Только для того, чтобы этот код работал на SQL Server 2000, я использую в функции параметр nTEXT, а не VARCHAR (MAX), хотя последний сделал бы процедуру более простой.

"Очистка данных - не точная наука"

В действительности, каждый из нас сталкивается с требованиями при проверке различий, которые за счет тонких отличий никогда не есть те же самые. Очистка данных не является точной наукой. Я вообще предпочитаю игнорировать разделители (White-space), включая новую строку и знаки пунктуации, при проверке различий. Мой подход состоит в том, чтобы разбить текст на слова и 'не-слова' или разделители. Я именую так различные типы символов. Табличная функция, которую я привожу ниже, позволяет Вам определить слово в терминах символов, которые составляют слово. Это различается в разных языках. Процедура вообще, хотя и не всегда, будет намного быстрее, если Вы воспользуетесь таблицей чисел 'number', но я решил, что создание такой таблицы для этой статьи отвлекло бы читателя от главного.

С использованием табличной функции 'parsing', я делаю затем простое внешнее соединение между двумя наборами слов, и считаю количество раз, когда минимум 'лучших совпадений' слов меняется в их последовательности. Конечно, это - аппроксимация: я должен бы использовать прокрутку и другие приспособления, основанные на итерациях. У каждого наступает момент, когда следует передать работу программистам. Я обычно останавливаюсь тогда, когда процедура выполняет нужную мне работу.

Напоследок я приготовил изменение функции, которая обеспечивает однострочную таблицу, дающую первую точку, в которой отличаются два образца текста. Это действительно лишь побочный продукт первой процедуры, но я включил ее, чтобы дать представление о многих способах, которыми процедура может быть приспособлена к специфическим случаям. Это удивительно удобно для приложений типа итоговых отчетов о последних изменениях, сделанных в хранимых процедурах!

 

IF OBJECT_ID(N'dbo.uftWordTokens') IS NOT NULL
  DROP FUNCTION dbo.uftWordTokens
GO

/*------------------------------------------------------------*/
CREATE FUNCTION [dbo].[uftWordTokens]
  (
    @string NTEXT,
    @WordStartCharacters VARCHAR(255) = 'a-z',
    @WordCharacters VARCHAR(255) = '-a-z'''
  )
RETURNS @Results TABLE
  (
    SeqNo INT IDENTITY(1, 1),
    Item VARCHAR(255),
    TokenType INT
  )
AS /*
Эта табличная функция создает таблицу, которая разделяет слова
и пробелы между словами в некотором тексте и создает таблицу
двух типов, взятых в последовательности, в которой они обнаруживаются
*/
   BEGIN
    DECLARE @Pos INT,    --индекс текущего поиска
      @WhereWeAre INT,--текущий индекс в строке
      @ii INT,    --текущее число найденных слов
      @next INT,  --откуда стартует поиск
      @size INT   --полный размер текста

    SELECT  @ii = 0, @WhereWeAre = 1, @size = DATALENGTH(@string)


    WHILE @Size >= @WhereWeAre
      BEGIN
        SELECT  @pos = PATINDEX('%[' + @wordStartCharacters + ']%',
                                SUBSTRING(@string, @whereWeAre, 4000))
        IF @pos > 0
          BEGIN
            IF @pos > 1
              INSERT  INTO @Results
                      ( item, tokentype )
                      SELECT  SUBSTRING(@String, @whereWeAre, @pos - 1), 2
            SELECT  @next = @WhereWeAre + @pos, @ii = @ii + 1
            SELECT  @pos = PATINDEX('%[^' + @wordCharacters + ']%',
                                    SUBSTRING(@string, @next, 4000) + ' ')
            INSERT  INTO @Results
                    ( item, tokentype )
                    SELECT  SUBSTRING(@String, @next - 1, @pos), 1
            SELECT  @WhereWeAre = @next + @pos - 1
          END
        ELSE
          BEGIN
            IF LEN(REPLACE(
                    SUBSTRING(@String, @whereWeAre, 4000), ' ', '!'
            )) > 0
              INSERT  INTO @Results
                      ( item, tokentype )
                      SELECT  SUBSTRING(@String, @whereWeAre, 4000), 2
            SELECT  @whereWeAre = @WhereWeAre + 4000
          END
      END
    RETURN
   END

/* Тесты:
SELECT  '[' + item + ']', tokentype
FROM    dbo.uftWordTokens('This     has
 been relentlessly
,^----tested', DEFAULT, DEFAULT)
SELECT  '[' + item + ']', tokentype
FROM    dbo.uftWordTokens('This has been relentlessly tested        !',
                          DEFAULT, DEFAULT)
SELECT  item, tokentype
FROM    dbo.uftWordTokens('This has been', DEFAULT, DEFAULT)
SELECT  '[' + item + ']', tokentype
FROM    dbo.uftWordTokens(' ',
                          DEFAULT, DEFAULT)

*/
GO

IF OBJECT_ID(N'dbo.ufnDifferencesInText') IS NOT NULL
  DROP FUNCTION dbo.ufiDifferencesInText
GO
/*------------------------------------------------------------*/
CREATE FUNCTION dbo.ufiDifferencesInText
  (
    @Sample NTEXT,
    @comparison NTEXT
  )
RETURNS INT
AS BEGIN
    DECLARE @results TABLE
      (
        token_ID INT IDENTITY(1, 1),
        sequenceNumber INT,
        Sample_ID INT,
        Item VARCHAR(255),
        TokenType INT
      )
/*
Эта функция возвращает число отличий, обнаруженное в двух текстах
*/
    INSERT  INTO @results
            ( SequenceNumber, Sample_ID, Item, Tokentype )
            SELECT  seqno, 1, item, tokentype
            FROM    dbo.uftWordTokens(@sample, DEFAULT, DEFAULT)

    INSERT  INTO @results
            ( SequenceNumber, Sample_ID, Item, Tokentype )
            SELECT  seqno, 2, item, tokentype
            FROM    dbo.uftWordTokens(@comparison, DEFAULT, DEFAULT)
    DECLARE @closestMatch TABLE
      (
        sequenceNumber INT,
        skew INT
      )
    INSERT  INTO @closestMatch
            ( sequencenumber, skew )
            SELECT  COALESCE(a.sequencenumber, b.sequencenumber),
                    COALESCEE(MIN(ABS(COALESCE(b.sequenceNumber, 1000)
                        - COALESCE(a.sequencenumber, 1000))),
                             -1)
            FROM    ( SELECT  *
                      FROM    @results
                      WHERE   sample_ID = 1 AND tokentype = 1
                    ) a FULL OUTER JOIN ( SELECT  *
                                          FROM    @results
                                          WHERE   sample_ID = 2
                                              AND tokentype = 1
                                        ) b ON a.item = b.item
            GROUP BY COALESCE(a.sequencenumber, b.sequencenumber)
            ORDER BY COALESCE(a.sequencenumber, b.sequencenumber)



    RETURN ( SELECT SUM(CASE WHEN a.skew - b.skew = 0 THEN 0
                             ELSE 1
                        END)
             FROM   @closestmatch a INNER JOIN @closestMatch b
                  ON b.sequenceNumber = a.sequenceNumber + 2
           )
   END
GO

SELECT  dbo.ufnDifferencesInText('I am a piece of text',
                                 'I am a piece of text')
--0
SELECT  dbo.ufnDifferencesInText('I am a piece of text',
                                 'I am not a piece of text')
--1
SELECT  dbo.ufnDifferencesInText('I am a piece of text',
                                 'I am piece a a a of text')
--2
SELECT  dbo.ufnDifferencesInText('I  piece of text',
                                 'I am a piece of text')
--1
SELECT  dbo.ufnDifferencesInText('I  am a pot of jam',
                                 'I am a piece of text')
--3
SELECT  dbo.ufnDifferencesInText('I  am a pot of jam',
                                 'I  am a pot of jam beloved by humans')
--3
SELECT  dbo.ufnDifferencesInText('I am a piece of text',
                                 'text of piece a am I')
--4
SELECT  dbo.ufnDifferencesInText('I am a piece of text',
                                 'this is completely different')
--5
SELECT  dbo.ufnDifferencesInText('I am a piece of text', '')
--5
SELECT  dbo.ufnDifferencesInText('', 'I am a piece of text')
--5

SELECT  dbo.ufnDifferencesInText('Call me Ishmael. Some years ago -- never mind how long precisely --
having little or no money in my purse, and nothing particular to interest me on shore, I thought I
would sail about a little and see the watery part of the world. It is a way I have of driving off
the spleen, and regulating the circulation. Whenever I find myself growing grim about the mouth;
whenever it is a damp, drizzly November in my soul; whenever I find myself involuntarily pausing
before coffin warehouses, and bringing up the rear of every funeral I meet; and especially whenever
my hypos get such an upper hand of me, that it requires a strong moral principle to prevent me from
deliberately stepping into the street, and methodically knocking people''s hats off -- then, I account
 it high time to get to sea as soon as I can. This is my substitute for pistol and ball. With a
 philosophical flourish Cato throws himself upon his sword; I quietly take to the ship. There is
 nothing surprising in this. If they but knew it, almost all men in their degree, some time or
 other, cherish very nearly the same feelings towards the ocean with me.'
, 'Call me Ishmael. Some years ago -- never mind how long precisely -- having little or no money
in my purse, and nothing particular to interest me on shore, I thought I would sail about a little
and see the watery part of the world. It is a way I have of driving off the spleen, and regulating
 the circulation. Whenever I find myself growing grim about the mouth; whenever it is a damp,
 drizzly November in my soul; whenever I find myself involuntarily pausing before coffin warehouses,
 and bringing up the rear of every funeral I meet; and especially whenever my hypos get such an upper
  hand of me, that it requires a strong moral principle to prevent me from deliberately stepping into
   the street, and methodically knocking people''s hats off -- then, I account it high time to get to
    sea as soon as I can. This is my substitute for pistol and ball. With a philosophical flourish Cato
     throws himself upon his sword; I quietly take to the ship. There is nothing surprising in this.
      If they but knew it, almost all men in their degree, some time or other, cherish very nearly
      the same feelings towards the ocean with me.')


-- =============================================
-- Описание: Процедура, которая возвращает единственную строку,
-- которая дает контекст первого различия двух строк
-- =============================================
IF OBJECT_ID(N'dbo.uftShowFirstDifference') IS NOT NULL
  DROP FUNCTION dbo.uftShowFirstDifference
GO
CREATE FUNCTION uftShowFirstDifference
  (
    -- Добавляем параметры для этой функции
    @sample NTEXT,
    @comparison NTEXT
  )
RETURNS @result TABLE
  (
    -- Добавляем определения столбцов для табличной переменной
    first VARCHAR(2000),
    second VARCHAR(2000),
    [where] INT
  )
AS BEGIN
    DECLARE @results TABLE
      (
        token_ID INT IDENTITY(1, 1),
        sequenceNumber INT,
        Sample_ID INT,
        Item VARCHAR(255),
        TokenType INT
      )
    INSERT  INTO @results
            ( SequenceNumber, Sample_ID, Item, Tokentype )
            SELECT  seqno, 1, item, tokentype
            FROM    dbo.uftWordTokens(@sample, DEFAULT, DEFAULT)

    INSERT  INTO @results
            ( SequenceNumber, Sample_ID, Item, Tokentype )
            SELECT  seqno, 2, item, tokentype
            FROM    dbo.uftWordTokens(@comparison, DEFAULT, DEFAULT)
    DECLARE @closestMatch TABLE
      (
        sequenceNumber INT,
        skew INT
      )
    INSERT  INTO @closestMatch
            ( sequencenumber, skew )
            SELECT  COALESCE(a.sequencenumber, b.sequencenumber),
                    COALESCE(MIN(ABS(COALESCE(b.sequenceNumber, 1000)
                            - COALESCE(a.sequencenumber, 1000))),
                             -1)
            FROM    ( SELECT  *
                      FROM    @results
                      WHERE   sample_ID = 1 AND tokentype = 1
                    ) a FULL OUTER JOIN ( SELECT  *
                                          FROM    @results
                                          WHERE   sample_ID = 2
                                               AND tokentype = 1
                                        ) b ON a.item = b.item
            GROUP BY COALESCE(a.sequencenumber, b.sequencenumber)
            ORDER BY COALESCE(a.sequencenumber, b.sequencenumber)



    DECLARE @first VARCHAR(2000)
    DECLARE @firstDifference INT
    DECLARE @second VARCHAR(2000)
    SELECT  @FirstDifference = MIN(sequenceNumber)
    FROM    @closestMatch
    WHERE   skew <> 0
    SELECT  @first = '', @second = ''
    SELECT TOP 10
            @first = COALESCE(@First, '') + item
    FROM    @results
    WHERE   sample_ID = 1 AND sequenceNumber >= @FirstDifference
    ORDER BY SequenceNumber
    SELECT TOP 10
            @second = COALESCE(@second, '') + item
    FROM    @results
    WHERE   sample_ID = 2 AND sequenceNumber >= @FirstDifference
    ORDER BY SequenceNumber
    INSERT  INTO @result
            ( first, Second, [where] )
            SELECT  [first] = @First, [second] = @second,
                    [where] = @FirstDifference

    RETURN
   END
GO

SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text',
                                   'I am a piece of text')
-- NULL
SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text',
                                   'I am not a piece of text')
--a piece of text     not a piece of text         5
SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text',
                                   'I am piece a a a of text')
--a piece of text     piece a a a of              5
SELECT  *
FROM    dbo.uftShowFirstDifference('I  piece of text',
                                   'I am a piece of text')
--piece of text       am a piece of text          3
SELECT  *
FROM    dbo.uftShowFirstDifference('I  am a pot of jam',
                                   'I am a piece of text')
--pot of jam          piece of text               7
SELECT   *
FROM    dbo.uftShowFirstDifference('I  am a pot of jam',
                                   'I  am a pot of jam beloved by humans')
--                    beloved by humans           13
SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text',
                                   'text of piece a am I')
--I am a piece of     text of piece a am          1
SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text',
                                   'this is completely different')
--I am a piece of     this is completely different 1
SELECT  *
FROM    dbo.uftShowFirstDifference('I am a piece of text', '')
--I am a piece of                                  1
SELECT  *
FROM    dbo.uftShowFirstDifference('', 'I am a piece of text')
--                    I am a piece of              1


 

20-09-2007

На главную страницу

Print  Версия для печати


Usage of any materials of this site is possible
only under condition of mandatory allocation of the direct link to a site
http://www.sqlbooks.ru
on each page where used materials are placed.

 Main   Articles    Books 
Рейтинг@Mail.ru Rambler's Top100 Alt Упражнения по SQL: обучение, тестирование, сертификация по языку SQL Copyright c 2002-2006. All rights reserved.