строки хеширования

Question

У меня есть потоковые строки (текст, содержащий слова и цифры).

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

примеры могут быть: строки с их счетами / хэш

  User1 logged in Comp1 port8087       1109      
  User2 logged in comp2                1135
  user3 logged in port8080             1098
  user1 logged in comp2 port8080       1178       

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

Один простой способ сделать это: взять UliCp8 , Ulic .... (т.е. 1-ю букву каждого предложения) и найти какой-то способ подсчета очков. После этого похожие набранные строки хранятся в том же ведре, а затем подгруппируют их.

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

Учитывая расстояние Левенштейна или jaccard_index или некоторые метрики расстояния подобия, все они требуют ввода строк для сравнения. Нет ли какого-либо метода для хеширования / оценки строки, как указано, без использования сравнений (теги POS, сравнение выглядят неочевидно для моей цели, поскольку данные потоковые, огромные по количеству, неструктурированные)

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

Answer 1

Как уже говорилось, вы не ищете хеш-функцию, скорее что-то вроде расстояния Левенштейна , которое представляет собой алгоритм для вычисления метрики, представляющей степень различий между двумя последовательностями битов , Обычно используется, чтобы узнать, насколько похожи / не похожи две строки. Хеширование / дайджесты сообщений хороши для создания идентификаторов для уникальных, отличных значений, но они будут давать совершенно разные результаты для «похожих» значений.

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

Answer 2

"как минимум два одинаковых слова (без учета длины) должны иметь одинаковое значение хеш-функции"

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

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