Детектирование самого подходящего паттерна для последовательности значений / Microsoft SQL Server

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Детектирование самого подходящего паттерна для последовательности значений

11 сообщений из 11, страница 1 из 1

Детектирование самого подходящего паттерна для последовательности значений

#40134047

uaggster

Гость

Коллеги, приветствую!
Помогите решить задачу, не знаю с какой стороны подступиться.
Есть набор паттернов, в виде набора записей, и набор последовательностей, тоже в виде набора записей:

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.

Create table #patterns (id_pattern int not null, n int not Null, v int not null)

insert into #patterns Values
(1, 1, 1),
(1, 2, 1),
(1, 3, 0),
(1, 4, 0),
(1, 5, 0),
(1, 6, 1),
(1, 7, 0),
(1, 8, 1),
(1, 9, 0),
(1, 10, 0),
(2, 1, 1),
(2, 2, 0),
(2, 3, 0),
(2, 4, 1),
(2, 5, 1),
(2, 6, 1),
(2, 7, 1),
(3, 1, 0),
(3, 2, 0),
(3, 3, 0),
(3, 4, 1),
(3, 5, 1),
(3, 6, 0),
(3, 7, 1),
(3, 8, 1),
(3, 9, 0),
(3, 10, 0)

Create table #chains (id_chain int not null, n int not Null, v int not null)

insert into #chains Values
(1, 1, 0), 
(1, 2, 1), 
(1, 3, 1), 
(1, 4, 0), 
(1, 5, 0), 
(2, 1, 1), 
(2, 2, 1), 
(2, 3, 0), 
(2, 4, 1), 
(3, 1, 0), 
(3, 2, 0), 
(3, 3, 1), 
(3, 4, 1), 
(3, 5, 1), 
(3, 6, 0), 
(3, 7, 1)

Необходимо определить, какая цепочка соответствует какому паттерну НЕТОЧНО .
Правила следующие:
0. И паттерны и цепочки - длинные, ~ 1000 символов паттерн, ~100 символов - цепочка
1. При сравнении паттерна и цепочки роль играет только последовательность звеньев. Чем больше звеньев в последовательности совпало - тем больше вес "подходящего" паттерна.
2. Паттерн с цепочкой можно сравнивать начиная с любого символа паттерна, не обязательно с первого.
3. Начинаем сравнивать паттерн с цепочкой начиная с 1 символа паттерна. Если далее совпали N из M символов в цепочке - текущий вес паттерна N
4. Финальный вес паттерна - это максимальный из текущих весов, измеренных со 2, 3, и т.д. символа паттерна при сравнении его цепочкой.
5. Совпавшим считается паттерн с максимальным весом. Если таких несколько - то совпали все.

Т.е:
Паттерн
1010110011000 11101 01101
Цепочка:
11101 1
В этом случае - максимальный вес паттерна - 5 (хотя есть совпадения 1, 2, 3)
Он, очевидно, выигрывает в сравнение с таким паттерном:
10101010101010101010101010101010101010101

Решение нужно какое угодно.
Циклы, курсоры, рекурсия... гм... вызова внешних скриптов хотелось бы избежать...
С какой стороны хоть подступиться к такому?
Похоже на расстояние Дамерау — Левенштейна...

...

Рейтинг:

0 / 0

14.02.2022, 17:56

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134075

aleks222

Участник

Сообщения: 2 564

Рейтинг: 0 / 0

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.

with p as ( select * from #patterns )
   , c as ( select * from #chains )
   , c1 as ( select * from c where n = 1 )
   , b as ( select pid = id_pattern, cid = c1.id_chain, dn = p.n - c1.n, p.v from c1 inner join p on p.v = c1.v )
   , x as ( select pid, cid, dn from b inner join c on b.cid = c.id_chain inner join p on b.pid = p.id_pattern where p.v = c.v and p.n - c.n = b.dn )
   , t as ( select pid, cid, dn, cnt = count(*) from x group by pid, cid, dn )
  select pid, cid, dn, cnt from t where cnt = ( select max(cnt) from t as t1 where t1.pid = t.pid )
    order by pid, cnt desc, cid

...

Рейтинг:

0 / 0

14.02.2022, 19:35

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134090

Akina

Участник

Откуда: Зеленоград, Москва, Россия

Сообщения: 20 644

Рейтинг: 0 / 0

uaggster

Похоже на расстояние Дамерау — Левенштейна...

Близко не лежало. Это - "Поиск максимальной общей подпоследовательности".

uaggster

вызова внешних скриптов хотелось бы избежать...

Как раз внешняя функция, возвращающая длину макс. общей подпоследовательности двух переданных ей строк (паттерн и цепочка), была бы вполне уместна. SQL - хреновый инструмент для такой задачи.

...

Рейтинг:

0 / 0

14.02.2022, 20:16

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134102

invm

Участник

Откуда: Москва

Сообщения: 9 956

Рейтинг: 0 / 0

"В лоб"

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

with
 p (id_pattern, p) as (select id_pattern, string_agg(v, '') within group (order by n) from #patterns group by id_pattern),
 c (id_chain, c) as (select id_chain, string_agg(v, '') within group (order by n) from #chains group by id_chain)
select
 p.*, d.*
from
 p cross apply
 (
  select top (1)
   len(b.c), b.c, c.c
  from
   c cross apply
   (select len(c.c)) a(l) cross apply
   (select top (a.l) left(c.c, row_number() over (order by 1/0)) from master.dbo.spt_values) b(c)
  where
   charindex(b.c, p.p) > 0
  order by
   len(b.c) desc
 ) d(w, sub_c, c)
order by
 p.id_pattern;

...

Рейтинг:

0 / 0

14.02.2022, 21:56

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134130

uaggster

Гость

aleks222

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.

with p as ( select * from #patterns )
   , c as ( select * from #chains )
   , c1 as ( select * from c where n = 1 )
   , b as ( select pid = id_pattern, cid = c1.id_chain, dn = p.n - c1.n, p.v from c1 inner join p on p.v = c1.v )
   , x as ( select pid, cid, dn from b inner join c on b.cid = c.id_chain inner join p on b.pid = p.id_pattern where p.v = c.v and p.n - c.n = b.dn )
   , t as ( select pid, cid, dn, cnt = count(*) from x group by pid, cid, dn )
  select pid, cid, dn, cnt from t where cnt = ( select max(cnt) from t as t1 where t1.pid = t.pid )
    order by pid, cnt desc, cid

Блин, нифига не понял, от слова совсем.
Буду пытаться разобраться. Спасибо.

...

Рейтинг:

0 / 0

15.02.2022, 08:15

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134131

uaggster

Гость

invm

"В лоб"

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

with
 p (id_pattern, p) as (select id_pattern, string_agg(v, '') within group (order by n) from #patterns group by id_pattern),
 c (id_chain, c) as (select id_chain, string_agg(v, '') within group (order by n) from #chains group by id_chain)
select
 p.*, d.*
from
 p cross apply
 (
  select top (1)
   len(b.c), b.c, c.c
  from
   c cross apply
   (select len(c.c)) a(l) cross apply
   (select top (a.l) left(c.c, row_number() over (order by 1/0)) from master.dbo.spt_values) b(c)
  where
   charindex(b.c, p.p) > 0
  order by
   len(b.c) desc
 ) d(w, sub_c, c)
order by
 p.id_pattern;

Тоже не понял. Преобразуем последовательность записей в строку, и для цепочки, и для паттерна, а потом последовательно обрезаем цепочку с конца и ищем charindex обрезка цепочки в паттерне?
Спасибо, буду думать.

...

Рейтинг:

0 / 0

15.02.2022, 08:20

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134414

ValK412

Гость

uaggster,
правильно ли я понял задачу:

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

with pT as (select * from (values (1,'1100010100'),(2,'1001111'),(3,'0001101100')) as t(id_pattern,	p))  -- паттерны из условия задачи
,cT as (select * from (values (1,'01100'),(2,'1101'),(3,'0011101')) as t(id_chain, c) )  -- цепочки из условия задачи  string_agg(v, '')
,cL as (select * from (values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12)) as l(i)) -- для веса, нужна последовательность, равная макс длине цепочки

,match as (
select id_pattern,p as pattern,i,charindex(left(cT.c, i),pT.p) ind,id_chain,cT.c as chain,left(cT.c, i) sub_chain from pT
	left join cL on cl.i<=LEN(pT.p)
	left join cT on len(cT.c)>=i and charindex(left(cT.c, i),pT.p)>=0
	where charindex(left(cT.c, i),pT.p)>0
)
select id_pattern,pattern,id_chain,chain, max(i) as weight ,left(chain, max(i)) as  sub_chain 
	from match
	group by id_pattern,pattern,id_chain,chain
	order by id_pattern,id_chain

id_pattern pattern id_chain chain weight sub_chain1 1100010100 1 01100 2 011 1100010100 2 1101 3 1101 1100010100 3 0011101 3 0012 1001111 1 01100 3 0112 1001111 2 1101 2 112 1001111 3 0011101 5 001113 0001101100 1 01100 5 011003 0001101100 2 1101 4 11013 0001101100 3 0011101 4 0011
как бы это удалить)

...

Рейтинг:

0 / 0

16.02.2022, 00:51

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134422

aleks222

Участник

Сообщения: 2 564

Рейтинг: 0 / 0

ValK412

uaggster,
правильно ли я понял задачу:

Ты, главное, не переживай. ТС сам ничо не понимает.

...

Рейтинг:

0 / 0

16.02.2022, 06:09

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134471

Владислав Колосов

Участник

Сообщения: 9 447

Рейтинг: 0 / 0

uaggster,

цепочку надо нарезать на элементы длиной от 1 до длины цепочки и подсчитывать количество совпавших элементов в паттерне.

...

Рейтинг:

0 / 0

16.02.2022, 11:42

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134510

uaggster

Гость

aleks222

ValK412

uaggster,
правильно ли я понял задачу:

Ты, главное, не переживай. ТС сам ничо не понимает.

Смех смехом, но именно так. Пока приостановилось, жду, пока бизнес прочихается.
Решение invm подошло прямо в лоб (к тому, что просили), но результат почему-то не устроил. Выясняю почему.

...

Рейтинг:

0 / 0

16.02.2022, 13:58

| Ответить | Цитировать | Написать

Детектирование самого подходящего паттерна для последовательности значений

#40134514

Владислав Колосов

Участник

Сообщения: 9 447

Рейтинг: 0 / 0

uaggster,

задача напоминает расшифровку генома.

...

Рейтинг:

0 / 0

16.02.2022, 14:19

| Ответить | Цитировать | Написать

11 сообщений из 11, страница 1 из 1

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

Start [/forum/topic.php?fid=46&msg=40134102&tid=1683831]:	0ms
get settings:	6ms
get forum list:	6ms
check forum access:	1ms
check topic access:	1ms
track hit:	39ms
get topic data:	6ms
get forum data:	1ms
get page messages:	215ms
get tp. blocked users:	1ms
others:	280ms

total:	556ms