Проверка, содержит ли строковый хеш подстрока

Question

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

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

, например

var string1 = "bla bla bla cat dog bla bla";
var string2 = "cat dog";
var hash1 = HashAlgo(string1); // <-- magic goes here
var hash2 = HashAlgo(string2);
Assert.IsTrue(string1.Contains(string2));
Assert.IsTrue(hash1.Contains(hash2)); // <--- magic goes here

Answer 1

Если вы подумаете об этом, не имеет смысла, что это возможно.

Прежде всего, все хэши SHA256 имеют одинаковую длину.Я основал ответ на SHA256, но насколько мне известно, это применимо к любому методу хеширования.

• Рассмотрим документ из 1000 символов, который вы хэшировали в SHA256.Его хэш длиной 64 цифры.
• Рассмотрим документ из 100 символов, который вы хэшировали в SHA256.Его хеш длиной 64 цифры.Содержимое этого документа является первой главой более крупного документа.
• Рассмотрим второй 100-символьный документ, который вы хэшировали в SHA256.Его хеш длиной 64 цифры.Содержимое этого документа является второй главой более крупного документа.

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

Во-вторых, подумайте, сколько 100-символьных подстрок я мог бы взять из документа из 1000 символов.Это не просто 10 (как в 1000/100 = 10), а скорее 900. Обозначая подстроки в качестве границ индекса, существует множество возможностей:

• 0 до 100
• 1 доОт 101
• 2 до 102
• ...
• 897 до 997
• 898 до 998
• 899 до 999

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

Эти 900 уникальных хешей не могут быть всеподстрока хэша исходного файла.

Кроме того, учтите, что мы даже не думали о подстроках другой длины!Предполагая любую возможную длину подстроки, вы можете получить 999 000 различных подстрок (но, конечно, некоторые из них будут иметь дубликаты)

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

Это расширение возможных значений только плато, когда вы находитесь на порядок 10 ⁷⁷ (точнее, 2 ²⁵⁶ ), так как это количество уникальных SHAхэши могут существовать.
Задняя часть салфетки, это будет документ с 10 ³⁸ байтами.Как только вы достигнете этого размера файла, все возможные подстроки (любой длины) должны будут содержать хотя бы один дубликат.

Я думаю, вы можете понять, почему ваше предложение просто математически невозможно.

Я оставлю это в качестве sidenote, но superpermutations - это тема, на которую стоит обратить внимание, чтобы понять, насколько это невозможно.Для 7 уникальных символов вам нужна суперперестановка 5907 цифр , если вы хотите охватить все возможные перестановки из 7 символов.Это наибольшее значение N, для которого мы нашли (минимальные) суперперестановки.

Для начального примера 900 уникальных хешей (= уникальных перестановок шестнадцатеричных символов), которые все будут содержаться в вашем«главный» хеш, минимальная требуемая длина главного хэша просто неисчислима.Но как минимум абсолютный (который вы, вероятно, не можете использовать), ваш главный хеш должен иметь длину 963 символа (если вы предполагаете, что каждая подстрока из 64 символов всегда дает вам новый уникальный хэш)