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

Question

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

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

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

Спасибо

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

Я думаю, что самый безопасный путь:

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

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

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

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

Answer 7

Интересно, возможен ли ответ?

Являются ли цвет и цвет одним и тем же словом? Они получают один серийный номер или два?

Польский и польский это одно и то же слово?

Являются ли часы (существительное) и часы (глагол) одним и тем же словом?

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

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

Неужели не одно и то же слово?

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

Answer 8

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

serialNumber = MD5( ToLower ( english word ) )