Поиск последовательности и теория подобия (Delphi)
Исходные данные:
1. Имеется вектор A[0..N], каждый элемент которого задан целым числом. Порядок числа N - сотни тысяч, миллион
2. Имеется матрица B[0..k][0..l], каждый элемент которой является целым числом. Порядок чисел k, l - единицы, десятки
Матрица B фактически содержит значения функции (т.е. если в визуальном виде представить матрицу B, то получится 3D поверхность правильной формы (в смысле не хаотичный набор случайных чисел)).
Фактически вектор A - это объединение различных матриц B, собранных в вектор [0..k*l]. Т.е. чтобы было понятнее, то вектор A - это бинарный файл, состоящий из множестка матриц B, растянутых в вектор.
Задача стостоит в том, чтобы:
1. Найти значение смещения в векторе A, по которому находится матрица, наиболее похожая для заданной матрицы B. Т.е. фактически найти смещение в файле, по которому находятся значения 3D графика, максимально похожего на значения 3D графика, заданного матрицей B.
2. Для найденного смещения вывести меру похожести между заданной матрицы B и найденной матрицей в векторе A.
3. Т.к. смещений, описанных в п.1 может быть несколько, то необходимо в цикле получить заданное количество (задается пользователем) смещений и меры похожести.
Насколько я понимаю, данная задача решается вейвлетами, однако мне подойдут и другие решения, которые решат эту задачу. Поэтому перед тем, как браться за решение этой задачи предварительно должен быть согласован алгоритм ее решения.
При определении меры похожести матриц нужно учитывать не их разницу значений, а производные. Таким образом максимально похожими считаются графики (т.е. матрицы B), у которых форма самих графиков наиболее похожа.
Результатом работы должна быть программа на любой из версий Delphi4,5,6,7, реализующая данную задачу вместе с исходником.
Исходный текст программы должен быть сделан в виде отдельного Unit, таким образом, чтобы его могли использовать другие программы на Delphi.
В качестве примера, вектор A в прикрепленном архиве находится в файле a.bin, исходная матрица размером 11 на 16 в файле b.bin. Если представить данную матрицу в графическом виде, то получим "правильную" поверхность. Типы данных в файле a.bin и b.bin - BYTE. Т.е. каждое значение представляется байтом в диапазоне 0..255
Соответственно в векторе A матрицы, похожие на матрицу B встретятся по адресам: 0x01D5, 0x0288, 0x006F, 0x0122
В данном примере в качестве значений матрицы B используются значения из диапазона 0..255 и помещающиеся в одном байте. В реальности значения могут быть WORD, DWORD, а также знаковые и беззнаковые.
Для теста а также для выполнения задания я готов предоставить дополнительно различные варианты векторов A и матриц B.
Оплатить работу готов Яндекс.Деньгами.