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

MP>из постановки задачи следует, что для определения степени похожести (similarity) вам надо испольовать просто match (= количество совпадающих элементов).
MP>Если будете читать литературу по similarities — не искушайтесь пользовать продвинутые функции типа cosine similarity — они, конечно, модные и красивые по замыслу, но работают хуже, чем та же евклидова дистанция. Для обобщения решения насчитанные similarities лучше отнормировать в пределах [0..1]. Но в Вашей постановке задачи это не критично.

А почему расстояние Евклида, а не Хэмминга (это, кстати, частный случай манхеттенского расстояния)?! Или Хэмминг заморочнее?

---

На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию?

Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.
Всё множество векторов разбиваем на подмножества с одинаковыми весами (векторы, лежащие на "сферах" соответствующего радиуса).
И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны.

Очевидно, что сфера D/2 (где D — размерность пространства) имеет максимальную "площадь", и мы можем нарваться на линейный перебор.

Чтобы избежать этого, введём ещё одно разбиение — по расстояниям от какого-нибудь вектора на сфере D/2 — например, от 01010101...01 или 00...011...1.

То есть, всем векторам сопоставлены несколько чисел — расстояния от нескольких опорных точек.
Нужно найти вектор, чьи расстояния минимально отличаются от расстояний искомого вектора. То есть, некий аналог триангуляции

Таким образом, мы из D-мерного двоичного пространства перебрались в малоразмерное D-ричное.
(Хотя подразумевается, что это пространство N-мерное, где N — количество исходных векторов).

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