Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
Доброе время суток.
Подскажите, пожалуйста, как улучшить алгоритм поиска наибольшей общей последовательности двух строк. Строки будут представлены двумя таблицными переменными, содеращими символ и его номер в строке. Сделал по алгоритму, найденному в интернете. Но, как то на мой взгляд, будет медленно.
То что нужно в примере создать индексы в таблицных переменных - понимаю, но всё же хотелось бы получить совет по изменению самого алгоритма. Заранее спасибо.
-- таблицы входных предложений, для примера
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));
-- таблица позиций пересечений букв предложений
Declare @charIntersects As Table ([Char] nvarchar(1), rowId int, colId int, grlobalId int);
-- таблица связей позиций
Declare @ParentChild As Table (Parent_Id int, Child_Id int);
-- таблица результатов последовательностей
Declare @Sequences As Table (pathId int, Sentence nvarchar(1024), itemCount int);

-- Две исходные таблицы предложений
Insert Into @colWord Values
(1, N'ч'), (2, N'е'), (3, N'г'), (4, N'о'), (5, N'-'), (6, N'т'), (7, N'м'), (8, N' '), (9, N'в');
Insert Into @rowWord Values
(1, N'в'), (2, N' '), (3, N'м'), (4, N'о'), (5, N'т'), (6, N'ч'), (7, N'е'), (8, N'г'), (9, N'о');

-- заполняем таблицу позиций пересечений букв предложений
-- и присваиваем уникальный индекс каждой позиции
Insert Into @charIntersects
Select
       TR.[Char], TR.rowId, TC.colId,
       Row_Number() Over (Order By TR.rowId, TC.colId) As globalId
From
       @rowWord TR Inner Join @colWord TC On (TR.[Char] = TC.[Char]);

-- заполняем таблицу связей, считая предком позицию у которой
-- и строковый и столбцовый индекс одновременно меньше
-- строкового и столбцового индекса дочерних позиций
Insert Into @ParentChild
Select
       TParent.grlobalId As Parent_Id, TChild.grlobalId As Child_Id
From @charIntersects TParent Inner Join @charIntersects TChild
       On (TParent.rowId < TChild.rowId And TParent.colId < TChild.colId);

-- собираем последовательности
With Joiner (Link_Id, Sentence) As
(
       -- инициализируем начало последовательностей
       -- позициями, которые не имеют предков
       Select Child_Id, 
             Cast(TForP.[Char] + TForC.[Char] as nvarchar(1024))
       From @ParentChild TPC
             Inner Join @charIntersects TForP On (TPC.Parent_Id = TForP.grlobalId)
             Inner Join @charIntersects TForC On (TPC.Child_Id = TForC.grlobalId)
       Where Parent_Id Not In (Select Child_Id From @ParentChild)
       Union All -- дописываем в хвост буквы дочерних
       Select TChild.Child_Id,
             Cast(TParent.Sentence + TForC.[Char] as nvarchar(1024))
       From @ParentChild TChild 
             Inner Join Joiner TParent On (TChild.Parent_Id = TParent.Link_Id)
             Inner Join @charIntersects TForC On (TForC.grlobalId = TChild.Child_Id)
) -- записываем в результат, нумеруя - меньший номер у наибольшей по длине последовательности
Insert Into @Sequences
Select Row_Number() Over (Order By Len(Sentence) Desc),
       Sentence, Len(Sentence) From Joiner;

-- выводим первый результат
Select Sentence From @Sequences T Where pathId = 1;
13 окт 16, 14:39    [19777914]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));

-- Две исходные таблицы предложений
Insert Into @colWord Values
(1, N'ч'), (2, N'е'), (3, N'г'), (4, N'о'), (5, N'-'), (6, N'т'), (7, N'м'), (8, N' '), (9, N'в');
Insert Into @rowWord Values
(1, N'в'), (2, N' '), (3, N'м'), (4, N'о'), (5, N'т'), (6, N'ч'), (7, N'е'), (8, N'г'), (9, N'о');

-- это для осознания тривиальности
select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char];

-- все сопадения в порядке убывания длины
with s as ( select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
              from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char] )
