алгоритм — проверка наличия двоичной строки в базе данных похожих строк

Я должен написать программу для приложения на C ++, которая генерирует n-битные двоичные строки, которые необходимо сохранить для дальнейшей обработки.

Вопрос 1) Но всякий раз, когда генерируется новая строка, ее необходимо проверить, если она уже присутствует в базе данных. Если это так, его не следует добавлять.

Один из возможных способов сделать это — сохранить хеш-таблицу для поиска (например, STL-карту), где ключами являются десятичные значения двоичной строки. Но проблема в том, что n может быть очень большим, так как сохранение его десятичного значения неосуществимо. То есть иногда n может достигать 200+.

Кроме того, иногда биты n-битной строки не определены.
Например: — если n = 4, строка может иметь форму 01xx. Где младшие два бита не определены. В этом случае 01xx фактически представляет 4 полностью указанные 4-битные строки — 0100,0101,0110,0111. Таким образом, если 01xx находится в базе данных и создается 0110, то 0110 не должен храниться в базе данных.

Можете ли вы предложить, что может быть эффективным способом проверить это.

Иногда я могу придумать это:

1) Выполнить поиск по всей базе данных строк и сравнить вновь сгенерированную строку одну за другой со строками в базе данных. Это наивный метод, который будет иметь сложность O (mn), где m — это количество строк в базе данных.

2) Храните строки в двоичной структуре дерева решений. В этом типе метода поиск будет логарифмическим?

3) Для каждой позиции бита в строке — я храню строки, в которых указано их значение.
Например: — для n = 4, если база данных содержит: — 01xx и 1xx1, тогда эта информация может быть сохранена как: —

0 — 1xx1

1 —

2 — 01xx

3 — 01xx, 1xx1

0 означает, что LSB установлен. 3 означает, что MSB установлен. Поэтому, если генерируется новая строка, скажем, 0101, я могу искать ее либо в 2, либо в 3. Этот метод кажется дорогим на использование памяти.

Можете ли вы предложить несколько эффективных способов сделать этот поиск строки.

Вопрос 2) Кроме того, с точки зрения реализации C ++, что может быть эффективным способом хранения этих n-битных строк? Следует отметить, что большую часть времени большинство битов в n-битной строке не определены. Таким образом, вместо резервирования пространства в памяти, пропорционального n, имеет смысл хранить только указанные биты.

То есть n может быть 10. Но сгенерированная строка может выглядеть примерно так: — 1x1xxxxxxx. В этом случае имеет смысл хранить что-то вроде {(9,1), (7,1)}. Так я должен хранить строки как векторы 2-кортежей? В таком случае, что может быть хорошим способом для хранения базы данных этих строк?