Здравствуйте, Videoman, Вы писали:

В общем, спасибо всем большое за подсказки. Решил задачу. Остановились на VP-Tree (Vantage Point Tree)
Почему так долго:
— решил написать когда уже все отладил и решил всю задачу в комплексе, не только эту
— долго смотрел что вообще есть, какие подходы, какие структуры
— все готовые решения которые видел в интернете — академические какашки (в плане кода), существующие только для демонстрации, где куча new и С с классами
— долго убеждался что все отлажено и работает как надо

Результат:
В качестве хешей у меня получились uint32_t. VP-Tree очень быстро работает, начинает обгонял линейный поиск на размерах, где-то, больше 4096. При >= 10М хешей начинает обгонять "грубую силу" в 1000 и более раз.

Для тех кому интересно что за дерево(структура) и как устроено:

Это дерево строится рекурсивно: Берем наши хеши. Выбираем любой элемент случайно и частично сортируем их все по расстоянию (Хемминга в моем случае) до этого выбранного элемента. Далее берем медиану и все что меньше по расстоянию от медианы в левое поддерево, а все что больше в правое поддерево. Дальше повторяем рекурсивно, пока мы не отсортируем все хеши.

Поиск:
Берем любой хеш и заданный порог. Идем в корень дерева. Считаем расстояние от корня до нашего хеша. Если подходит, то добавляем хеш в список. Прибавляем к нему наш порог, чтобы получить максимальное расстояние поиска. Сравниваем максимальное расстояние с заданным порогом и идем в левое поддерево, если расстояние меньше порога, в оба, если меньше либо равно, и в правое, если строго больше порога. Далее повторяем шаги рекурсивно, пока не соберем все элементы.

Есть следующая задача:
— Есть битовая строка
— Задано максимальное расстояние
Необходимо:
— Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

Вроде бы на форуме мелькало, но с ходу найти не получается. Задача кажется не сложной. Может быть, туплю. Если кто-то в теме, просьба подсказать куда копать? Желательно как можно проще. Еще лучше если можно будет быстренько "наложить" на STL.
Заранее, спасибо большое всем откликнувшимся!

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, R.K., Вы писали:

V>>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

RK>>Задачка для PATRICIA trie.
_>И чем суффиксное дерево поможет в поиске максимального расстояния?

Подвышенной тормознутостью (по сравнению с оптимизировнной ксоркой 64-битными словами).

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, R.K., Вы писали:

RK>>После того, как мы построили trie над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку.
_>Это здорово, но чем это поможет в поиске максимально удалённых по растоянию элементов?

Я написал, чем поможет. Задача звучала так:

V>Есть следующая задача:
V>- Есть битовая строка
V>- Задано максимальное расстояние
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

Это достаточно точная формулировка одного из эффективных способов применения trie.

Здравствуйте, Videoman, Вы писали:

V>Есть следующая задача:
V>- Есть битовая строка
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать расстояние Хемминга в наборе битовых строк такой же длины.
dist = bit_count( s1 xor s2 ) ?
Или стороки не ипической длинны?
Структуру в которой можно искать ближайшие по расстояние Хемминга или что? Какие ограничения?

Здравствуйте, kov_serg, Вы писали:

_>dist = bit_count( s1 xor s2 ) ?
Так точно!

_>Структуру в которой можно искать ближайшие по расстояние Хемминга или что? Какие ограничения?
Хочется некую структуру таких строк — s(1..50000). На вход подается sN и нужно быстро найти все строки с максимальным заданным расстоянием d.

Здравствуйте, Videoman, Вы писали:

V>Здравствуйте, kov_serg, Вы писали:

_>>dist = bit_count( s1 xor s2 ) ?
V>Так точно!

_>>Структуру в которой можно искать ближайшие по расстояние Хемминга или что? Какие ограничения?
V>Хочется некую структуру таких строк — s(1..50000). На вход подается sN и нужно быстро найти все строки с максимальным заданным расстоянием d.
Длинна строк какая? 10бит сотни бит или гигабиты и больше?

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, Videoman, Вы писали:

V>>Здравствуйте, kov_serg, Вы писали:

_>>>dist = bit_count( s1 xor s2 ) ?
V>>Так точно!

