Поиск подмассива в массиве

Простейшие вопросы в области инженерной разработки
Ответить
alexander756

Activity
professional
professional
Сообщения: 301
Зарегистрирован: 12 июн 2008, 19:56
Награды: 1
Версия LabVIEW: 8.6; 2009
Откуда: Montreal
Контактная информация:

Поиск подмассива в массиве

Сообщение alexander756 »

Добрый день,

подскажите пожалуйста способ определить положение заданного подмассива в массиве с возможностью регулировки допуска совпадения (1-20%).

Например

@1=(135, 202, 321, 473, 503, 68, 705, 82, 903);
@2=(473, 503, 68, 705);
или подмассив может быть и такой:
@2=(471, 504, 69, 705);

Хотелось чтобы функция вернула бы 3 -> место начала подмассива
Аватара пользователя
Konstantin Sumenko

Activity Bronze
expert
expert
Сообщения: 1439
Зарегистрирован: 17 июл 2008, 12:20
Награды: 2
Версия LabVIEW: 2010
Откуда: Moscow
Поблагодарили: 1 раз
Контактная информация:

Re: поиск подмассива в массиве

Сообщение Konstantin Sumenko »

Временно сижу без LV, поэтому напишу:
1) Берем запоминаем длину (n) подмассива (1).
2) Ищем через search array в исходном массиве ищем первый элемент подмассива (1).
3) Если элемент найден, то с начиная с него (индекс x) и далее берем подмассив (2) исходного массива длины (n)- array subset.
4) Имеем подмассивы: (1)- данный по условию, (2)- полученный.
5) Применям сравнение equal? поэлементно: получаем битовый массив длины (n), где true- совпадение, false- иначе.
6) Если кол-во true в % соотношении подходит, то возвращаем (индекс x).
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: поиск подмассива в массиве

Сообщение mzu2006 »

Crowbar писал(а):ищем первый элемент подмассива
А если первый элемент отличается на 1?

Нет, IMHO, тут надо считать корреляции одного и другого массивов. И резкий максимум в корреляционной функции будет давать величину смещения подмассива в массиве. Отличие величины максимума от единицы - давать оценку точкности совпадения. Корреляцию, естественно, считать через БПФ.
Аватара пользователя
Konstantin Sumenko

Activity Bronze
expert
expert
Сообщения: 1439
Зарегистрирован: 17 июл 2008, 12:20
Награды: 2
Версия LabVIEW: 2010
Откуда: Moscow
Поблагодарили: 1 раз
Контактная информация:

Re: поиск подмассива в массиве

Сообщение Konstantin Sumenko »

Кстати, а конечный элемент подмассива тоже может содержать несуществующий элемент исходного массива? P.S: зачем корреляцию считать через БПФ, когда есть готовые VI с той же корреляцией и сверткой и максимальные размеры массивов не оговаривались?
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: поиск подмассива в массиве

Сообщение mzu2006 »

Crowbar писал(а):P.S: зачем корреляцию считать через БПФ, когда есть готовые VI с той же корреляцией и сверткой и максимальные размеры массивов не оговаривались?
А, ну это, чтобы никому не пришло в голову по определению интеграл считать ...

Конечно, надо использовать встроенные функции (внутри они сводятся к Cross Correlation и, видимо, к БПФ).
alexander756 писал(а):допуска совпадения
Определи поточнее, plz
Аватара пользователя
Konstantin Sumenko

Activity Bronze
expert
expert
Сообщения: 1439
Зарегистрирован: 17 июл 2008, 12:20
Награды: 2
Версия LabVIEW: 2010
Откуда: Moscow
Поблагодарили: 1 раз
Контактная информация:

Re: поиск подмассива в массиве

Сообщение Konstantin Sumenko »

Скорее всего встроенные функции используют несколько подходов в зависимости от длины используемых массивов (Там и БПФ-обратное БПФ и прямое высчитывание свертки и т.п).
Аватара пользователя
Eugen Graf

Activity Professionalism Silver Black
guru
guru
Сообщения: 6502
Зарегистрирован: 13 ноя 2007, 02:20
Награды: 4
Версия LabVIEW: 2009
Откуда: Saarbrücken
Контактная информация:

Re: поиск подмассива в массиве

Сообщение Eugen Graf »

А что если индексировать первый массив и сравнивать каждый его элемент с первым элементом второго подмассива с помощью in Range and Course, если совпало, то сравниваем следующий элемент первого массива со вторым элементом второго подмассива тем же способом, и если совпало, то так далее. Если где то не совпало, то продолжаем искать дальше (с одним нюансом о котором может быть позже).
alexander756

Activity
professional
professional
Сообщения: 301
Зарегистрирован: 12 июн 2008, 19:56
Награды: 1
Версия LabVIEW: 8.6; 2009
Откуда: Montreal
Контактная информация:

Re: поиск подмассива в массиве

Сообщение alexander756 »

eg писал(а):А что если индексировать первый массив и сравнивать каждый его элемент с первым элементом второго подмассива с помощью in Range and Course, если совпало, то сравниваем следующий элемент первого массива со вторым элементом второго подмассива тем же способом, и если совпало, то так далее. Если где то не совпало, то продолжаем искать дальше (с одним нюансом о котором может быть позже).
Я так и сделал как ты говоришь, вроде как работает (только если tolerance = 0, работать небудет). А как сюда еще добавить, что допускается например какой-то % не совпадения даже с коэффициентом допуска, как писал Crowbar во втором сообщении.
Вложения
search subarray.vi
(10.73 КБ) 267 скачиваний
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: поиск подмассива в массиве

Сообщение mzu2006 »

Crowbar писал(а):Скорее всего встроенные функции используют несколько подходов в зависимости от длины используемых массивов (Там и БПФ-обратное БПФ и прямое высчитывание свертки и т.п).
Да, согласен. Давно не занимался ЧМ ...
eg писал(а):А что если индексировать первый массив ... искать дальше (с одним нюансом о котором может быть позже).
Интересно будет сравнить скорость
Ответить
  • Похожие темы
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в «Для чайников»