Я создаю Антиплагиат. Я использую метод гальки. Например, у меня есть следующие черепицы:
Есть ли метод вычисления равного хеша для этих строк?
Я знаю о существовании расстояния Левенштейна. Однако я не знаю, что я должен взять исходное слово. Может быть, есть лучший способ, чем рассматривать расстояние Левенштейна.
Проблема с хешированием заключается в том, что логически вы столкнетесь с двумя строками, которые отличаются одним символом, который хеширует разные значения.
Небольшое доказательство:
Рассмотрите все возможные строки.
Предположим, что все эти хэши имеют по крайней мере 2 разных значения.
Возьмите любые 2 строки A и B, которые имеют хэши с разными значениями.
Очевидно, что вы можете перейти от A к B, просто изменив по одному символу за раз.
Таким образом, в какой-то момент хеш изменится.
Таким образом, в этот момент хэш будет другим для изменения одного символа.
Возможны следующие варианты:
Хэшируйте несколько частей строки и проверяйте каждый из этих хэшей. Вероятно, это не будет работать слишком хорошо, поскольку пропуск одного символа приведет к значительной разнице в значениях хеш-функции.
Проверьте диапазон хэшей. Хэш является одномерным, а сходство строк — нет, поэтому это, вероятно, тоже не сработает.
В общем, хеширование, вероятно, не выход.
Этот вопрос немного устарел, но вам может быть интересна эта статья двумя исследователями из AT&T. Они используют метод, напоминающий хеш Nilsimsa, чтобы определить, когда подобные sms-сообщения были просмотрены «ненормальное» количество раз во временном окне.
Похоже, что хеширование с учетом местоположения также имеет отношение к вашей проблеме.
