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

Question

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

"book" -> 50000
"car"  -> 60000
"card" -> 65000
"a longer string" -> 15000
"another long string" -> 15500
"awesome" -> 16000

Как функция это должно быть что-то вроде: f (x) = y, так что для любого x1 f (x1)

Если входной набор x конечен, то я всегда могу выполнить сортировку и назначить правильные значения, но я ищу что-то общее для неограниченного входного набора для x.

Answer 1

Если вам требуется, чтобы f отображалось в целые числа, это невозможно.

Предположим, что есть такая карта f. Рассмотрим строки a, aa, aaa и т. Д. Рассмотрим значения f(a), f(aa), f(aaa) и т. Д. Поскольку мы требуем, чтобы f(a) < f(aa) < f(aaa) < ... мы видели, что f(a_n) стремится к бесконечности как n стремится к бесконечности; здесь я использую очевидную запись, что a_n - это символ a, повторенный n раз. Теперь рассмотрим строку b. Мы требуем, чтобы f(a_n) < f(b) для всех n. Но f(b) - это некоторое конечное целое число, и мы только что показали, что f(a_n) уходит в бесконечность. У нас есть противоречие. Такая карта невозможна.

Может, ты расскажешь нам, зачем тебе это? Это довольно абстрактно, и мы можем предложить что-то более подходящее. Кроме того, не обязательно беспокоиться о решении "это" вообще. ЯГНИ и все такое.

Answer 2

Вы запрашиваете временную приостановку принципа голубиного отверстия (http://en.wikipedia.org/wiki/Pigeonhole_principle).

Строки - это голуби, числа - это дыры. Голубей больше, чем отверстий, поэтому вы не можете поместить каждого голубя в отдельное отверстие.

Answer 3

Как следствие ответа Джейсона , если вы можете сопоставить свои строки с рациональными числами, такое отображение очень простое. Если code(c) является ASCII-кодом символа c, а s[i] является i -ым символом в строке s, просто выполните суммирование следующим образом:

result <- 0
scale  <- 1
for i from 1 to length(s) 
  scale <- scale / 26
  index <- (1 + code(s[i]) - code('a'))
  result <- result + index / scale
end for
return result

Это сопоставляет пустую строку с 0, а все остальные строки с рациональным числом от 0 до 1, сохраняя лексикографический порядок. Если у вас есть десятичные числа с плавающей запятой произвольной точности, вы можете заменить деление на степени 26 степенями 100 и при этом иметь точно представимые числа; двоичные числа с плавающей точкой произвольной точности можно разделить на степени 32.

Answer 4

Может быть Radix Tree - это то, что вы ищете?

радикальное дерево, дерево / дерево Патриция, или Критическое битовое дерево - это специализированный набор структура данных на основе дерева, которое используется для хранения набора строк. В контраст с обычным три, края дерева Патриция помечены с последовательностями символов, а чем с одиночными символами. Эти могут быть строки символов, битовые строки такие как целые числа или IP-адреса, или как правило, произвольные последовательности объекты в лексикографическом порядке. Иногда имена основываются на дереве и Критическое битовое дерево применяется только к деревья, хранящие целые числа и Патриция Три сохраняется для более общего входы, но структура работает одинаково во всех случаях.

В LWN.net также есть статья, описывающая использование этих структур данных в ядре Linux .

Answer 5

Было бы гораздо лучше написать компаратор, который вы можете использовать для функции сортировки. Компаратор берет две строки и возвращает -1, 0 или 1. Даже если вы можете создать такую ​​карту, вам все равно придется сортировать по ней. Если вам нужен и «хеш», и порядок, то храните вещи в двух структурах данных - одна, которая сохраняет порядок, и другая, которая обеспечивает быстрый доступ.

Answer 6

У меня есть вопрос здесь https://stackoverflow.com/questions/22798824/what-lexicographic-order-means В качестве обходного пути вы можете добавить пустые символы с нулевым кодом к правой стороне строки и использовать расширение из случая II.

Без такого расширения с лишними пустыми символами я на самом деле не знаю, как сделать такое отображение .... Но если у вас есть конечный набор символов (V), то | V * | эквивалентна | N | - факт из Disrete Math.