Гуманизированная или натуральная сортировка чисел из смешанных строк из слов и цифр

Question

В ответ на этот вопрос Sivaram Chintalapudi меня интересует, практично ли в PostgreSQL выполнять естественную или "гуманизированную" сортировку строк, которые содержат смесь многозначных чисел и слов / букв. шаблон слов и чисел в строках, и в строке может быть более одного многозначного числа.

Единственное место, где я обычно это делал, - это Finder в Mac OS, который сортирует имена файлов, содержащие смешанные числа и слова, естественно, ставя "20" после "3", а не перед ним.

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

'AAA2fred' станет ('AAA',2,'fred') а также 'AAA10bob' станет ('AAA',10,'bob'), Затем они могут быть отсортированы по желанию:

regress=# WITH dat AS ( VALUES ('AAA',2,'fred'), ('AAA',10,'bob') )
regress-# SELECT dat FROM dat ORDER BY dat;
     dat      
--------------
 (AAA,2,fred)
 (AAA,10,bob)
(2 rows)

по сравнению с обычным порядком сортировки строк:

regress=# WITH dat AS ( VALUES ('AAA2fred'), ('AAA10bob') )
regress-# SELECT dat FROM dat ORDER BY dat;
    dat     
------------
 (AAA10bob)
 (AAA2fred)
(2 rows)

Однако подход сравнения записей не обобщается, потому что Pg не будет сравнивать конструкции ROW(..) или записи с неодинаковым количеством записей.

Учитывая данные примера в этом SQLFiddle, сопоставление по умолчанию en_AU.UTF-8 производит порядок:

1A, 10A, 2A, AAA10B, AAA11B, AAA1BB, AAA20B, AAA21B, X10C10, X10C2, X1C1, X1C10, X1C3, X1C30, X1C4, X2C1

но я хочу:

1A, 2A, 10A, AAA1BB, AAA10B, AAA11B, AAA20B, AAA21B, X1C1, X1C3, X1C4, X1C10, X1C30, X2C1, X10C10, X10C2

В данный момент я работаю с PostgreSQL 9.1, но предложения только для 9.2 подойдут. Меня интересуют советы о том, как создать эффективный метод разделения строк и как сравнить полученные результирующие данные в описанном порядке чередования строк и чисел. Или, конечно, на совершенно разных и лучших подходах, которые не требуют разделения строк.

PostgreSQL, похоже, не поддерживает функции компаратора, иначе это можно сделать довольно легко с помощью рекурсивного компаратора и чего-то подобного ORDER USING comparator_fn и comparator(text,text) функция. Увы, этот синтаксис мнимый.

Обновление: пост в блоге по теме.

Answer 1

Основываясь на ваших тестовых данных, но это работает с произвольными данными:

CREATE TYPE ai AS (a text, i int); -- Could also be a table or even a temp table

SELECT data
FROM (
    SELECT ctid, data, regexp_matches(data, '(\D*)(\d*)', 'g') AS x
    FROM   alnum
    ) x
GROUP  BY ctid, data   -- ctid as stand-in for a missing pk
ORDER  BY regexp_replace (left(data, 1), '[0-9]', '0')
        , array_agg(ROW(x[1], CASE x[2] WHEN '' THEN '0' ELSE x[2] END)::ai)
        , data         -- for special case of trailing 0

Протестировано с PostgreSQL 9.1.5.

• Хитрость заключается в том, чтобы сформировать массив ai - ai будучи составным типом, состоящим из text и integer колонка. Это работает с различным количеством элементов.

• regexp_matches () с шаблоном (\D*)(\d*) и g Опция возвращает одну строку для каждой комбинации букв и цифр, плюс одну строку в конце. С начальными цифрами мы получаем пустой элемент в начале для части письма.

• добавлять regexp_replace (left(data, 1), '[0-9]', '0') как первый ORDER BY пункт, чтобы заботиться о ведущих цифрах и пустых строках.

• Заменить пустые строки на 0 для integer часть.

- Если специальные символы, такие как {}()"', может произойти, вы должны избежать тех, кто соответственно.

• Предложение @ Крейга использовать ROW выражение заботится об этом.

• Если NULL может произойти, вы должны были бы в особом случае это - или использовать весь Shebang в STRICT Функция, как @Craig предлагает.

Кстати, это не будет выполняться в sqlfiddle, но в моем кластере БД. JDBC не до этого. sqlfiddle жалуется:

