Сокращение строк, которое остается уникальным

Question

У меня есть уникальный список строк (оригинальной идеей были имена столбцов в таблице).Задача состоит в том, чтобы выполнить максимально возможное сокращение списка, чтобы список оставался четким.

Например, AAA, AB можно сократить до AA, AB.(Но не до A, AB - поскольку A может быть префиксом как AAA, так и AB).AAAA, BAAAA можно сократить до A, B.Но A1, A2 не может быть сокращено совсем.

Вот примерные данные

create table tab as 
select 'AAA' col from dual union all
select 'AABA' col from dual union all
select 'COL1' col from dual union all
select 'COL21' col from dual union all
select 'AAAAAA' col from dual union all
select 'BBAA' col from dual union all
select 'BAAAA' col from dual union all
select 'AB' col from dual;

Ожидаемый результат:

COL    ABR_COL                
------ ------------------------
AAA    AAA                      
AAAAAA AAAA                     
AABA   AAB                      
AB     AB                       
BAAAA  BA                       
BBAA   BB                       
COL1   COL1                     
COL21  COL2        

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

Кстати, в r есть аналогичная функция, называемая abbreviate, но я ищу решение SQL.Предпочтительные Oracle решения для других СУБД приветствуются.

Answer 1

Я нашел второй подход, не добавленный к первому ответу, так как он короче и отличается.Шаги следующие:

1. Рассчитать все потенциальные сокращения для каждого имени, рекурсивно

SQL

  select
      col
    , col as abbr
  from tab
  union all
  select
    col
  , substr(abbr, 1, length(abbr)-1 ) as abbr
  from potential_abbreviations a
  where length(abbr) > 1

Результаты

 col    abbr
 --- -------
 AAA    AAA
 AAA    AA
 AAA    A
 ...

Затем вычислите конфликты между сокращениями.Также следите за именем столбца, который привел к этому сокращению.Мы хотим сохранить только сокращения, которые не вызывают конфликтов, поэтому агрегат min() не имеет значения.

SQL

select
    abbr
  , count(*) as conflicts
  , min(col) as best_candidate
  from potential_abbreviations
 group by abbr
having count(*) = 1

Результат

ABBR    CONFLICTS BEST_CANDIDATE
------- --------- ---------------
AAAA    1         AAAAAA
AAAAA   1         AAAAAA
AAAAAA  1         AAAAAA
AAB     1         AABA
AABA    1         AABA
...

Наконец, сделайте левое соединение потенциальных сокращений с лучшими бесконфликтными кандидатами и просто используйте имя столбца, если не было бесконфликтного разрешения:

SQL

select
    p.col as col
  , nvl(min(c.abbr), p.col) as abbr
  from potential_abbreviations p
  left join conflict_free c on p.col = c.best_candidate
 where c.conflicts = 1 or p.abbr = p.col
 group by p.col
  order by col, abbr

Полный SQL

with potential_abbreviations(col,abbr) as (
  select
      col
    , col as abbr
  from tab
  union all
  select
    col
  , substr(abbr, 1, length(abbr)-1 ) as abbr
  from potential_abbreviations a
 where length(abbr) > 1
)
, conflict_free as (
    select
        abbr
      , count(*) as conflicts
      , min(col) as best_candidate
      from potential_abbreviations
     group by abbr
    having count(*) = 1
)
select
    p.col as col
  -- , c.best_candidate
  , nvl(min(c.abbr), p.col) as abbr
  -- , min(c.abbr) over (partition by c.best_candidate) shortest
  from potential_abbreviations p
  left join conflict_free c on p.col = c.best_candidate
 where c.conflicts = 1 or p.abbr = p.col
 group by p.col, c.best_candidate
 order by col, abbr

Результат

COL     ABBR
------- ----
AAA     AAA
AAAAAA  AAAA
AABA    AAB
AB      AB
AC1     AC
AD      AD
BAAAA   BA
BBAA    BB
COL1    COL1
COL21   COL2

Скрипка SQL