select count(*) as cnt, min(colId) as cStart, max(colId) as cStop, min(rowId) as rStart, max(rowId) as rStop
from s
group by IntervalID
order by count(*) desc;
13 окт 16, 14:58    [19777990]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
Но честно предупреждаю - не фсе так тривиально.
13 окт 16, 14:59    [19777994]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
alexs2, большое спасибо за ваше решение!
Но. Если есть подстроки разной длины, то не очень чётко выходит. Пусть
Insert Into @colWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'а'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'а');
Insert Into @rowWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'о'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'о');

Есть две совпадающие последовательности абс и лютн. Но ваш алгоритм выводит диапазон от 1 до 8.
Я извиняюсь, не совсем подробно описал задачу, полагая, что понятна разница между наибольшей последовательностью и наибольшей подтсрокой Наибольшая общая подпоследовательность.
Для этого примера входных данных результат должен быть абслютн
13 окт 16, 15:39    [19778153]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
anvg
alexs2, большое спасибо за ваше решение!
Но. Если есть подстроки разной длины, то не очень чётко выходит. Пусть
Insert Into @colWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'а'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'а');
Insert Into @rowWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'о'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'о');

Есть две совпадающие последовательности абс и лютн. Но ваш алгоритм выводит диапазон от 1 до 8.
Я извиняюсь, не совсем подробно описал задачу, полагая, что понятна разница между наибольшей последовательностью и наибольшей подтсрокой Наибольшая общая подпоследовательность.
Для этого примера входных данных результат должен быть абслютн

Я нигде не обещал чудес.
Учитесь думать сами.
13 окт 16, 17:58    [19778904]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
попробуйте хранить хэши для всех подстрок, crc64 должно хватить
14 окт 16, 05:53    [19779841]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
Lepsik
попробуйте хранить хэши для всех подстрок, crc64 должно хватить

Ты болен?
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));

-- Две исходные таблицы предложений
--Insert Into @colWord Values
--(1, N'ч'), (2, N'е'), (3, N'г'), (4, N'о'), (5, N'-'), (6, N'т'), (7, N'м'), (8, N' '), (9, N'в');
--Insert Into @rowWord Values
--(1, N'в'), (2, N' '), (3, N'м'), (4, N'о'), (5, N'т'), (6, N'ч'), (7, N'е'), (8, N'г'), (9, N'о');

Insert Into @colWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'а'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'а');
Insert Into @rowWord Values
(1, N'а'), (2, N'б'), (3, N'с'), (4, N'о'), (5, N'л'), (6, N'ю'), (7, N'т'), (8, N'н'), (9, N'о');

-- это для осознания тривиальности
select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char];

-- максимальное совпадение "с дырками"
with s as ( select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
              from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char] )
  select * from s 
    where IntervalID = ( select top(1) IntervalID from s group by IntervalID order by count(*) desc);
 
14 окт 16, 07:37    [19779890]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
дурачек - иди-ка ты лечится в ТП
14 окт 16, 09:45    [19780200]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
Доброе время суток, aleks2
Спасибо за варианты. Хотя на вашу реплику
aleks2
Я нигде не обещал чудес. Учитесь думать сами.
отвечу, я где то требовал чего-нибудь готового? И на осовании чего сделан вывод, о том что я не пытаюсь думать?
Ваш алгоритм хорош, правда учитывая, что ищет только общие подстроки, а не последовательности. Причём хорош и тем, что выявляет общие подстроки вне зависимости от их последовательного расположения в строках. Хотя и не лишён глюка - если в одной из строк есть совпадающая повторяющаяся подстрока, а в другой она встречается только раз, то вывод будет всё равно повторяющимся.
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));

-- Две исходные таблицы предложений
Insert Into @colWord Values
(1, N' '), (2, N'a'), (3, N'b'), (4, N'c'), (5, N' '), (6, N'd'), (7, N'e'), (8, N' '), (9, N' ');
Insert Into @rowWord Values
(1, N'_'), (2, N'd'), (3, N'e'), (4, N'a'), (5, N'b'), (6, N'c'), (7, N'a'), (8, N'b'), (9, N'c');

-- это для осознания тривиальности
select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId, row_number() over(Order By rowId, colId) As gId
from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char];

-- максимальное совпадение "с дырками"
with s as ( select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId,
                    row_number() over(Order By rowId, colId) As gId
              from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char] )
  select * from s 
    where IntervalID In ( select IntervalID from s group by IntervalID Having Count(*) > 1)
       Order By gId;

