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

MP>стоп машины! ... Словом, это были две разные мысли.

Ааа. Кудряво вышло.
То есть, "если уж не Хэмминг — то хотя бы Евклид, и не заморачиваться прочими изощрениями".

К>>

---

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

MP>тогда {0,1,0,1}, {1,1,0,0}, {1,0,1,0} и т.д. будут иметь один и тот же "вес", не смотря на то, что "активированы" у них разные измерения.
Именно так. Твои векторы лежат на разных краях одной сферы с радиусом 2 и центром в {0,0,0,0}.

К>>Всё множество векторов разбиваем на подмножества с одинаковыми весами (векторы, лежащие на "сферах" соответствующего радиуса).

MP>поправьте меня, если я ошибаюсь, но мне кажется, что из-за "булевости" всех массивов в исходной задаче, радиусы всех возможных сфер будут равны "весу" подгруппы (за исключением null space {0,0,..,0})

Ну да. А почему "за исключением"? Вектор 0000 лежит на сфере нулевого радиуса. Вектор 1111 — на сфере радиуса 4.
Площадь сферы равна C(D,R).

Может быть, слово "сфера" неудачно. Это грань гипероктаэдра (эквидистанта по манхеттенской метрике).

К>>И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны.
MP>... не понял, куда отступать? если мы уже в верной подгруппе, то остается только менять измерения. а отступать-то, вроде и некуда.

Ну если мы в верной подгруппе не нашли совпадения. Задача-то найти вектор, наиболее близкий к заданному, а не обязательно — точно совпадающий.

Для точного совпадения все эти танцы с бубном не нужны: вводим абсолютно произвольный (например, лексикографический) порядок, сортируем вектора в этом порядке, и двоичным поиском скачем по этой последовательности. Можно ещё хэш-функцию прикрутить для ускорения поиска — порядок-то нас не интересует.

Расстояние до 0000 — это не хэш-функция, точнее, не только хэш-функция. Потому что нас интересует не только тот же самый класс, но и смежные классы (тогда как хэш-функция хэширует, т.е. перемешивает, классы в произвольном порядке).

MP>в итоге получаем lookup tables в количестве, равном количеству опорных точек, с количеством элементов n(n-1)/2 каждая.

Да, lookup table — возможно, иерархически устроенная.

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

... но при этом радикально сужаем и очень постепенно наращиваем круг поиска.

MP>короче, вроде, решение я понял и, на мой взгляд, оно должно работать.
MP>но по эффективности и количеству используемых данных оно уступает простой lookup table похожестей

Я не очень понял твоё решение.
Как с помощью таблицы d[i,j] = |v[i],v[j]| можно найти v[k] наиболее близкий к данному вектору u?

Кроме того, "по количеству данных" моё решение занимает O(N*K) памяти где K — количество опорных точек (какое-то небольшое). А таблица похожестей — это O(N*N).