Можно ли сравнить две строки по их "хеш-числам"?

Question

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

Integer savedHash = 352736;
String newText = "this is new string";
if (Math.abs(hash(newText) - savedHash) < 100) {
  // wow, they are very close!
}

Существуют ли алгоритмы для этой цели?

пс.Длина текста не фиксирована.

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

ppps.В очень простом сценарии этот метод hash() будет выглядеть так:

public int hash(String txt) {
  return txt.length();
}

Answer 1

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

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

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

Answer 2

Если хэши не совпадают, то строки различаются.

Если хэши совпадают, то строки , вероятно, одинаковы.

Больше ничего нетвы можете вывести из значения хеша.

Answer 3

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

[Отредактировано в свете комментариев, конечно, вероятность столкновения очень реальна]

Редактировать для уточнения:

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

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

Answer 4

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

Однако есть несколько человек, которые разработали алгоритмы, которые хотя бы чем-то похожи на это. Например, есть компания под названием «Xpriori», которая имеет некоторые алгоритмы хеширования (или наименее хеш-подобные), которые допускают подобные вещи. Они позволят вам сравнивать по степени сходства или (например) позволят вам комбинировать хеши так: hash(a) + hash(b) == hash(a+b) (для некоторого определения +, а не просто для сложения чисел). Как и в случае с большинством хэшей, всегда существует вероятность столкновения, поэтому у вас есть некоторый шанс ложного срабатывания (но, выбрав размер хэша, вы можете установить этот шанс на сколь угодно малое значение).

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

Answer 5

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

Рассчитать Коэффициент корреляции Пирсона между первой и второй половиной строки (если длина строки - нечетное число символов, затем добавить некоторые отступы) и сохранить это число как 32-разрядное число с плавающей запятой. Но я не уверен, насколько надежным будет этот метод.

== EDIT ==
Вот пример кода C (неоптимизированный), который реализует эту идею (немного модифицированный):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

float mean(char *str) {
  char *x;
  float sum = 0.0;

  for(x=str; *x!='\0'; x++) {
    sum += (float) *x;
  }
  return sum/strlen(str);
}

float stddev(char *str) {
  char *x;
  float sum = 0.0;
  float u = mean(str);

  for(x=str; *x!='\0'; x++) {
    sum += ((float)*x - u)*((float)*x - u);
  }
  return sqrt(sum/strlen(str));
}

float covariance(char *str1, char *str2) {
  int i;
  int im = fmin(strlen(str1),strlen(str2));
  float sum = 0.0;
  float u1 = mean(str1);
  float u2 = mean(str2);

  for(i=0; i<im; i++) {
    sum += ((float)str1[i] - u1)*((float)str2[i] - u2);
  }
  return sum/im;
}

float correlation(char *str1, char *str2) {
  float cov = covariance(str1,str2);
  float dev1 = stddev(str1);
  float dev2 = stddev(str2);
  return cov/(dev1*dev2);
}

float string_fingerprint(char *str) {
  int len = strlen(str);
  char *rot = (char*) malloc((len+1)*sizeof(char));
  int i;
  // rotate string by CHAR_COUNT/2
  for(i=0; i<len; i++){
    rot[i] = str[(i+len/2)%len];
  }
  rot[len] = '\0';
  // now calculate correlation between original and rotated strings
  float corr = correlation(str,rot);
  free(rot);
  return corr;
}

int main() {
  char string1[] = "The quick brown fox jumps over the lazy dog";
  char string2[] = "The slow brown fox jumps over the crazy dog";
  float f1 = string_fingerprint(string1);
  float f2 = string_fingerprint(string2);
  if (fabs(f1 - f2) < 0.2) {
    printf("wow, they are very close!\n");
  }
  return 0;
}

НТН!

Answer 6

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

Answer 7

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

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

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

Answer 8

Любой хороший алгоритм хеширования по определению НИКОГДА не даст одинаковые хеш-значения для аналогичных аргументов. В противном случае это было бы слишком легко взломать. Если хэшированное значение «aaaa» похоже на «aaab», то это плохой хэш. Раньше я делал такие же без особых проблем (забавная головоломка, которую нужно решить!) Но вы никогда не знаете, может быть, ваш алгоритм хеширования плохой. Идея, что это такое?

Если у вас есть время, вы можете просто перебрать это решение, хэшируя каждое возможное слово. Не элегантно, но возможно. Проще, если вы знаете длину исходного слова.

Если это стандарт имеет алгоритм, такой как MD5, вы можете найти сайты, которые уже имеют большие сопоставления источника и хэша, и получить ответ таким образом. Попробуйте http://hashcrack.com/

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

Приветствия

Daniel

Answer 9

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

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

Answer 10

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