Алгоритм, который генерирует уникальный серийный номер для каждого английского слова

Question

Для приложения мне нужно сгенерировать уникальные серийные номера для каждого английского слова.

Какой был бы лучший подход?

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

Благодаря

Answer 1

У вас есть список всех возможных слов? Если да, начните с 0 на первом слове и увеличьте серийный номер на 1 для каждого слова.

Если нет, то простой способ гарантировать их уникальность заключается в том, чтобы использовать само слово в качестве серийного номера. Например, ABC = 0x41 0x42 0x43 = 4276803. Как указано в комментариях, существуют и другие способы (которые требуют больше работы), например, сжимание слов сначала, например, с помощью Хаффмана.

Это, конечно, неудобно с длинными словами: Серийный номер Pneumonoultramicroscopicsilicovolcanoconiosis потребует, например, около 100 цифр.

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

Answer 2

Просто используйте 64-битный хэш-функции, как Fowler-Noll-Vo. Вероятно, вы не столкнетесь с коллизиями с использованием 64-битного целого числа, так как это дает вам 2^64 возможных значения, и, конечно же, есть намного меньше, чем многие слова на английском языке. Конечно, вам нужно нормализовать каждое слово (конвертировать в нижний регистр и т. Д.)

Answer 3

Действительно ли вам это нужно, чтобы быть «серийным»? если нет - пытались ли вы использовать различные алгоритмы хеширования? Некоторые из них встроены в .NET (MD5 и SHA1, если я правильно помню). Я не уверен, какой из них будет достаточно хорош, особенно с короткими струнами.

Answer 4

Вы, кажется, спрашиваете о идеальной функции хэширования. Если да, взгляните на this Wikipedia article и на утилиту gperf.

Answer 5

Вот алгоритм (в Python), который позволяет кодировать и декодировать любую комбинацию из строчных букв:

def encode(s): 
    r = 1 
    for i in len(s): 
    r = r * 26 + (ord(s[i]) - ord('a')) 
    return r 

Использование 64 бит можно закодировать до 12 букв слова. Остальные неиспользуемые сериалы можно использовать как в индексе для таблицы, содержащей низкочастотные очень длинные слова.

Answer 6

О алгоритме хеширования MD5. Сделайте что-то вроде этого:

serialNumber = MD5(ToLower (english word)) 

Answer 7

Вы ищете каждое слово или каждое слово в английском словаре? Используете ли вы стандартные слова - например, из Оксфордского словаря английского языка или включены также сленговые слова? Я предполагаю, что я получаю: «Насколько велика ваш словарь»? Вы можете использовать хеш MD5, который имеет теоретическую возможность столкновения - хотя 1 в миллиардах хэшей, которые могут столкнуться - хотя, я не могу сказать, что я бы понял цель использования хэша с использованием фактического слова. Если, возможно, вы не хотите рассчитать последовательную клиентскую сторону, чтобы ссылаться на правильный элемент словаря на стороне сервера, не анализируя словарь, ищущий его серийный номер. Конечно, слово, очевидно, должно быть достаточно уникальным, чтобы мы могли понять его как людей, и мы более эффективны при анализе смысла слов, чем компьютер делает то же самое.

Вы хотите разделить слова, которые выглядят одинаково, но произносятся по-другому? Слова, которые выглядят и звучат одинаково, но имеют разные значения? Если это так, то вы собираетесь отклеиваться хешем, так как одно и то же написание с другой семантикой даст такой же хэш, поэтому для этого сценария это не сработает. В этом случае вам понадобится какая-то инкрементная система. Если вы добавите слова после факта в словарь, они будут добавлены в конце и просто будут указаны следующий порядковый номер в последовательности? Что, если это слово написано так же, как и другое слово, но звучит по-другому или звучит одинаково, но имеет другую семантику? Что тогда?

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

Самый эффективный алгоритм, вероятно, состоит в том, чтобы разделить словарь на одно и то же количество кусков, поскольку у вас есть процессоры, и у каждого потока есть поток на каждом процессоре. Сериализуйте слова в своем блоке, рекомбинируя вывод из каждого потока в конце. Это (теоретически) будет работать со скоростью чуть медленнее, чем O (n/число процессоров) в реальном мире, однако я думаю, что для математической корректности это все равно O (n), потому что вам все равно придется разобрать весь словарь один раз для сериализации каждое слово.

Я думаю, что самый безопасный способ пойти: (? По алфавиту)

• Беспокойство о том, что у вас есть в настоящее время
• Заказать их в наиболее логической последовательности
• Число их в последовательности
• Добавить новые слова (независимо от того, написаны они одинаковые или нет и имеют разную семантику) в конце; дать им следующее число в последовательности, независимо от их законного места в словаре в алфавитном порядке.

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

Если вам нужно получить доступ к словарю в алфавитном порядке, просто сортируйте по слову, в противном случае - нет.

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

Answer 8

Интересно, возможен ли даже ответ.

Цвет и цвет одно и то же слово? Получают ли они один серийный номер или два?

Являются ли польский и польский одно и то же слово?

Есть часы (существительное) и смотреть (глагол) то же слово?

Умножают (глагол) и умножают (наречие) одно и то же слово?

Анализ (единственное существительное) и анализы (множественное существительное) - это не одно и то же слово. Анализируют (множественный глагол) и анализируют (множественный глагол) одно и то же слово? Являются ли анализы (сингулярный глагол) и анализы (сингулярный глагол) одним и тем же словом?Являются ли анализы (сингулярный глагол) и анализы (множественное существительное) одним и тем же словом?

Умер и не будет то же слово?

Пекине и Пекине одно и то же слово? Или, может быть, они не англичане, так как Лондрес и Франкрейх не являются английскими, но тогда какое английское слово для столицы Средней Страны?