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

Пусть дан ряд чисел X=(X1,X2,X3,X4, ..,Xn). Будем называть его гистограммой (хотя это может быть произвольный упорядоченный набор значений, вектор). На комопненты гистограммы наложим ограничение — все значения лежат в фиксированном, конечном интервале. В наших примерах это будет интервал от 0 до 100.
Итак, имеется большой набор гистограмм и есть шаблонная гистограмма, к которой мы хотим найти наиболее похожую гистограмму из имеющегося набора.
Введем меру различий двух гистограмм, равной максимальной разнице между двумя соответствующими компонентами (эта мера называется также расстоянием Чебышева):

d(X, Y) = max(|Xi-Yi|)

При решении задачи поиска «в лоб» мы будем перебирать гистограммы из заданного набора, и сравнивать их с шаблоном. Для каждого сравнения мы будем перебирать компоненты гистограмм, считать их разности и находить максимальную из них. Понятно, что это долго, а нам бы хотелось ускорить этот процесс.