Получение числового / нормализованного представления строк для помощи в «естественном порядке сортировки» заголовков в БД

Question

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

Пара причин для этого: во-первых, я хотел бы более естественный порядок, чем простой порядок, предлагаемый сервером БД, где такие вещи, как «The» и «A» и знаки препинания игнорируются в начале, а числа обрабатываются «естественно».

Во-вторых, это для индекса с большим количеством перестановок - он сэкономит место и, возможно, время при обходе индекса с большим количеством строк.

Мне нужен алгоритм перевода строки в это числовое значение или, я полагаю, нормализованное строковое значение.

Я использую PHP и MySQL.

Боюсь, что «извлечь все из БД и отсортировать в PHP с использованием natcasesort ()» не является решением для данной конкретной ситуации, так как я хотел бы получить строки (используя order by и group by) в отсортированном заказ до того, как они доберутся до условия соединения или ограничения. Спасибо.

Изменить:

Спасибо за ответы. Мне просто пришло в голову, что тот факт, что мое приложение использует UTF-8, весьма актуален. С учетом сказанного, я думаю, что практичность представления начальной части строки в упакованной / числовой форме - это растяжение, может быть, просто какая-то нормализованная форма (все сложено регистром, числа с нулем и как можно больше символов) нормализуется до их корня, т. е. от а до а) будет уместно.

Answer 1

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

Напомним, что я хотел сохранить представления строк таким образом, чтобы при извлечении в двоичном порядке все, что я сохранял для «8 миль», было отсортировано до того, что я сохранил для «101 далмаций».

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

Итак, «8» становится «18», а «101» становится «3101». Это добавляет некоторую избыточность к числу, поскольку вы используете больше цифр, чем вам нужно, и некоторые значения не будут существовать, но теперь у них есть свойство, что двоичная сортировка будет сортировать числа в числовом порядке. «101» предварительно отсортировалось бы до «8», что было нежелательно. После добавления этой дополнительной цифры «18» сортируется перед «3101».

Примечание: если номер длиной 9 или более цифр, я добавляю две цифры к началу: количество цифр в числе минус 9, затем 9, затем номер. Это позволяет использовать цифры до 18 цифр, что достаточно для меня.

Я также нормализую строку и другими способами - все в нижнем регистре, символы Юникода будут переведены в ближайший эквивалент ascii, а 'a', 'an' и 'the' будут удалены, если они первое слово.

Я отказался от превращения строки в одно большое числовое значение; это все еще строка, просто она не предназначена для чтения людьми.

Answer 2

Часть "с точностью до первых букв X или около того" имеет решающее значение, поскольку абсолютно точное назначение чисел невозможно. Чтобы увидеть это, предположим для конкретности, что ваш столбец title равен varchar(50), и вы хотите использовать 32-битный столбец integer sort_order. Тогда вы могли бы хранить (255 ^ 51 - 1) разных заголовков, для каждого из которых требовалось бы различное значение sort_order, но есть только 2 ^ 32 разных значения sort_order для обхода. Даже если бы вы сказали, что никогда не добавите более 2 ^ 32 строк, вам нужно заранее знать, какие заголовки у них будут, чтобы создать схему, позволяющую избежать переназначения всех значений sort_order каждый раз, когда строка была вставлена.

Хотя «теоретически совершенное» решение невозможно, все же возможно получить практичную «приближенную» систему, которая должна работать с идеальной точностью до многих миллионов строк. Самый простой способ - использовать тип с плавающей точкой. Сначала перечислите строки в отсортированном порядке и присвойте первой строке значение sort_order 1,0, второй - значение 2,0 и т. Д. Затем всякий раз, когда вставляется строка, задайте ее sort_order в средней точке (то есть в среднем) строк по обе стороны в отсортированном порядке. Если новая добавленная строка находится до (или после) всех существующих строк, просто установите ее на 1 меньше (или больше) предыдущего минимального (или максимального) значения sort_order.

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