_>>>Структуру в которой можно искать ближайшие по расстояние Хемминга или что? Какие ограничения?
V>>Хочется некую структуру таких строк — s(1..50000). На вход подается sN и нужно быстро найти все строки с максимальным заданным расстоянием d.
_>Длинна строк какая? 10бит сотни бит или гигабиты и больше?

Тысячи. Пока точно не понятно, но давайте, для конкретики, возьмем 1024 бита.

Здравствуйте, Videoman, Вы писали:

V>Есть следующая задача:
V>- Есть битовая строка
V>- Задано максимальное расстояние
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

В общем виде вопрос на Нобелевку В теории кодирования есть "быстрые" алгоритмы, которые пользуются свойствами "набора" для нахождения ближайших по Хэммингу кодовых слов к заданному паттерну. Твоя задача куда как более общая — требуется не наименьшее, а заданное расстояние искать, причем "набор" произволен. Под "быстрыми" понимаю хотя бы имеющие меньший показатель экспоненты, чем длина строки.

V>>>Хочется некую структуру таких строк — s(1..50000). На вход подается sN и нужно быстро найти все строки с максимальным заданным расстоянием d.
_>>Длинна строк какая? 10бит сотни бит или гигабиты и больше?
V>Тысячи. Пока точно не понятно, но давайте, для конкретики, возьмем 1024 бита.
1. распаралелить полный перебор
2. разбить на кластеры и всякие деревья для ускорения поиска ближайшего соседа

Здравствуйте, andyp, Вы писали:

A>В общем виде вопрос на Нобелевку

Вот я всегда так влипаю. Приходится за ученых делать их работу

A>В теории кодирования есть "быстрые" алгоритмы, которые пользуются свойствами "набора" для нахождения ближайших по Хэммингу кодовых слов к заданному паттерну. Твоя задача куда как более общая — требуется не наименьшее, а заданное расстояние искать, причем "набор" произволен. Под "быстрыми" понимаю хотя бы имеющие меньший показатель экспоненты, чем длина строки.

Не... Может быть я невнятно задачу описал:
мне нужно в жестко заданном наборе искать кодовые слова, именно ближайшие, к заданному на входе с расстояние не более N.

Здравствуйте, kov_serg, Вы писали:

_>1. распаралелить полный перебор
_>2. разбить на кластеры и всякие деревья для ускорения поиска ближайшего соседа

Ну это я видел. Думал что на форуме народ что-то более понятное подскажет, на пальцах общую идею, так сказать.

Здравствуйте, Videoman, Вы писали:

V>Не... Может быть я невнятно задачу описал:
V>мне нужно в жестко заданном наборе искать кодовые слова, именно ближайшие, к заданному на входе с расстояние не более N.

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

Здравствуйте, andyp, Вы писали:

A>Да я про то и писал. В теории кодирования жизнь упрощается тем, что все кодовые слова (твой набор) имеют определенную структуру (обычно являются линейной комбинацией относительно небольшого количества "базисных" кодовых слов, т.н. линейный код). Среди них ищется ближайшее по Хэммингу слово к тому набору бит, что был принят с ошибками из канала.

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

Здравствуйте, Videoman, Вы писали:

V>Я понял. Ты про коды коррекции ошибок. У меня не тот случай, согласен. Но у меня, все-таки, есть ограниченный набор битовых слов, поэтому интуиция подсказывает что должны быть структуры оптимизирующие такой поиск.

Если макс. расстояние N совсем невелико (1..2), можно сделать так:

Построение данных для поиска:

0. Полагаем w = 0, а списком рассмотренных слов — все K кодовых слов длиной L бит из набора.

Для каждого веса w от 1 до N:

1. формируем всевозможные битовые комбинации с w единицами — их будет L_choose_w (биномиальный коэффициент из L по w).

2. Добавляем их (XOR) поочередно ко всем кодовым словам. Если в получившемся списке окажутся слова, которые мы уже раньше рассматривали, вычеркиваем их.

3. Сохраняем полученные на этапе 2 слова в списке рассмотренных вместе с w

4. переходим к следующему w


При поиске просматриваем список рассмотренных, если находим, выдаем значение w для найденного слова.