Метод org.postgresql.jdbc3.Jdbc3Array.getArrayImpl(long,int,Map) еще не реализован.

Answer 2

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

CREATE OR REPLACE FUNCTION human_sort(text)
  RETURNS text[] AS
$BODY$   
  /* Split the input text into contiguous chunks where no numbers appear,
     and contiguous chunks of only numbers. For the numbers, add leading 
     zeros to 20 digits, so we can use one text array, but sort the 
     numbers as if they were big integers.

       For example, human_sort('Run 12 Miles') gives
            {'Run ', '00000000000000000012', ' Miles'}
  */
  select array_agg(
    case
      when a.match_array[1]::text is not null 
        then a.match_array[1]::text         
      else lpad(a.match_array[2]::text, 20::int, '0'::text)::text                                      
    end::text)
    from (
      select regexp_matches(
        case when $1 = '' then null else $1 end, E'(\\D+)|(\\d+)', 'g'
      ) AS match_array      
    ) AS a  
$BODY$
  LANGUAGE sql IMMUTABLE;

протестирован для работы на Postgres 8.3.18 и 9.3.5

• Нет рекурсии, должно быть быстрее, чем рекурсивные решения
• Может использоваться только в порядке, указанном в предложении, не нужно иметь дело с первичным ключом или ctid
• Работает для любого выбора (даже не нужен PK или Ctid)
• Проще, чем некоторые другие решения, должно быть легче расширять и поддерживать
• Подходит для использования в функциональном индексе для улучшения производительности
• Работает на Postgres v8.3 или выше
• Позволяет неограниченное количество чередований текста / номера на входе
• Использует только одно регулярное выражение, должно быть быстрее, чем версии с несколькими регулярными выражениями
• Номера более 20 цифр упорядочены по первым 20 цифрам

Вот пример использования:

select * from (values 
  ('Books 1', 9),
  ('Book 20 Chapter 1', 8),
  ('Book 3 Suffix 1', 7),
  ('Book 3 Chapter 20', 6),
  ('Book 3 Chapter 2', 5),
  ('Book 3 Chapter 1', 4),
  ('Book 1 Chapter 20', 3),
  ('Book 1 Chapter 3', 2),
  ('Book 1 Chapter 1', 1),
  ('', 0),
  (null::text, 0)
) as a(name, sort)
order by human_sort(a.name)
-----------------------------
|name               |  sort |
-----------------------------
|                   |   0   |
|                   |   0   |
|Book 1 Chapter 1   |   1   |
|Book 1 Chapter 3   |   2   |
|Book 1 Chapter 20  |   3   |
|Book 3 Chapter 1   |   4   |
|Book 3 Chapter 2   |   5   |
|Book 3 Chapter 20  |   6   |
|Book 3 Suffix 1    |   7   |
|Book 20 Chapter 1  |   8   |
|Books 1            |   9   |
-----------------------------

Answer 3

Добавляю этот ответ поздно, потому что похоже, что все остальные разворачиваются в массивы или что-то подобное. Казалось чрезмерным.

CREATE FUNCTION rr(text,int) RETURNS text AS $$
SELECT regexp_replace(
    regexp_replace($1, '[0-9]+', repeat('0',$2) || '\&', 'g'), 
    '[0-9]*([0-9]{' || $2 || '})', 
    '\1', 
    'g'
)
$$ LANGUAGE sql;

SELECT t,rr(t,9) FROM mixed ORDER BY t;
      t       |             rr              
--------------+-----------------------------
 AAA02free    | AAA000000002free
 AAA10bob     | AAA000000010bob
 AAA2bbb03boo | AAA000000002bbb000000003boo
 AAA2bbb3baa  | AAA000000002bbb000000003baa
 AAA2fred     | AAA000000002fred
(5 rows)