Резльтат должен быть abcde или deabc (для оценки совпадения строк разницы нет), а получается deabcabc
14 окт 16, 11:17    [19780784]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
кролик-зануда
Guest
anvg,
а почему же тогда ваш "медленный" алгоритм возвращает abc?
14 окт 16, 11:34    [19780903]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
кролик-зануда, а он и должен вернуть 'abc'. Алгоритм ищет наибольшую последовательность между двумя строками слева на право с расстоянием между символами не обязательно раным 1 (например, 'a___bc__d___e' и 'a bc de' предложенный алгоритм выдаст наибольшую последовательность 'abcde',а алгоритм aleks2 только 'bc').
В строках совпадают подстроки 'de' и 'abc', но они не идут последовательно. В 1 строке 'abc' 'de', а во второй 'de' 'abc' => наибольшая последовательность 'abc'.
14 окт 16, 12:09    [19781088]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
anvg
Доброе время суток, aleks2
Спасибо за варианты. Хотя на вашу реплику
aleks2
Я нигде не обещал чудес. Учитесь думать сами.
отвечу, я где то требовал чего-нибудь готового? И на осовании чего сделан вывод, о том что я не пытаюсь думать?
Ваш алгоритм хорош, правда учитывая, что ищет только общие подстроки, а не последовательности. Причём хорош и тем, что выявляет общие подстроки вне зависимости от их последовательного расположения в строках. Хотя и не лишён глюка - если в одной из строк есть совпадающая повторяющаяся подстрока, а в другой она встречается только раз, то вывод будет всё равно повторяющимся.
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));

-- Две исходные таблицы предложений
Insert Into @colWord Values
(1, N' '), (2, N'a'), (3, N'b'), (4, N'c'), (5, N' '), (6, N'd'), (7, N'e'), (8, N' '), (9, N' ');
Insert Into @rowWord Values
(1, N'_'), (2, N'd'), (3, N'e'), (4, N'a'), (5, N'b'), (6, N'c'), (7, N'a'), (8, N'b'), (9, N'c');

-- это для осознания тривиальности
select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId, row_number() over(Order By rowId, colId) As gId
from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char];

-- максимальное совпадение "с дырками"
with s as ( select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId,
                    row_number() over(Order By rowId, colId) As gId
              from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char] )
  select * from s 
    where IntervalID In ( select IntervalID from s group by IntervalID Having Count(*) > 1)
       Order By gId;

Резльтат должен быть abcde или deabc (для оценки совпадения строк разницы нет), а получается deabcabc


Ты хоть осознаешь, чего делаешь то? Или так, "от балды" рисуешь запросы?
14 окт 16, 12:13    [19781110]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
anvg
кролик-зануда, а он и должен вернуть 'abc'. Алгоритм ищет наибольшую последовательность между двумя строками слева на право с расстоянием между символами не обязательно раным 1 (например, 'a___bc__d___e' и 'a bc de' предложенный алгоритм выдаст наибольшую последовательность 'abcde',а алгоритм aleks2 только 'bc').
В строках совпадают подстроки 'de' и 'abc', но они не идут последовательно. В 1 строке 'abc' 'de', а во второй 'de' 'abc' => наибольшая последовательность 'abc'.


Он еще и клевещет:
Declare @colWord As Table(colId int, [Char] nvarchar(1));
Declare @rowWord As Table(rowId int, [Char] nvarchar(1));

-- Две исходные таблицы предложений
-- Две исходные таблицы предложений
Insert Into @colWord Values
(1, N' '), (2, N'a'), (3, N'b'), (4, N'c'), (5, N' '), (6, N'd'), (7, N'e'), (8, N' '), (9, N' ');
Insert Into @rowWord Values
(1, N'_'), (2, N'd'), (3, N'e'), (4, N'a'), (5, N'b'), (6, N'c'), (7, N'a'), (8, N'b'), (9, N'c');

-- это для осознания тривиальности
select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char];

-- максимальное совпадение "с дырками"
with s as ( select c.[Char], IntervalID = c.colId - r.rowId, c.colId, r.rowId
              from @colWord as c inner join @rowWord as r on c.[Char] = r.[Char] )
  select * from s 
    where IntervalID = ( select top(1) IntervalID from s group by IntervalID order by count(*) desc);


