Строка в число и обратный алгоритм

Question

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

Например: Слово «котенок» может дать 12432, но только слово «котенок» производит это число. Текст может быть любым, и нужно указать правильное число.

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

---

Мои попытки. У вас есть буквы A-Z и 0-9, поэтому один символ может иметь число от 1 до 36. Но если A = 1 и B = 2, а текст A (1) B (2) и вы добавите его, вы получите результат 3, проблема в том, что текст BA выдает тот же результат, поэтому этот алгоритм не будет работа.

Есть идеи, чтобы указать мне правильное направление или это невозможно сделать?

Answer 1

Ваша идея в целом нормальна, ее нужно только немного развить.

Пусть f(c) будет функцией преобразования символа c в уникальное число в диапазоне [0..M-1]. Затем вы можете вычислить номер результата для всей строки следующим образом.

f(s[0]) + f(s[1])*M + f(s[2])*M^2 + ... + f(s[n])*M^n

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

Очевидно, что здесь нельзя использовать очень длинные строки (до 6 символов для вашего случая), так как 36^n быстро растет.

Answer 2

Просто обработайте каждый символ как цифру в базе 36 и вычислите десятичный эквивалент?

Итак:

'A' = 0
'B' = 1
[...]
'Z' = 25
'0' = 26
[...]
'9' = 35
'AA' = 36
'AB' = 37
[...]
'CAB' = 46657

Answer 3

Если текст написан правильно на каком-то языке, у вас может быть номер для каждого слова. Тем не менее, вам нужно учитывать все возможные множественные числа, названия мест и людей и т. Д., Что, как правило, невозможно. О каком тексте идет речь? Обычно будут некоторые существующие слова, которые никак не могут быть закодированы в 32 бита без предварительного знания их.

Можете ли вы составить список слов по ходу дела? Просто дайте первое слово, которое вы видите номер 1, второе число 2 и проверьте, есть ли слово уже номер или ему нужно новое. Затем сохраните ваш недавно созданный словарь где-нибудь. Скорее всего, это будет единственное работоспособное решение, если вам потребуется 100% надежное, обратимое сопоставление чисел и исходных слов с учетом нового неизвестного текста, который не следует ни одному известному шаблону.

С 64 битами и достаточно хорошим хешем, таким как MD5, крайне маловероятно, что возникнут коллизии, но для 32 битов маловероятно, что существует безопасный хеш.

Answer 4

Представьте, что вы пытаетесь хранить строки из набора символов "0-9" только в числе (эквивалент получения числа из строки цифр).Что бы вы сделали?

Char 9 8 7 6 5 4 3 2 1 0
Str  0 5 2 1 2 5 4 1 2 6

Num = 6 * 10^0 + 2 * 10^1 + 1 * 10^2...

Примените то же самое к вашим персонажам.

Char 5 4 3 2 1 0 
Str  A B C D E F
L = 36

C(I): transforms character to number: C(0)=0, C(A)=10, C(B)=11, ...

Num = C(F) * L ^ 0 + C(E) * L ^ 1 + ...

Answer 5

Создайте словарь из слов, сопоставленных с уникальными числами, и используйте это, это лучшее, что вы можете сделать.

Я сомневаюсь, что используется более 2 ^ 32 слов, но это непроблема, с которой вы сталкиваетесь, проблема в том, что вам нужно отобразить числа обратно в слова.

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

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

Другими словами:

AARDUANI = 0
AARDVARK = 1
...

Если вы хотите сопоставить числа с базой 26 символов, вы можете хранить только 6 символов (или 5 или 7, если я просчитался), но не 12 иконечно, не 20.

Если вы не учитываете только реальные слова, и они не следуют никаким хорошим счетным правилам.Единственный способ сделать это - просто поместить все слова в длинный список и начать присваивать цифры с самого начала.