Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
Есть 2 набора строк (упростим до букв):
Порядок
1ab
2b<->c
3ce
4df
5eb
6fa


Нужно найти одинаковые подпоследовательности:
b
c
e
f


Не нашёл готового решения под SQL, только под другие языки, есть только некая идея. Есть ли таковые под SQL?

Моё псевдорешение даёт все вхождения (и закомментированые варианты), но не последовательности.
SELECT T1.Значения, T1.Порядок, T2.Порядок
FROM Набор1 T1
INNER JOIN
(SELECT *
FROM Набор2 T2
ON T1.Значение = T2.Значение
--WHERE T1.Порядок = T2.Порядок
--WHERE T1.Порядок <> T2.Порядок
--GROUP BY T1.Значение


P.S.: Возможно ли будет сделать запросом, а не функцией с перебором?
13 ноя 14, 14:22    [16840273]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
Ang3L,

из ваших данных по вашему-же условию - такой результат как у вас получить нельзя.
13 ноя 14, 14:29    [16840330]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
А как можно получить из моих данных такой результат?
13 ноя 14, 14:40    [16840448]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8807
Ang3L,

это задача по программированию или по угадыванию? Вы уж определитесь.
13 ноя 14, 14:45    [16840494]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
Построение SQL запросов можно считать программированием? Если да, то задача по программированию. Если нет, то помочь мне или построить SQL запрос, который может выдать такой результат, или помочь написать функцию.

Короче, любой подходящий вариант: Запрос, процедура, функция в SQL.
13 ноя 14, 14:55    [16840587]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Glory
Member

Откуда:
Сообщений: 104751
Ang3L
Построение SQL запросов можно считать программированием? Если да, то задача по программированию.

Ваша задача есть задача перебора и нахождения какого одного из многих возможных решений
13 ноя 14, 15:02    [16840651]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
Ang3L
А как можно получить из моих данных такой результат?

КАК ? У вас в первом наборе данных нет поледоваьного набора
b
c
e
f

Ang3L
Есть 2 набора строк (упростим до букв):
Порядок
1ab
2b<->c
3ce
4df
5eb
6fa


Нужно найти одинаковые подпоследовательности:
b
c
e
f


13 ноя 14, 15:33    [16840900]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
Maxx
КАК ?

В этом и был вопрос.

В общем случае, найти последовательности которые не пересекаются и идут последовательно (какая тафталогия :) ), т.е. друг за другом. Тема точно отражает задачу. Но всё что я нагуглил были общие принципы и код на С++, в основном.

Примерно (из данных предоставленых мною):
bc самая длинная подпоследовательность, которая есть и в наборе1 и в наборе2. То же и с ef. Оставшиеся подпоследовательности b и a (по 1 елементу в каждой) идут после найденных нами подпоследовательностей, а в наборе1 они до (поэтому их откидываем). Вот и получается остаются 2 подпоследовательности: bc и ef, которые можно объединить в 1 таблицу (в результирующий набор).

Остальные подпоследовательности которые есть в наборе2 нет в наборе1.

К чему всё это? Основная задача: найти разницу между 2 текстами (в моём случае, кодом), сравниваемым построчно. Нужно найти те строки, что есть и в первом тексте, и во втором, причём они не должны пересекаться. Это делается на тот случай если в коде есть полностью одинаковые строки (чаще всего комментарии-линии и пустые строки). Я, думаю, так будет проще представить.

Изначально хочу решить задачу составным SQL запросом. Если уж никак не получится, то буду делать через функцию возвращающую таблицу.

И главный вопрос, можете чем либо помочь?
13 ноя 14, 16:44    [16841594]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Konst_One
Member

Откуда:
Сообщений: 11621
с чего вы вдруг решили, что bc - это последовательность, а например bf - не последовательность

серверу ещё нужно коллейшен указать под которым ваши символы будут сортироваться или делайте через циферки, определяющие каждый символ в вашем случае правильно и последовательно (т.е. как вам надо)
13 ноя 14, 16:47    [16841631]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8807
Ang3L,

нам надо угадать - как связаны таблица 1 и таблица2? И т.п.
13 ноя 14, 16:48    [16841642]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Glory
Member

