Сопоставить двоичный шаблон, включая «все равно»

У меня есть набор битовых шаблонов, и я хочу найти индекс элемента в наборе, который соответствует заданному входу.Битовая комбинация содержит биты «безразлично», то есть x-es, которые соответствуют как 0, так и 1.Пример Набор битовых шаблоновЗатем попытка сопоставления 0110 должна вернуть индекс 1, а 1011 должна вернуть индекс 4.Как решить эту проблему быстрее, чем линейный поиск по элементам?Я предполагаю, что можно было бы создать что-то вроде двоичного дерева, но тогда как создать такое дерево разумно?Существуют ли другие эффективные структуры /алгоритмы данных для такой проблемы, в первую очередь с точки зрения эффективности запросов, а также требований к хранилищу.Битовые шаблоны будут 64-битными (или более)Количество элементов в наборе будет в порядке 10 ^ 5 - 10 ^ 7.Не все битовые комбинации представлены в наборе, например, в примере 0000 не представленВ наборе данных будет много x-овБитовая строка будет соответствовать только одному из элементов в набореУ меня есть два разных случая, в которых мне нужно решить эту проблемуСлучай 1: у меня есть возможность сделать много предварительных вычисленийСлучай 2: Новые элементы будут добавляться в набор на летуОбновление . X-es с большей вероятностью будут отображаться в одних битовых позициях, чем в других, то есть в одних битовых позициях будут преобладать x-es, а в других - в основном нули /единицы.
7 голосов | спросил Petter T 10 FebruaryEurope/MoscowbMon, 10 Feb 2014 13:47:04 +0400000000pmMon, 10 Feb 2014 13:47:04 +040014 2014, 13:47:04

0 ответов


Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132