Список рассмотренных может быть организован как N+1 массивов, каждый из которых имеет длину максимум K* L_choose_w) элементов. K — количество слов в наборе для поиска.

Но не уверен, что этот поиск будет быстрее, чем просто расстояние Хэмминга считать для всего набора из K слов. Биномальные коэффициенты очень быстро растут, а у тебя L и так большое. Набор очень большим потенциально будет для L = 1024, K = 50000.

Здравствуйте, Videoman, Вы писали:

V>Вроде бы на форуме мелькало, но с ходу найти не получается. Задача кажется не сложной. Может быть, туплю. Если кто-то в теме, просьба подсказать куда копать? Желательно как можно проще. Еще лучше если можно будет быстренько "наложить" на STL.

Можно начать смотреть отсюда.
Битовую строку можно выразить как вещественный вектор со значениями 0 и 1, тогда расстояние хэмминга будет совпадать с евклидовым.

Здравствуйте, Brice Tribbiani, Вы писали:

BT>Битовую строку можно выразить как вещественный вектор со значениями 0 и 1, тогда расстояние хэмминга будет совпадать с евклидовым.

Это вряд ли, скорее с Манхэттенским.

Здравствуйте, cures, Вы писали:

C>Это вряд ли, скорее с Манхэттенским.

Да. Ну, или с квадратом евклидового.

Я бы так сделал.

Набор строк преобразуем в бинарное дерево. Каждый путь от корня до листа это соответствующая строка.

При поиске проходим по дереву и сразу отбрасываем поддеревья, путь до которых даёт слишком большую разницу.

В худшем случае будет тот же перебор, но на обычных данных имхо будет работать быстро, т.к. будет быстро отсекать плохие варианты. По крайней мере если вам нужны весьма похожие строки.

Здравствуйте, Videoman, Вы писали:

V>Заранее, спасибо большое всем откликнувшимся!
Я сталкивался, но ничего лучше чем использования flann (https://www.cs.ubc.ca/research/flann/) с хэмминоговой метрикой не придумал. Но времени было немного на поиски. Как уже было упомянуто, если строки получаются каким нибудь генератором (полиномом или еще чем) задачу можно решить.

Здравствуйте, Videoman, Вы писали:

V>Есть следующая задача:
V>- Есть битовая строка
V>- Задано максимальное расстояние
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

Задачка для PATRICIA trie.

V>Вроде бы на форуме мелькало, но с ходу найти не получается. Задача кажется не сложной. Может быть, туплю. Если кто-то в теме, просьба подсказать куда копать? Желательно как можно проще. Еще лучше если можно будет быстренько "наложить" на STL.

https://github.com/uxn/patl/tree/vc12
Моя либа, самый свежий публичный вариант. Там есть patl::hamming_distance, пример использования в demos/insider. Для битовых строк понадобится примерно такой компаратор:

using bit_string = std::bitset<BIT_LENGTH>;

namespace uxn { namespace patl {

template <>
class bit_comparator<bit_string, 0>
{
    typedef bit_string value_type;

public:
    typedef bool char_type;

    static const word_t bit_size = 1;

    word_t bit_length(const value_type &v) const
    {
        return v.size();
    }

    word_t get_bit(const value_type &v, word_t id) const
    {
        return v.test(id) ? 1 : 0;
    }

    word_t bit_mismatch(const value_type &a, const value_type &b, word_t skip = 0) const
    {
        if (&a == &b)
            return ~word_t(0);
        for (auto i{skip}; i != a.size(); ++i)
        {
            if (a.test(i) != b.test(i))
                return i;
        }
        return ~word_t(0);
    }
};

} } // uxn::patl

Спасибо всем откликнувшимся. К сожалению, пока-что, прояснения не наступило. Все как и думал сам, деревья-деревья .... лес короче. Нужно немного времени что-бы разобраться и вникнуть. Пока, больше всего, понравилось и показалось более понятным VP-Tree. Скорее всего потому, что оно ближе всего к BSP дереву в 3D. Пока погрузился во всяческие исследования и конкретней среагировать не могу.
Вообще задача, как обычно, оказалась более комплексной: как я понял — это audio feature extraction на двух аудио-потоках с последующим поиском отличий (поиск min editing distance).

Здравствуйте, Videoman, Вы писали:

V>Вообще задача, как обычно, оказалась более комплексной: как я понял — это audio feature extraction на двух аудио-потоках с последующим поиском отличий (поиск min editing distance).
Что бы быстро искать надо не расстояние, а функции сравнения иметь.

Здравствуйте, R.K., Вы писали:

V>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

RK>Задачка для PATRICIA trie.
И чем суффиксное дерево поможет в поиске максимального расстояния?

Здравствуйте, Videoman, Вы писали:

V>Есть следующая задача:
V>- Есть битовая строка
V>- Задано максимальное расстояние
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

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

В общем случае надо проксорить каждую строку с оригиналом и посчитать число оставшихся бит.

Здравствуйте, Videoman, Вы писали:

V>Спасибо всем откликнувшимся. К сожалению, пока-что, прояснения не наступило. Все как и думал сам, деревья-деревья .... лес короче. Нужно немного времени что-бы разобраться и вникнуть. Пока, больше всего, понравилось и показалось более понятным VP-Tree. Скорее всего потому, что оно ближе всего к BSP дереву в 3D.

Деревья строить надо и перебирать по битику! Если данные поступили один раз и найти нужно один раз, то тупой и быстрый перебор 8-байтными словами -- то что нужно. Если много раз, то можно данные упорядочить по числу установленных бит в векторе: тогда поиск сужается до диапазона [nbits — hdist, nbits + hdist], где nbits -- число установленных бит в векторе, hdist -- дистанция Хэмминга.

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, R.K., Вы писали:

V>>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

RK>>Задачка для PATRICIA trie.
_>И чем суффиксное дерево поможет в поиске максимального расстояния?

Trie это не суффиксное дерево. Оно может исполнять функцию suffix tree, когда используется для индексации всех суффиксов некоторой строки. А в более простом классическом варианте trie индексирует набор строк, примерно как search tree, но с дополнительными функциями за счет того, что для ветвления в trie используются несовпадающие символы строк. В PATRICIA trie, в свою очередь, для ветвления используются несовпадающие биты строк, что позволяет автоматически решить проблему большого количества символов в алфавите и делает структуру дерева наиболее простой и эффективной из возможных — binary tree.
После того, как мы построили trie над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку.

Здравствуйте, R.K., Вы писали:

RK>После того, как мы построили trie над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку.
Это здорово, но чем это поможет в поиске максимально удалённых по растоянию элементов?

Здравствуйте, Videoman, Вы писали:

V>Заранее, спасибо большое всем откликнувшимся!


IMHO, верно тебе бор советовали. Только надо его не из битов делать, а сразу из чётвёрок битов, или сразу 8-рок, даже
Если памяти не особо жаль, то узел дерева из тетрад -- это просто 16 смещений вперёд, или 0-й, если тетрада в узле не используется.

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

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

p. s.
Да, как сделать быстро перебор всех на расстоянии не больше чем. Просто генерим массив из 16 тетрад:

deltas[16] = { 0, //  0 бит 
    0x1, 0x2, 0x4, 0x8, //   1 бит
    0x3, 0x5, 0x9, 0x6, 0xA, 0xC, // 2 бита
    0x7, 0xB, 0xD, 0xE, // 3 бита
    0xF // 4 бита, на самом деле не нужно
};

Соответственно, если допустимой дистанции осталось менее 4 бит, то берём соответствующий отрезок массива deltas, последовательно ксорим с обьразцом и берём из узла варианты продолжения + сразу вычитаем скока надо бит. Если 4 и более, то берём все варианты в узле подряд и вычитаем число бит из разницы.

Здравствуйте, Videoman, Вы писали:

V>Есть следующая задача:
V>- Есть битовая строка
V>- Задано максимальное расстояние
V>Необходимо:
V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

Не надо никаких структур. Это чисто алгоритмическая задача, а не структурная по данным. Простое поле (битовое или текстовое) и хороший алгоритм. Всё! Опять же Radix Search. Алгоритм отработан и доказан математически. В него (во внутрь) можно встроить свои "особенности". Но классика — есть классика. Лучше не придумаешь, а только испортишь.