Откуда:
Сообщений: 104751
Ang3L
Основная задача: найти разницу между 2 текстами (в моём случае, кодом

Вот с этого и надо было начинать
https://www.sql.ru/forum/afsearch.aspx?s=???????????&submit=?????&bid=1
13 ноя 14, 16:52    [16841685]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
Konst_One
с чего вы вдруг решили, что bc - это последовательность, а например bf - не последовательность

С того что в "моих" наборах b и c последовательно идут друг за другом (образуя последовательность), а между b и f стоит куча других "символов" (bf в данном случае, множество, но не последовательность).
Но не будем углублятся в математические термины.

Konst_One
серверу ещё нужно коллейшен указать под которым ваши символы будут сортироваться или делайте через циферки, определяющие каждый символ в вашем случае правильно и последовательно (т.е. как вам надо

Честно, это самая последняя проблема над которой я задумываюсь. Пока проблемы сравнить строки не стоит. Кириллицы не будет.

Владислав Колосов
нам надо угадать - как связаны таблица 1 и таблица2? И т.п.

Не надо гадать, тема указывает на проблему.

Glory
https://www.sql.ru/forum/afsearch.aspx?s=???????????&submit=?????&bid=1

Так ссылка отображается у меня сейчас (сижу через удалёнку). Кликнув по ссылке увидел поисковый запрос "Левенштейна", но результат пустой.
По алгоритмам я уже погуглил, начав с любимого algolist'а. Посмотрел метод Вагнера и Фишера, Хиршберга, Ханта-Шиманского, Машека и Патерсона. Метод динамического программирования, я думаю, можно откинуть сразу. Рекурсивный вариант тоже не очень хорош для SQL. Остаётся итеративный. Вот я и подумал, может можно превратить итератиный код в запрос. Запрос точно также итеративно пройдёт все значения. Вот и думаю пока.

Подумалось что можно сделать FULL OUTER JOIN - будет матрица совпадении. Те значения что будут равны, как-нибудь пометить, остальное NULL. А вот дальше что можно сделать...

Короче, общественное мнение сходится на том, как я понял, что запрос можно не делать, а сделать функцию и итеративно проходить все значения в наборах 1 и 2 как указано в алгоритмах? Я чую, что на SQL сервере это будет страсть как неэффективно.
13 ноя 14, 17:29    [16841936]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Glory
Member

Откуда:
Сообщений: 104751
Ang3L
Так ссылка отображается у меня сейчас (сижу через удалёнку). Кликнув по ссылке увидел поисковый запрос "Левенштейна", но результат пустой.

Ну так наберите в поиске форума Левенштейна
13 ноя 14, 17:30    [16841945]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
bcefba
a=
b==
c=
d
e=
f=

Нарисовав такую таблицу (к тому что я описал выше), вырисовывается след. картина. Мне нужны все значения что идут подиагонали (вправо-вниз).
FULL OUTER JOIN - образует данную таблицу.
WHERE Набор1.значение = Набор2.Значение - отбираем те значения что равны.

И остаётся отобрать те что "смежны". Или, возможно, что чётко идут непрерывно по диагонали.
13 ноя 14, 17:38    [16841977]     Ответить | Цитировать Сообщить модератору
 Re: Нахождение наибольшей общей подпоследовательности посредством SQL  [new]
Ang3L
Guest
Вдруг кому понадобится решение.

Есть 2 строки с порядком строк. Нужно найти общие подпоследовательности.

1)
SELECT T1.Значения, T1.Порядок, T2.Порядок, T1.Порядок - T2.Порядок Diff --Диагональ
FROM Набор1 T1
INNER JOIN Набор2 T2
ON T1.Значение = T2.Значение
Ищем последовательности на одной диагонали (те что удовлетворяют функции y = x).

2) Группируем по Diff и выбираем те значения что более 1. Т.е. выбираем цепочки подпоследовательностей на одной диагонали (Опять же, те что удовлетворяют функции y = x).

3) INNER JOIN'им с собой по признаку равенства Diff и неравенства значении, а условие отбора ставим что разница между положениями значении больше -1 или 1. Здесь мы выбрасываем те символы что не смежны по диагонали.

P.S.: Это решение частного случая, когда длина цепочки подпоследовательности более 1. Если кто подскажет как дальше улучшить - буду благодарен.
20 ноя 14, 13:09    [16877936]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить