У меня есть вопрос по одному методу. Он вкратце изложен тут (pdf, ~500 Кб - там включены изображения, потому так много, а вообще 4 странички):
http://slil.ru/23712522
Вопрос в общем такой. Можно ли как-то ускорить процесс поиска одной короткой строки в другой длинной. Ищется не полное совпадение. Обе строки содержат случайные элементы. Где что можно по этому поводу почитать. Самое интересное в принципиальной такой возможности. Нужно для убыстрения алгоритма.
P.S. Прошу простить, я ошибся в формуле при определении ВКФ. Там нужно понимать:
![$$r[\tau] = \left(\sum^{L-1}_{k=0}{\xi_2}[\tau+k] \cdot {\xi_1}[k]\right)^2$$](https://dxdy-04.korotkov.co.uk/f/f/5/8/f5808c5f2c55ac8a84d50fad2c391c3482.png "$$r[\tau] = \left(\sum^{L-1}_{k=0}{\xi_2}[\tau+k] \cdot {\xi_1}[k]\right)^2$$")
, а не
![$$r[\tau] = \sum^{L-1}_{k=0}\left({\xi_2}[\tau+k] - {\xi_1}[k]\right)^2$$](https://dxdy-04.korotkov.co.uk/f/7/0/e/70e6d7b73febd59d60e18005810b587c82.png "$$r[\tau] = \sum^{L-1}_{k=0}\left({\xi_2}[\tau+k] - {\xi_1}[k]\right)^2$$")
Давно уже не занимался, подзабыл теорию. В документе же при расчётах свёртка считается через частотную область при помощи прямого и обратного БПФ. Теперь, кажется ничего не напутал. Квадрат я взял только для того, чтобы по графику вручную находить максимум -- это для экспериментов. Ну и, конечно, чтобы всё было положительным.
09.01.2007, 21:26 
