Как найти самый длинный префикс среди строк и сгруппировать по нему?

Question

[prochanev]

Всем привет! Уже заспамил весь гугл, но, то что он выдал, не смог применить.
Смог только найти, что подобная задача называется Longest common prefix(LCP)

Есть таблица example:

+----+-----------+------------------------+
| id | parent_id | path                   |
+----+-----------+------------------------+
| 1  | 7         | val10/val11/val12/val3 |
| 2  | 7         | val1/val2/val3/val5    |
| 3  | 7         | val1/val2/val3/val6    |
| 4  | 7         | val1/val2/val3/val7    |
| 5  | 7         | val1/val2/val3/val8    |
| 6  | 7         | val1/val2/val3/val9    |
+----+-----------+------------------------+

Как сгруппировать строки по самому длинному префиксу в столбце path относительно parent_id? Под префиксом имеется ввиду повторяющаяся часть строки начиная с начала.

Для таблицы выше вывод должен быть:

+-----------+------------------------+-------+
| parent_id | path                   | count |
+-----------+------------------------+-------+
| 7         | val1/val2/val3         | 5     |
| 7         | val10/val11/val12/val3 | 1     |
+-----------+------------------------+-------+

для генерации примера:

create table example (id int, parent_id int, path varchar(50));

insert into example
select 1, 7, 'val10/val11/val12/val3'
union select 2, 7, 'val1/val2/val3/val5'
union select 3, 7, 'val1/val2/val3/val6'
union select 4, 7, 'val1/val2/val3/val7'
union select 5, 7, 'val1/val2/val3/val8'
union select 6, 7, 'val1/val2/val3/val9'

Возможно, кто-то встречался с такой задачей, отзовитесь! )

Comments

[prochanev]

Добился нужного результата используя функцию lca, по сути это и есть longest common prefix из расширения ltree для Postgresql

Спасибо за участие, тем, кто помогал.

Answer 1

[Константин Цветков]

ltree.

Comments

[prochanev]

Спасибо за наводку!

Answer 2

[d-stream]

гм,,, select path, count(*) from example group by path ?
или я что-то в условиях не совсем понял?

Comments

[prochanev]

Не совсем, возможно я плохо объяснил. У записей с id 2 - 6 есть общий кусочек val1/val2/val3, вот по нем и нужно сгруппировать, а вот у записи с id 1 строка не содержит префикс val1/val2/val3 по этому в ожидаемом выводе эта строка стоит отдельно.

При вашем варианте на против каждой строки будет стоять 1, т.к. они все разные.

Спасибо за отклик!

[d-stream]

prochanev, а можно поширше развернуть прикладной смысл этого?
Я так подозреваю что val1/val2/val3/val8 - это уже "схлопнутое" и в исходном [где-то] это скорее всего нечто "в ширину" типа битовых полей
is_val1
is_val2
...
isval100

Если - да - то я бы разворачивал в такое

[prochanev]

Вообще это просто структура подразделений, и в точке с parent_Id=7 нужно найти наиболее подходящее подразделение. Мне тут по смыслу подошёл наибольший общий префикс. В исходном виде это дерево parent-child, только проблема в том, что в точках подобных parent_id = 7 нету подразделения и мне нужно его "определить" исходя из дочерних.

[d-stream]

ТО есть для val1/val2/val3/val8 это

val1
    val2
       val3 
          val8

???

Типа для каждого id - есть кусочек из некоей глобальной иерархии без явной начальной токи???

[prochanev]

Смотрите
1. Есть таблица с иерархией подразделений, тут дерево

таблица departments:

+----+-----------+------+
| id | parent_id | name |
+----+-----------+------+

2. Есть таблица с сущностями, у которых есть признак department_id

+----+-----------+---------------+
| id | parent_id | department_id |
+----+-----------+---------------+

В "таблице с сущностями" у тех id, которые входят в список parent_id в поле department_id и parent_id пусто в моем примере это сущность с id = 7

У остальных сущностей есть признак department_id (в моем примере это id с 1 - 6)

Дак вот, задача у сущности с id = 7 найти наиболее подходящее подразделение исходя из наименований дочерних.

Имена 'val1/val2/val3/val5' это просто свернутое дерево подразделений.

Надеюсь понятно расписал :)

[d-stream]

Да, вроде мысль уловил. То есть у id=7 "потерялись" цепочки.
Правильно ли я понимаю что добытые цепочки гарантировано есть неразрывный фрагмент из какого-то бОльшего (общего дерева)?

Если да - то есть мысль:
- предположим что потряные цепочки - конечные - то есть хвосты совпадают
- строим из главного дерева иерархий все возможные цепочки
- ищем совпадения реверсивно
то есть в полной иерархии есть цепочка
a0/b1/c2/d3/e4/f5 - реверсивно - f5/e4/d3/c2/b1/a0
а "обрезок" d3/e4/f5 - реверсивно f5/e4/d3

тогда по этому обрезку получится найти исходную цепочку...

если предположение про совпадающие хвосты неверно - придется в цикле "укорачивать" полные цепочки и повторять поиск

Answer 3

[mayton2019]

Как по мне - задача поставлена неверно. Или не хватает доп-условий. Например я считаю что общий префикс должен быть такой.

+-----------+------------------------+-------+
| parent_id | path                   | count |
+-----------+------------------------+-------+
| 7         | val1                   | 6     |
+-----------+------------------------+-------+

Comments

[prochanev]

Согласен с этим замечанием, тут должен быть префикс с учётом разделителя “/“. Т.е. сравнение идёт по подстрокам с разделителем “/“.

[mayton2019]

Уже лучше. Но недостаточно. Я по прежнему могу указать исходные данные в которых будет много вариантов префиксов.