(reverse-i-search)`OD': SELECT crypt('richpass','$2$08$aJ9ko0uKa^C1krIbdValZ.dUH8D0R0dj8mqte0Xw2FjImP5B86ugC');
richardh=> 
richardh=> SELECT t,rr(t,9) FROM mixed ORDER BY rr(t,9);
      t       |             rr              
--------------+-----------------------------
 AAA2bbb3baa  | AAA000000002bbb000000003baa
 AAA2bbb03boo | AAA000000002bbb000000003boo
 AAA2fred     | AAA000000002fred
 AAA02free    | AAA000000002free
 AAA10bob     | AAA000000010bob
(5 rows)

Я не утверждаю, что два регулярных выражения являются наиболее эффективным способом сделать это, но rr() является неизменным (для фиксированной длины), поэтому вы можете индексировать его. Ох - это 9,1

Конечно, с помощью plperl вы можете просто оценить замену, чтобы дополнить / обрезать ее за один раз. Но тогда с Perl у вас всегда есть просто-еще-один вариант (TM), чем любой другой подход:-)

Answer 4

Следующая функция разбивает строку на массив (слово, число) пар произвольной длины. Если строка начинается с числа, то первая запись будет иметь NULL слово.

CREATE TYPE alnumpair AS (wordpart text,numpart integer);

CREATE OR REPLACE FUNCTION regexp_split_numstring_depth_pairs(instr text)
RETURNS alnumpair[] AS $$
WITH x(match) AS (SELECT regexp_matches($1, '(\D*)(\d+)(.*)'))
SELECT
  ARRAY[(CASE WHEN match[1] = '' THEN '0' ELSE match[1] END, match[2])::alnumpair] || (CASE 
  WHEN match[3] = '' THEN
    ARRAY[]::alnumpair[]
  ELSE 
    regexp_split_numstring_depth_pairs(match[3]) 
  END)
FROM x;$$ LANGUAGE 'sql' IMMUTABLE;

разрешение вступить в игру сортировки составных типов PostgreSQL:

SELECT data FROM alnum ORDER BY regexp_split_numstring_depth_pairs(data);

и получение ожидаемого результата в соответствии с этим SQLFiddle. Я принял замену Эрвина 0 для пустой строки во всех строках, начинающихся с числа, так что числа сортируются первыми; это чище, чем использовать ORDER BY left(data,1), regexp_split_numstring_depth_pairs(data),

Хотя эта функция, вероятно, ужасно медленная, она может, по крайней мере, использоваться в индексе выражений.

Это было весело!

Answer 5

create table dat(val text)
insert into dat ( VALUES ('BBB0adam'), ('AAA10fred'), ('AAA2fred'), ('AAA2bob') );

select 
  array_agg( case when z.x[1] ~ E'\\d' then lpad(z.x[1],10,'0') else z.x[1] end ) alnum_key
from (
  SELECT ctid, regexp_matches(dat.val, E'(\\D+|\\d+)','g') as x
  from dat
) z
group by z.ctid
order by alnum_key;

       alnum_key       
-----------------------
 {AAA,0000000002,bob}
 {AAA,0000000002,fred}
 {AAA,0000000010,fred}
 {BBB,0000000000,adam}

Работал над этим почти час и отправил, не глядя - я вижу, Эрвин прибыл в аналогичное место. Натолкнулся на ту же проблему "не удалось найти тип массива для типа данных text[]", как @Clodoaldo. У меня было много проблем с выполнением процедуры очистки, чтобы не агрегировать все строки, пока я не подумал о группировке по ctid (что на самом деле похоже на обман - и не работает на таблице псевдо, как в примере OP WITH dat AS ( VALUES ('AAA2fred'), ('AAA10bob') ) ...). Было бы лучше, если бы array_agg могла принимать подвыбор, производящий множество.

Answer 6

Я не гуру RegEx, но я могу работать до некоторой степени. Достаточно произвести этот ответ.

Он будет обрабатывать до 2 числовых значений в контенте. Я не думаю, что OSX идет дальше, если он даже обрабатывает 2.

WITH parted AS (
  select data,
         substring(data from '([A-Za-z]+).*') part1,
         substring('a'||data from '[A-Za-z]+([0-9]+).*') part2,
         substring('a'||data from '[A-Za-z]+[0-9]+([A-Za-z]+).*') part3,
         substring('a'||data from '[A-Za-z]+[0-9]+[A-Za-z]+([0-9]+).*') part4
    from alnum
)
  select data
    from parted
order by part1,
         cast(part2 as int),
         part3,
         cast(part4 as int),
         data;

SQLFiddle

Answer 7

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

      create function natsort(s text) returns text immutable language sql as $$
  select string_agg(r[1] || E'\x01' || lpad(r[2], 20, '0'), '')
  from regexp_matches(s, '(\D*)(\d*)', 'g') r;
$$;

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

Примечание: если вы ожидаете, что числа содержат больше цифр, вам придется заменить жестко заданную максимальную длину 20в функции подходящей большей длины. Обратите внимание, что это напрямую повлияет на длину результирующих строк, поэтому не делайте это значение больше, чем необходимо.