|
|
Версия для печати
На главную страницу
Количественное определение различий текста на 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
На главную страницу
Версия для печати
|
|