Нечёткий поиск в таблице чисел

Proteus

расходы на что? На хэш таблицу? А как вы без нее собирались (может я не правильно понял вашей задачи)? На таблицу масок? Она выходит как раз маленькая. На рантаймовый расчет масок? Так пишу ж, что это статические числа. Вы их можете перлом прямо в сорец в виде таблички (а лучше в виде 2х векторов, тк она получается треугольная) рассчитать в девелоптайме, чтоб хуцкеры бошки потом себе поломали.

 

_basmp_

а можно поподробнее? - насколько я понял задачу - начать ТС хотел с 32 разрядных А и Б, затем перейти к произвольной длине, но если "длинное" число например 1024бит то зачем ему хэш? имхо он и на записях измеряемых в килобайтах не всегда оправдан. А уж здесь как подменить таблицу А на таблицу хэшей я чего-то совсем не проедставляю, или под хэш ты подразумеваешь не "нечто вроде контрольной суммы", а что-то иное?

 

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

А вот обновление за разумное время, о нём ещё стоит подумать...

 

Y_Mur
Массив предвычесленных значений - тот же хеш.

 

Y_Mur

хэш, грубо говоря - некий способ рассчета позволяющий из большего числа (длинная строка == большое число) получать некое достаточно неповторяющееся меньшее (хэш), которое потом используется в качестве индекса в неком массиве, размер которого не меньше расчетного максимума этого вычисляемого числа (хэша). По данному индексу, при одном из решений находится ссылка на вектор первоначальных чисел (строк), чей хэш равен этому индексу. Позволяет уменьшить количество затратных сравнений (например, 2кб разрядных чисел или строк) в среднем в ~ хэш-макс раз. (надеюсь я не сильно отклонился от стандартного определения) А способ расчета и что считаем - большого значения не имеет. Если алг контрольной суммы дает хороший разброс и конечные цифры не слишком велики, то почему бы и не юзать его?
Блэк миррор в той теме проводил тест сравнения по хэшам. Если хэши оказывались достаточно близки, то сравнивались файлы. Токо он вроде не юзал 32 бита. Слишком большие числа, чтоб работать с ними быстро. Лучше потом еще раз уточнить или лишнюю пару сравнить.

 

Пока задача не поставлена конкретно, ничего конкретно сказать и нельзя.

 

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

 

_basmp_

Что собственно меня и смутило что здесь речь не о файлах , а о словах, тем более ТС в #23 это подтвердил ,
Booster

к тому же эти слова сравниваются с произвольным входным значением, значит "хэшем" в смысле "предвычисления" с некоторым натягом можно было-бы назвать таблицу масок , но _basmp_ эти вещи в одну кучу не смешивал, и правильно сделал, а насчёт

согласен - слишком много ньюансов, чтобы решать "в общем виде".

GoldFinch
А это зависит от "статичности массива" - если массив один раз постороен и меняется редко, а искать в нём нужно часто, то даже большие накладные расходы на пристраивание к нему быстрого поиска могут быть оправданы поскольку требуются однократно/изредка, а выигрыш в скорости поиска будет на каждом запросе
А если менять массив нужно соизмеримо или даже чаще чем искать в нём, то есно тупой последовательный перебор рулит

 

Y_Mur

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

Меня это тоже немного смущает, хотя задача найти эффективную хеш функцию и тут и там.

_basmp_

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

 

Booster

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

дык писал же. "ссылки в хэштаблице (с индексами == хэшчислу) -> на вектора всех различных значений с таким хэшем. Эти значения сравниваются с новым и, если различаются со всеми - значение добавляется к вектору." Те одинаковость хэшей не обязательно означает однозначной одинаковости данных (а как вы сможете сократить число на 2кб до 16бит, чтоб такая однозначность была?). Но различность хэшей - обязательно означает различность данных. Те хэши позволяют сократить количество необходимых сравнений в среднем в ХЭШмакс раз. Совпадение хэшей при различных исходных данных называется коллизией. Главной задачей получения хэш функции является уменьшение вероятности коллизии на наиболее вероятных данных. Это стандартная теория и простейший случай. Кнут, том 3.

 

_basmp_
Я в курсе, что у Кнута об этом есть в 3 томе.

Я написал, что это можно рассматривать как хеш функцию. Вы можете точно сформулировать что есть хеш?

 

Booster

писал выше. Могу только добавить, что распределение получаемых хэш индексов в пределах хэш таблицы должно быть равномерным. В случае подсчета битов, скажем для строк - ячейки 0 и 8 будут не заняты, 1 - мало, 7 скорей всего тоже занято не будет итд. А средние ячейки будут перегружены, те сравнений при попадании в них придется делать очень много. И потом, что это за хэш таблицы из хоть 8, хоть 128 элементов? Выигрыш на поиске по индексу (хэшу) должен как минимум перекрывать затраты на расчет этого самого хэша (индекса), тк как минимум одно полноценное сравнение все равно будет (может жать все файлы перед сравнением каким нить быстрым алгосом и в таком виде сравнивать?).

 

_basmp_
Не стоит докапываться, ваше право понимать хеш только так:

Я же имею полное право понимать это понятие шире, то есть не только как:

Например следуя вашей логике MD5 хеш, это совсем не хеш.

Это свойство, а не признак.

Я не предлагал использовать этот метод для сравнения файлов, да и тема вроде не про это.

 

Booster
из словаря мюллера (одно из значений)
hash
==
"2) что-л. старое, выдаваемое в измененном виде за новое"
еще значение похожее на 'измельчать' есть.

еще есть значение
3) мешанина, путаница; to make a hash of smth. - напутать, напортить в чем-л.

а вообще - это просто слова. Я, напр, свою машину - калошей называю. Правда на ноги - не одеваю.

Смутно помню, что не про то, что допускается называть называть хэшем (фаршем?)