Char	IntervalID	colId	rowId
a -2 2 4
b -2 3 5
c -2 4 6
14 окт 16, 12:18    [19781135]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
aleks2
Или так, "от балды" рисуешь запросы?
Почему это сразу от балды? ;) Проверяю разные гипотезы. Ваш алгоритм тем и интересен, что можно проверять 'Иванов Сидор Петрович' и 'Сидор Петрович Иванов' - по сути одинаковые данные в строках.
Для подобного класса задач очень хорошее решение, так что зря вы в своём последнем варианте "потеряли" de. В любом случае - большое спасибо.
14 окт 16, 12:40    [19781223]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
aleks2
Guest
anvg
aleks2
Или так, "от балды" рисуешь запросы?
Почему это сразу от балды? ;) Проверяю разные гипотезы. Ваш алгоритм тем и интересен, что можно проверять 'Иванов Сидор Петрович' и 'Сидор Петрович Иванов' - по сути одинаковые данные в строках.
Для подобного класса задач очень хорошее решение, так что зря вы в своём последнем варианте "потеряли" de. В любом случае - большое спасибо.

Я не потерял. У меня фсе ходы записаны.

Другое дело, что ты не могешь внятно сформулировать свои хотелки.
Но сам понимаешь - это твои проблемы.
14 окт 16, 12:54    [19781307]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
aleks2
ты не могешь внятно сформулировать свои хотелки.
По моему я вполне внятно сформулировал вопрос в первом сообщении - оптимизация запроса для решения задачи Long Common Sequence. Собственно моя реализация работает, как то описывает алгоритм. ('a___bc__d___e' и ' a bc de' предложенный алгоритм выдаст наибольшую последовательность 'abcde)
Вами было предложено отличное частное решение этой задачи - нахождение наибольшей общей подстроки. Плюс, как часть решения - выявление всех общих подстрок двух строк в не зависимости от порядка следования этих подстрок в исходных строках. Осталось решить проблему как подавить вывод, если одна и таже подстрока в 1 строке встречается один раз, а во второй несколько.
То есть. 1 строка - 'ура решение!' и вторая строка - 'решение, ура, ура!'.
Требуемый результат 'ура решение' или 'решение ура', в то время как для адаптированного варианта ("лобовое использование повторяющихся значений IntervalID) получается 'ррешениее ура ура!'
Пытаюсь чего-нибудь придумать.
14 окт 16, 14:25    [19781856]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
кролик-зануда
Guest
anvg,

вы снова себе противоречите
с одной стороны
anvg

То есть. 1 строка - 'ура решение!' и вторая строка - 'решение, ура, ура!'.
Требуемый результат 'ура решение' или 'решение ура'


с другой

anvg
моя реализация работает


рискну предположить, что она не выдаст ни один из вариантов требуемого результата.
14 окт 16, 15:51    [19782454]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
кролик-зануда, а в чём вы видите противоречие? Я понимаю, что текста уже написано много, но пояснения я уже давал.
И моя реализация LCS и алгоритм aleks2, выявляют наибольшую подстроку в обоих строках 'решение'.
Теперь же обдумывается решение, нахождение всех полных подстрок двух строк. Для последнего примера это подстроки 'ура' и 'решение'. И, да, я описался, желаемое может быть только 'урарешение' или 'решениеура', как склейка этих общих подстрок.
Если рассмотреть что выдаёт алгоритм aleks2 в поле IntervalID, то казалось, что можно для этого случая зацепиться за его равные значения, как признак совпадающих подстрок, но, увы, не всё так просто. Надо думать дальше.
14 окт 16, 16:43    [19782750]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
кролик-зануда
Guest
anvg
Теперь же обдумывается решение, нахождение всех полных подстрок двух строк.


тогда перестаньте отправлять к изначальному описанию, в нем об этом ничего нет.

а лучше сформулируйте то, что вы хотите получить теперь.
а то в одном сообщении вы добавляете односимвольные совпадения, в другом - игнорируете "!"
14 окт 16, 17:04    [19782860]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм наибольшей общей последовательности двух строк  [new]
anvg
Member

Откуда: СПб
Сообщений: 101
Доброе время суток.
кролик-зануда
а то в одном сообщении вы добавляете односимвольные совпадения, в другом - игнорируете "!"

Потому что рассматриваются два алгоритма.
1-ый – наибольшая общая последовательность символов (LCS). Символы в строках идут в том же порядке в обеих строках, но индексное расстояние между символами произвольное.
2-ой – наибольшая общая подстрока. Здесь более жёсткое ограничение – расстояние между соседними символами должно быть равно 1.
В первом приближении задачу можно описать так. Имеется эталонная строка. Её «повредили»: 5-10% символов случайным образом заменили, 5-10% удалили. Разбили на 3-4 приблизительно равные части и их случайным образом переставили.
На входе несколько таких «повреждённых» строк. Требуется определить, какая из них исходная эталонная строка.
Предварительная гипотеза: найти все LCS между «повреждённой» и «эталонной» строками и по нему определить меру сходства.
Несколько переделал алгоритм поиска LCS первого сообщения.
Declare @MaxRow int, @curRow int = 1;
-- таблицы входных предложений, для примера
Declare @colSentence As Table(colId int, [Char] nvarchar(1));
Declare @rowSentence As Table(rowId int, [Char] nvarchar(1));
-- таблица позиций пересечений букв предложений
Declare @charIntersect As Table ([Char] nvarchar(1), colId int, rankRow int, Index idx_rank (rankRow));
-- таблица результатов последовательностей
Declare @Sequences As Table 
	([Sequence] nvarchar(1024), charCount int, rankRow int, colId int,
	 Primary Key (rankRow Desc, colId Desc), Index idx_needed (charCount Desc, rankRow Desc, colId Desc));

-- Две исходные таблицы предложений
Insert Into @colSentence Values
(1, N'_'), (2, N'a'), (3, N'b'), (4, N'_'), (5, N'c'), (6, N'_'), (7, N'd'), (8, N'e'), (9, N'e');
Insert Into @rowSentence Values
(1, N'd'), (2, N'a'), (3, N'e'), (4, N' '), (5, N'b'), (6, N' '), (7, N'c'), (8, N'd'), (9, N'e');

-- заполняем таблицу позиций пересечений букв предложений, создавая сквозную нумерацию 
-- строк (какие-то символы могу и не совпадать и существующий номер будет пропущен).
Insert Into @charIntersect
Select
       TR.[Char], TC.colId,
	   Dense_Rank() Over (Order By TR.rowId) As rankId
From @rowSentence TR Inner Join @colSentence TC On (TR.[Char] = TC.[Char]);

-- Формируем опорный элемент
Insert Into @Sequences Values (N'', 0, 0, 0);
-- число строк
Select @MaxRow = Max(rankRow) From @charIntersect;
-- выбираем для каждого символа строки начальную последовательность
-- максимальной длины (по возможности ближайшую по строке и столбцу)
While (@curRow <= @MaxRow)
begin
	Insert Into @Sequences
	Select
		(Select Top(1) TSec.[Sequence] From @Sequences TSec 
		 Where TChar.rankRow > TSec.rankRow And TChar.colId > TSec.colId
		 Order By TSec.charCount Desc, TSec.rankRow Desc, TSec.colId Desc
		) + TChar.[Char] As [Sequence],
		(Select Top(1) TSec.[charCount] From @Sequences TSec 
		 Where TChar.rankRow > TSec.rankRow And TChar.colId > TSec.colId
		 Order By TSec.charCount Desc, TSec.rankRow Desc, TSec.colId Desc
		) + 1 As [charCount],
		TChar.rankRow, TChar.colId
	From @charIntersect TChar 
	Where TChar.rankRow = @curRow
	Set @curRow = @curRow + 1;
end;
Select Top(1) * From @Sequences Order By charCount Desc;

Подскажите, пожалуйста, насколько правильно настроил индексы для табличных переменных? Интересует, будет ли в цикле while поиск и вставка в @Sequences выполняться за Log(N)? И как лучше это сделать? И можно ли избавиться от while (цикл над таблицами для выборки вставки выглядит не совсем правильно с точки зрения концепции баз данных)?
По идее должно по скорости выполняться в лучшем случае (все символы в строках уникальные и строки равны) – за N*Log(N), а в худшем (в обеих строках один и тот же символ) – за N^2*Log(N). В первой реализации было. Лучшее – N^2, худшее – за N^3.
Для поиска всех последовательностей, похоже, придётся делать внешний цикл, для поиска LCS замены найденных символов на заведомо несуществующий, и поиск новой LCS, пока не получим пустую. Похоже сложность будет N^2*Log(N).
16 окт 16, 08:27    [19786426]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить