Сравнение строк в SQL: редактирование расстояния и алгоритм Левенштейна
Иногда вам нужно знать, насколько похожи слова, а не идентичны ли они. Получить общую меру сходства сложно, вероятно, невозможно, потому что сходство так сильно определяется культурой. Алгоритм Soundex может давать некоторые совпадения, но настаивает на том, что, например, «voluptuousness» и «velvet» похожи. Семейные генеалоги в Британии никогда не найдут алгоритм поиска, который помог бы им понять, что некоторые ветви семьи Теобальд пишут свою фамилию «Tibble», хотя Soundex знает, что они довольно близки. Чтобы оценить подобного рода сходство, вам нужно знать контекст языка, произношения, культуры и семантики. Однако мы можем прибегнуть к более научным мерам, основанным на сравнении последовательностей, хотя они никогда не будут идеальными.
‘Edit distance’ - это очевидный способ измерения сходства последовательностей значений, а строки - это просто последовательности символов. Сколько правок требуется для преобразования первой строки во вторую? Редактирование может быть вставкой, удалением, заменой или транспозицией. Алгоритмы для выполнения этой «задачи исправления строки в строку» для любых последовательностей были актуальны с шестидесятых годов и все более совершенствуются для целого ряда наук, таких как исследования генома, криминалистика, дендрохронология и прогнозный текст.
Динамический подход к поиску расстояния редактирования лучше всего осуществить с помощью матрицы. Решения для этого существуют для всех типов языков. SQL имеет недостатки из-за отсутствия поддержки матриц. Вместо этого можно использовать эквивалентное отношение, но оно излишнее и медленное. Нам не нужны все замечательные вещи, которые дает нам отношение. Самые быстрые динамические решения в SQL, как правило, используют строки Unicode в качестве матриц кода, поскольку их можно использовать в качестве целочисленных матриц, но их сложно использовать и отлаживать.
К счастью, существуют сторонние функции CLR для вычисления расстояния Дамерау-Левенштейна в SQL Server. Расстояние Левенштейна, разработанное Владимиром Левенштейном в 1965 году, является алгоритмом, который мы изучаем в колледже для измерения разницы редактирования. Он не имеет дело с транспозициями, потому что он даже не пытается их обнаружить: он записывает одну транспозицию как две правки: вставка и удаление. Алгоритм Дамерау-Левенштейна для редактирования расстояния решает эту проблему.
Вот простая реализация алгоритма Левенштейна с использованием полной матрицы. В этой версии мы ограничили длину строки, чтобы добиться хорошей производительности. Мы удвоили производительность, удалив NVARCHAR (MAX).
|
CREATE function LEVENSHTEIN ( @SourceString nvarchar(100), @TargetString nvarchar(100) ) --Returns the Levenshtein Distance between @SourceString string and @TargetString --Translated to TSQL by Joseph Gama --Updated slightly by Phil Factor returns int as BEGIN DECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int, @ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int, @Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells int -- Step 1: Set n to be the length of s. Set m to be the length of t. -- If n = 0, return m and exit. -- If m = 0, return n and exit. -- Construct a matrix containing 0..m rows and 0..n columns. if @SourceString is null or @TargetString is null return null Select @SourceStringLength=LEN(@SourceString), @TargetStringLength=LEN(@TargetString), @Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1)) If @SourceStringLength = 0 return @TargetStringLength If @TargetStringLength = 0 return @SourceStringLength if (@TargetStringLength+1)*(@SourceStringLength+1)> 4000 return -1 --Step 2: Initialize the first row to 0..n. -- Initialize the first column to 0..m. SET @ii=0 WHILE @ii<=@SourceStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))--d(i, 0) = i SET @ii=@ii+1 END SET @ii=0 WHILE @ii<=@TargetStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))--d(0, j) = j SET @ii=@ii+1 END --Step 3 Examine each character of s (i from 1 to n). SET @ii=1 WHILE @ii<=@SourceStringLength BEGIN
--Step 4 Examine each character of t (j from 1 to m). SET @jj=1 WHILE @jj<=@TargetStringLength BEGIN --Step 5 and 6 Select --Set cell d[i,j] of the matrix equal to the minimum of: --a. The cell immediately above plus 1: d[i-1,j] + 1. --b. The cell immediately to the left plus 1: d[i,j-1] + 1. --c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost @Above=unicode(substring(@Matrix,@jj*(@SourceStringLength+1)+@ii-1+1,1))+1, @ToTheLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1,1))+1, @AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1)) + case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1)) then 0 else 1 end--the cost -- If s[i] equals t[j], the cost is 0. -- If s[i] doesn't equal t[j], the cost is 1. -- now calculate the minimum value of the three if (@Above < @ToTheLeft) AND (@Above < @AboveAndToLeft) select @MinimumValueOfCells=@Above else if (@ToTheLeft < @Above) AND (@ToTheLeft < @AboveAndToLeft) select @MinimumValueOfCells=@ToTheLeft else select @MinimumValueOfCells=@AboveAndToLeft Select @Matrix=STUFF(@Matrix, @jj*(@SourceStringLength+1)+@ii+1,1, nchar(@MinimumValueOfCells)), @jj=@jj+1 END SET @ii=@ii+1 END --Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m] return unicode(substring( @Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1 )) END go |
Вот тот же базовый код с дополнениями, чтобы превратить его в алгоритм Дамерау-Левенштейна.
|
CREATE function DamerauLevenschtein ( @SourceString nvarchar(100), @TargetString nvarchar(100) ) --Returns the Damerau Levenshtein Distance between @SourceString string and @TargetString --Updated by Phil Factor to add transposition as an edit returns int as BEGIN --DECLARE @SourceString nvarchar(100)='achieve', @TargetString nvarchar(100)='acheive' DECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int, @ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int, @Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells INT, @previous INT
-- Step 1: Set n to be the length of s. Set m to be the length of t. SELECT @SourceString=RTRIM(LTRIM(COALESCE(@sourceString,''))), @TargetString=RTRIM(LTRIM(COALESCE(@TargetString,''))), @SourceStringLength=LEN(@SourceString), @TargetStringLength=LEN(@TargetString)
-- remove matches at the beginning and end IF SUBSTRING(@sourceString,1,1)=SUBSTRING(@targetString,1,1) BEGIN SET @ii=1 WHILE SUBSTRING(@sourceString+'!!',@ii+1,1)=SUBSTRING(@targetString+'??',@ii+1,1) BEGIN SELECT @ii=@ii+1 END SELECT @sourceString=STUFF(@sourceString,1,@ii,''), @targetString=STUFF(@targetString,1,@ii,'') END
SELECT @SourceStringLength =LEN(@sourceString), @TargetStringLength =LEN(@TargetString) IF SUBSTRING(@sourceString,@SourceStringLength,1)=SUBSTRING(@targetString,@TargetStringLength,1) BEGIN WHILE SUBSTRING(@sourceString,@SourceStringLength-1,1)=SUBSTRING(@targetString,@TargetStringLength-1,1) AND @SourceStringLength>0 AND @TargetStringLength>0 BEGIN SELECT @SourceStringLength=@SourceStringLength-1, @TargetStringLength=@TargetStringLength-1 END SELECT @sourceString=LEFT(@sourceString,@SourceStringLength) SELECT @targetString=LEFT(@targetString,@TargetStringLength) END -- If n = 0, return m and exit. -- If m = 0, return n and exit. If @SourceStringLength = 0 return @TargetStringLength If @TargetStringLength = 0 return @SourceStringLength if (@TargetStringLength+1)*(@SourceStringLength+1)> 4000 return -1 IF @SourceStringLength=1 RETURN @TargetStringLength -CASE WHEN CHARINDEX(@SourceString,@TargetString)>0 THEN 1 ELSE 0 end IF @TargetStringLength=1 RETURN @SourceStringLength -CASE WHEN CHARINDEX(@TargetString,@SourceString)>0 THEN 1 ELSE 0 end -- Construct a matrix containing 0..m rows and 0..n columns. SELECT @Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1)) --Step 2: Initialize the first row to 0..n. -- Initialize the first column to 0..m. SET @ii=0 WHILE @ii<=@SourceStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))--d(i, 0) = i SET @ii=@ii+1 END SET @ii=0 WHILE @ii<=@TargetStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))--d(0, j) = j SET @ii=@ii+1 END --Step 3 Examine each character of s (i from 1 to n). SET @ii=1 WHILE @ii<=@SourceStringLength BEGIN --Step 4 Examine each character of t (j from 1 to m). SET @jj=1 WHILE @jj<=@TargetStringLength BEGIN --Step 5 and 6 Select --Set cell d[i,j] of the matrix equal to the minimum of: --a. The cell immediately above plus 1: d[i-1,j] + 1. --b. The cell immediately to the left plus 1: d[i,j-1] + 1. --c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost @Cost=case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1)) then 0 else 1 END,--the cost -- If s[i] equals t[j], the cost is 0. -- If s[i] doesn't equal t[j], the cost is 1. @Above =unicode(substring(@Matrix, @jj * (@SourceStringLength+1)+@ii-1+1,1))+1, @ToTheLeft =unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1 ,1))+1, @AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1))+@cost, @previous =unicode(substring(@Matrix,(@jj-2)*(@SourceStringLength+1)+@ii-2+1,1))+@cost -- now calculate the minimum value of the three if (@Above < @ToTheLeft) AND (@Above < @AboveAndToLeft) select @MinimumValueOfCells=@Above else if (@ToTheLeft < @Above) AND (@ToTheLeft < @AboveAndToLeft) select @MinimumValueOfCells=@ToTheLeft else select @MinimumValueOfCells=@AboveAndToLeft IF (substring(@SourceString,@ii,1) = substring(@TargetString,@jj-1,1) and substring(@TargetString,@jj,1) = substring(@SourceString,@ii-1,1)) begin SELECT @MinimumValueOfCells = CASE WHEN @MinimumValueOfCells< @previous THEN @MinimumValueOfCells ELSE @previous END end --write it to the matrix SELECT @Matrix=STUFF(@Matrix, @jj*(@SourceStringLength+1)+@ii+1,1, nchar(@MinimumValueOfCells)), @jj=@jj+1 END SET @ii=@ii+1 END --Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m] return unicode(substring( @Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1 )) end |
Наверное лучшее из SQL-решений для алгоритма Левенштейна - это псевдонимное «Арнольд Фриббл» (возможно, ссылка на Арнольда Риммера из Red Dwarf и его «друга» Мистера Флиббла.), которая является SQL-версией улучшенного Левенштейна. Алгоритм, который обходится без полной матрицы и использует только два вектора.
Можно ли это сделать с помощью отношений? Да, но без поддержки матриц это немного болезненно, поскольку полная матричная версия занимает в десять раз больше, чем строковая версия. Хотя есть много возможностей для улучшения.
.
|
alter FUNCTION LevenschteinDifference ( @FirstString nVarchar(255), @SecondString nVarchar(255) ) RETURNS int as begin Declare @PseudoMatrix table (location int identity primary key, firstorder int not null, Firstch nchar(1), secondorder int not null, Secondch nchar(1), Thevalue int not null default 0, PreviousRowValues varchar(200) )
insert into @PseudoMatrix (firstorder, firstch, secondorder, secondch, TheValue ) SELECT TheFirst.number,TheFirst.ch, TheSecond.number,TheSecond.ch,0 FROM --divide up the first string into a table of characters/sequence (SELECT number, SUBSTRING(@FirstString,number,1) AS ch FROM numbers WHERE number <= LEN(@FirstString) union all Select 0,Char(0)) TheFirst cross JOIN --divide up the second string into a table of characters/sequence (SELECT number, SUBSTRING(@SecondString,number,1) AS ch FROM numbers WHERE number <= LEN(@SecondString) union all Select 0,Char(0)) TheSecond --ON Thefirst.ch= Thesecond.ch --do all valid matches order by TheFirst.number, TheSecond.number
Declare @current Varchar(255) Declare @previous Varchar(255) Declare @TheValue int Declare @Deletion int, @Insertion int, @Substitution int, @minim int Select @current='', @previous='' Update @PseudoMatrix Set @Deletion=@TheValue+1, @Insertion=ascii(substring(@previous,secondorder+1,1))+1, @Substitution=ascii(substring(@previous,(secondorder),1)) +1, @minim=case when @Deletion<@Insertion then @Deletion else @insertion end, @TheValue = Thevalue = case --when Firstorder+SecondOrder=0 then 0 when SecondOrder=0 then FirstOrder When FirstOrder=0 then Secondorder when FirstCh=SecondCh then ascii(substring(@previous,(secondorder),1)) else case when @Minim<@Substitution then @Minim else @Substitution end end, @Previous=PreviousRowValues=case when secondorder =0 then @current else @Previous end, @current= case when secondorder =0 then char(@TheValue) else @Current+char(@TheValue) end return @TheValue End Go |
Что использовать? Если нам нужна производительность, и нам разрешен CLR, мы используем подход CLR. В противном случае, мы все еще используем подход ‘Arnold Fribble’ для сравнения строк Он достаточно хорошо масштабируется и достаточно быстр, но трудно не думать, что с помощью оконных функций и таблицы чисел можно было бы эффективно получить отображение «расстояния редактирования» из подпрограммы, которая является действительно реляционной.