Строковое кодирование примитивных типов, сохраняющих лексикографический порядок - PullRequest
Новая
       7

Строковое кодирование примитивных типов, сохраняющих лексикографический порядок

5 голосов
/ 19 ноября 2009

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

В идеале я ищу библиотеку C ++, но и другие языки тоже хороши. Также можно предположить, что формат не должен быть закодирован в самой строке (то есть, если это int64 / string / float, тогда закодированная строка не должна кодировать эту информацию, достаточно только кодирования данных).

Ответы [ 4 ]

9 голосов
/ 29 июля 2010

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

http://www.zanopha.com/docs/elen.pdf

2 голосов
/ 19 февраля 2013

Кстати ... В SimpleDB Amazon Web Service все данные хранятся в виде строк. Его компараторы select используют лексикографическое упорядочение. AWS предоставляет служебные функции для кодирования различных типов. Например, целые числа кодируются, зная диапазон априорных целых чисел, и корректируются с помощью дополнения нулями и смещений (например, для отрицательных целых чисел). Конечно, вы могли бы дать ему наихудший возможный диапазон.

См. «Запрос 201: Советы и рекомендации для Amazon SimpleDB Query» - http://aws.amazon.com/articles/1232

http://typica.s3.amazonaws.com/com/xerox/amazonws/sdb/DataUtils.html

2 голосов
/ 08 июля 2012

У меня была проблема преобразования целых и длинных строк в строки, которые сохраняют порядок. А поскольку я работал на Java, у меня были только подписанные типы.

Мой алгоритм был очень прост:

  1. Отразить бит знака (toEncode ^ Long.MAX_VALUE для длинных), в противном случае отрицательные числа больше положительных чисел.
  2. Выполнить модифицированное кодирование base64 байтов. К сожалению, обычная кодировка base64 не сохраняет порядок; специальные символы (+ и /) идут после цифр, следующих за символами. Это полностью от ASCII. Моя модифицированная кодировка просто использует порядок ASCII. (Чтобы было ясно, что это не обычный base64, я изменил специальные символы на - и _ с ~ в качестве отступа. Они все еще могут использоваться в URL, что было еще одним ограничением, которое у меня было.)
0 голосов
/ 19 ноября 2009

Просто напишите числовые значения в фиксированной ширине столбца с начальными нулями и строками как обычно. Так вот так: 

0.1 -> 0000000.1000000
123 -> 0000123.0000000
foo -> foo
X   -> X

Затем вы можете сортировать как текст (например, Unix sort без -n). Как насчет этого?

...