Что такое Харрисон Хэшинг, его приложения в веб -поисковых системах?

Question

Что такое харрисон хэшинг и каковы его приложения в поиске в Интернете? Может ли кто -нибудь дать мне некоторую соответствующую информацию?

Обновлять:

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

Answer 1

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

Также вы можете найти в Алгоритмы поиска строки Грэм А. Стивен.

Answer 2

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

Подписи построены путем изучения всех пар последовательных символов в строке. Таким образом, для строки «Abcdef» пары были бы «AB», «BC», «CD», «de», «EF». В зависимости от природы данных и используемого компьютера, один выбирает немного размер для подписи, возможно, 32 или 64 бита, но возможны разные размеры. Далее вы должны разработать хэш -функцию, которая будет сопоставить любую пару символов в один из битов в подписи. Простая хэш -функция заключается в том, чтобы умножить значения символов вместе, делиться на размер бит подписи и использовать остаток. На практике необходима некоторые настройки, чтобы получить хорошее распространение битов, установленных по всем парам персонажей. Затем вы рассчитываете хэш для каждой из пар символов и устанавливаете соответствующий бит в подписи. Когда разные пары хэшируют к одному биту, бит остается установленным, то есть вы продолжаете в бите, чтобы установить подпись. Вы создаете таблицу всех подписей для всех строк в исходном исходном файле.

Чтобы найти подстроение, вы рассчитываете подпись самой подстроки. Если подстроение содержится в строке, то все наборные биты в подписи подстроения должны быть установлены в подписи строки. Это должно быть самостоятельно, потому что, если в подстроении содержалась пара символов, которые, как говорится, 17, но бит 17 не был установлен в подписи строки, то ясно, что пара символов не может быть в строке, потому что если если если это Это был этот бит был бы установлен.

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

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

Профессор Харрисон был одним из моих учителей в Институте математических наук Курант, и я использовал этот алгоритм в ряде программ редактирования текста. Это действительно блестящее наблюдение.