Примечание: Для Postgresql рекурсивный CTE должен быть with recursive в то время как Oracle там вообще не нравится слово recursive.

Answer 2

Я бы сделал фильтрацию в рекурсивном CTE:

with potential_abbreviations(col, abbr, lev) as (
      select col, col as abbr, 1 as lev
      from tab
      union all
      select pa.col, substr(pa.abbr, 1, length(pa.abbr) - 1) as abbr, lev + 1
      from potential_abbreviations pa
      where length(abbr) > 1 and
            not exists (select 1
                        from tab
                        where tab.col like substr(pa.abbr, 1, length(pa.abbr) - 1) || '%' and
                              tab.col <> pa.col
                       )
     )
select pa.col, pa.abbr
from (select pa.*, row_number() over (partition by pa.col order by pa.lev desc) as seqnum
      from potential_abbreviations pa
     ) pa
where seqnum = 1

Здесь - это дБ <> скрипка.

lev строго не требуется,Вы можете использовать length(abbr) desc в order by.Но я обычно включаю счетчик рекурсии, когда использую рекурсивные CTE, так что это привычка.

Выполнение дополнительного сравнения в CTE может выглядеть сложнее, но это упрощает выполнение - рекурсия останавливается на правильномзначение.

Это также проверяется на уникальных однобуквенных значениях col.

Answer 3

Это на самом деле возможно при использовании рекурсивного CTE.Я действительно не получаю его короче, чем три подзапроса (плюс один запрос), но по крайней мере это не ограничено длиной строки.Шаги примерно таковы:

1. Рассчитать все потенциальные сокращения с помощью рекурсивного CTE.При этом выбираются все имена столбцов, а затем имена столбцов сокращаются на одну букву рекурсивно:

Таблица:

 col    abbr
 --- -------
 AAA    AAA
 AAA    AA
 AAA    A
 ...

Для каждого сокращения посчитайте, как часто оно встречается

Таблица

ABBR    CONFLICT
----    --------
AA      3
AAA     2
AABA    1
...

Выберите аббревиатуры, которые являются уникальными самыми короткими, а также аббревиатуры, которые являются только самим именем столбца, и оцените их по длине аббревиатуры.В этом примере вы видите, что AAA конфликтует с каким-то другим сокращением, но все же должно быть выбрано, так как оно равно не сокращенному имени.

Таблица

COL     ABBR    CONFLICT    POS
-------------------------------
AAA     AAA     2           1
AAAAAA  AAAA    1           1
AAAAAA  AAAAA   1           2
AAAAAA  AAAAAA  1           3
AABA    AAB     1           1
...

Выберите первое ранжированное сокращение (или имя самого столбца) для каждого столбца.

Таблица

COL     ABBR    POS
-------------------
AAA     AAA     1
AAAAAA  AAAA    1
AABA    AAB     1
...

Полный SQL

Это приводит к следующемуSQL, с вышеуказанными шагами в качестве CTE:

with potential_abbreviations(col,abbr) as (
  select
      col
    , col as abbr
  from tab
  union all
  select
    col
  , substr(abbr, 1, length(abbr)-1 ) as abbr
  from potential_abbreviations
  where length(abbr) > 1
)
, abbreviation_counts as (
  select abbr
       , count(*) as conflict
  from potential_abbreviations
  group by abbr
)
, all_unique_abbreviations(col,abbr,conflict,pos) as (
select
    p.col
  , p.abbr
  , conflict
  , rank() over (partition by col order by p.abbr) as pos
  from potential_abbreviations p
    join abbreviation_counts c on p.abbr = c.abbr
    where conflict = 1 or p.col = p.abbr
)
select col, abbr, pos
from all_unique_abbreviations
where pos = 1
 order by col, abbr

Результат

COL     ABBR
------- ----
AAA     AAA
AAAAAA  AAAA
AABA    AAB
AB      AB
AC1     AC
AD      AD
BAAAA   BA
BBAA    BB
COL1    COL1
COL21   COL2

SQL Fiddle