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

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

У всех чисел одинаковая разрядность. Вставки и удаления во время сравнения не используются.


Разные вариации задачи (на разные вкусы):
1) допустим отличаться должна не половина разрядов, а четверь или на крайняк ещё меньше...
2) разрядность чисел достаточно большая (т.е. больше машинного слова в два или более раз)
3) нужен способ добавлять в таблицу новые числа за разумное время

 

Проведи Операцию:

Код (Text):

1. xor Число, Образец

Тогда в "Число" все отличающиеся биты станут единицами. Останется только подсчитать количество единиц (есть какой-то способ сделать это всего за 4 операции).

 

Proteus
Выбирай числа случайным образом.
Еще хотелось бы знать отсортированны данные или нет и их разрядность.

 

Придётся пояснять, возможно плохо объяснил =))

- как выше сказано, надо без тупого сравнения чисел с образцом. Оптимизация сравнения скучна и проблем не представляет. Хотя единицы посчитать это забавная фишка. Надо каким-то образом структурировать данные, затем чтобы не бегать по всем числам, а делать что-то более быстрое.

Случаность будет не быстрее перебора, никакой пользы. Любые данные можешь подготавливать заранее, любым способом, хоть сортируй, хоть на изнанку выворачивай. Разрядность бери какую, тебе угодно, всё равно задача совсем не тривиальная. Допустим 32 бита...

 

Proteus
а отсортировать числа в порядке возрастания "количества единичек" не пойдёт?
если важен порядок чисел до сортировки можно добавить массив их исходных индесов, чтобы найдя нужное число (например делением диапазона пополам ) определить его исходное несортированное положение.

 

http://ru.wikipedia.org/wiki/Расстояние_Хэмминга

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

 

Вот я тоже именно в этом сомневаюсь. Ну 1 и 25 бит, если считать это ослаблением начальной задачи, всё равно как-то не греет. В реале тестить в помощью rand() придётся, он данные такие халявные данные рисовать не будет.

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

 

Для быстрого счёта количества битов, можно заюзать массив где элемент это число битов.
Если число будет большое и будет не хватит памяти, то можно соорудить дерево или хеш и сразу отсекать не подходящие для сравнения случаи. Число битов максимум-то 8 - 32
Например расчёт кол-ва битов 32 числа можно сделать в два обращения к 16 битному массиву.

 

Proteus

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

ЗЫ:
я не понял твоя задача сводится к формулировке "найти в массиве число у которого количество единичных бит лежит в дипазоне от x до y (например от 5 до 12)" или важен также порядок расположения этих бит при логическом сравнении с эталоном? например в числах 0х55555555 и 0хAAAAAAAA количество бит=1 одинаковое, но при битовом сравнении не будет ни одного совпадения 0 и 0 или 1 и 1
В первом случае (если искать нужно намного чаще чем добавлять, удалять, изменять элементы массива) бинарное дерево (оно же метод деления отрезка пополам ) рулит, а если второй случай, то я затрудняюсь с формулировкой "критерия упорядоченности" (необходимого и достаточного) для дерева, но если его всё таки придумаешь, то будет тебе быстрый поиск

 

вроде бы был недавно подобный вопрос

 

Решили ?
Подобные вопросы часто возникают. Я только упростил насколько мог...

Скажем так. Между образцом и найденым числом мы смотрим расстояние по Хемингу (нужно минимальное по расстоянию). И ещё раз повторяю: не можем перебирать всю таблицу.

 

Proteus

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

 

А припоминаю, с файлами он мучался. Помойму ничего фундаметального так и не придумал.
На самом деле не только у него такие проблемы бывают, я много схожих проблем в других местах видел. Действительно важная задача .....

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

 

А можно примерчик? есть число 0х55555555 (32 бита всего, из них 16 единичек) что за массив такой из которого можно двумя выборками получить число 16 исходя из 0х55555555?

Proteus

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

А как на счёт почётче сформулировать практическую сторону "нечёткой" задачи? может найдутся альтернативные пути

 

Y_Mur
Ну как. Есть массив размером 0xffff, в каждом элементе которого храниться кол-во битов индекса. Например в элементе с индексом 0x5555, храниться число 8. Как говориться -"увеличиваем расход памяти, уменьшаем время".

 

Booster
дошло ) хотя

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

 

Нет смысла. Практических задач похожих по смыслу попадается много (видел иногда в разных ЖЖ, формах и т.д. даже тут было).
А я как бы свёл это к более упрощённой задаче. Притом упростил максимально, чтобы было понятнее и легче было решать.

вот как раз под новый год и подумаем. Сколько таких задач раньше было?! =) Которые невозможно решить. Которые решили, хотя они порою слишком много памяти жрали и решения на первый взгляд были сомнительны. Но решения иногда всё же возникали, почему бы не подумать =)

 

напишу то, что писал в той ветке.

любое число можно представить как A = B xor M

где каждая единица в М будет соответстововать биту различному в А и В.

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

Однако, такая таблица масок может быть слишком большой. Рассмотрим далее. Очевидно, что числа могут отличаться расстоянием между отдельными единичными битами в М (1), представленном как замкнутый кольцевой битовый буфер и кольцевым сдвигом относительно начала (2). Так 32х битное М с одним битом - одно число (1) и 32 сдвига (включая 0ой) (2), с двумя битами - 16 (1) и по Х (2) для каждого. итд. (алгос для (1) и (2) вышел немного не самый простой или оптимальный и прямо щас его не помню, но можна посмотреть в той ветке)

 

Proteus

зачем же с каждым числом, надо пока не найдётся подходящее.

 

Раходы большие. Но это уже не так плохо))) спасибо...