Здравствуйте, R.K., Вы писали:
V>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.
RK>Задачка для PATRICIA trie.
И чем суффиксное дерево поможет в поиске максимального расстояния?
Здравствуйте, Videoman, Вы писали:
V>Есть следующая задача: V>- Есть битовая строка V>- Задано максимальное расстояние V>Необходимо: V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.
Эта задача из области помехоустойчивых кодов (Боуза-Чоудхури-Хоквингема они же BCH-коды, коды Хэмминга как более частный случай). Верней, там решается обратная задача: даётся повреждённый код и нужно найти оригинальный имеющий наименьшую хэмминговскую дистанцию. Может знакомство с теорией на что-то натолкнёт.
В общем случае надо проксорить каждую строку с оригиналом и посчитать число оставшихся бит.
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, R.K., Вы писали:
V>>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.
RK>>Задачка для PATRICIA trie. _>И чем суффиксное дерево поможет в поиске максимального расстояния?
Подвышенной тормознутостью (по сравнению с оптимизировнной ксоркой 64-битными словами).
Здравствуйте, 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 над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку.
Это здорово, но чем это поможет в поиске максимально удалённых по растоянию элементов?
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, R.K., Вы писали:
RK>>После того, как мы построили trie над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку. _>Это здорово, но чем это поможет в поиске максимально удалённых по растоянию элементов?
Я написал, чем поможет. Задача звучала так:
V>Есть следующая задача: V>- Есть битовая строка V>- Задано максимальное расстояние V>Необходимо: V>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.
Это достаточно точная формулировка одного из эффективных способов применения 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. Алгоритм отработан и доказан математически. В него (во внутрь) можно встроить свои "особенности". Но классика — есть классика. Лучше не придумаешь, а только испортишь.
В общем, спасибо всем большое за подсказки. Решил задачу. Остановились на VP-Tree (Vantage Point Tree)
Почему так долго:
— решил написать когда уже все отладил и решил всю задачу в комплексе, не только эту
— долго смотрел что вообще есть, какие подходы, какие структуры
— все готовые решения которые видел в интернете — академические какашки (в плане кода), существующие только для демонстрации, где куча new и С с классами
— долго убеждался что все отлажено и работает как надо
Результат:
В качестве хешей у меня получились uint32_t. VP-Tree очень быстро работает, начинает обгонял линейный поиск на размерах, где-то, больше 4096. При >= 10М хешей начинает обгонять "грубую силу" в 1000 и более раз.
Для тех кому интересно что за дерево(структура) и как устроено:
Это дерево строится рекурсивно: Берем наши хеши. Выбираем любой элемент случайно и частично сортируем их все по расстоянию (Хемминга в моем случае) до этого выбранного элемента. Далее берем медиану и все что меньше по расстоянию от медианы в левое поддерево, а все что больше в правое поддерево. Дальше повторяем рекурсивно, пока мы не отсортируем все хеши.
Поиск:
Берем любой хеш и заданный порог. Идем в корень дерева. Считаем расстояние от корня до нашего хеша. Если подходит, то добавляем хеш в список. Прибавляем к нему наш порог, чтобы получить максимальное расстояние поиска. Сравниваем максимальное расстояние с заданным порогом и идем в левое поддерево, если расстояние меньше порога, в оба, если меньше либо равно, и в правое, если строго больше порога. Далее повторяем шаги рекурсивно, пока не соберем все элементы.
