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

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

Здравствуйте, 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).
Что бы быстро искать надо не расстояние, а функции сравнения иметь.