发现模式在数组

最近,我的同事杰夫问我是否要看他写一些代码来找到一个模式的数字在一个更大的数组。没有看他的代码,我问他是否曾使用strfind,尽管他不是字符串数据。他发现,它解决了他的问题,速度比他的m文件。同时,我想看看我写了一个简单的算法我想m文件。我这里展示和讨论的结果。

内容

简单的测试数据

让我开始很简单的测试数据可以肯定所有算法都得到正确的答案。

一个= [0 1 4 9 16 4 9];b =双(“这是2003年”。);

第一个算法:findpattern

这是第一个findpattern算法。

类型findpattern

函数idx = findpattern (in_array模式)% findpattern数组中找到一个模式。% % K = FINDPATTERN(数组、模式)返回起始指数%的任何数组中出现的模式。数组和模式%可以是任意字符和数字类型的混合物。% %的例子:% = [0 1 4 9 16 4 9];% b =双('今年是2003。');% findpattern(9[4]),返回[3 6]% findpattern (a,[4] 9日)返回[]% findpattern (b,‘2003’)返回13% findpattern (b, uint8(' 2003 '))返回13% %看到STRFIND,比较字符串,STRNCMP STRMATCH。%算法:%找到所有的每个数字出现的模式。% % n元素模式,结果是一个n元素单元阵列。% i细胞包含在输入数组相匹配的第i个元素百分比的模式。% %的模式存在于输入流时,将会有一个连续的连续整数序列%细胞。 % As currently implemented, this routine has poor performance for patterns % with more than half a dozen elements where the first element in the % pattern matches many positions in the array. locations = cell(1, numel(pattern)); for p = 1:(numel(pattern)) locations{p} = find(in_array == pattern(p)); end % Find instances of the pattern in the array. idx = []; for p = 1:numel(locations{1}) % Look for a consecutive progression of locations. start_value = locations{1}(p); for q = 2:numel(locations) found = true; if (~any((start_value + q - 1) == locations{q})) found = false; break; end end if (found) idx(end + 1) = locations{1}(p); end end

你会注意到杰夫选择派生模式存在的信息存储在一个单元阵列,然后寻找连续位置。

下面是一些使用结果findpattern。首先,我将f函数句柄函数的问题。然后我可以重用相同的代码的其他情况下只需重新定义函数。

f = @findpattern t (4) = false;t (1) = isequal (f (a, 9 [4]), 6 [3]);t (2) = isempty (f (a、4 [9]));t (3) = isequal (f (b,“2003”),13);t (4) = isequal (f (b, uint8 (“2003”13)));极好的=所有(t = = true)

f = @findpattern极好的= 1

我的家酿算法:findPattern2

这是我自己的算法。这里的想法是找到可能的模式首先位置,精选出来,通过游行模式我假设通常较小,通常小很多,比数据。

类型findPattern2

函数开始= findPattern2(数组,模式)% findPattern2定位模式在一个数组中。% % = findPattern2指数(数组,模式)发现%的起始索引模式在数组中。% %的例子:% = [0 1 4 9 16 4 9];% patt = 9 [4];% = findPattern2指数(a型)%指数= % 3 6%假设目前的模式和非空%向量数组,但是没有检查。%这个算法,我遍历模式元素。len =长度(模式);%,找到候选人的位置;即。,match the first element in the % pattern. start = find(array==pattern(1)); % Next remove start values that are too close to the end to possibly match % the pattern. endVals = start+len-1; start(endVals>length(array)) = []; % Next, loop over elements of pattern, usually much shorter than length of % array, to check which possible locations are valid still. for pattval = 2:len % check viable locations in array locs = pattern(pattval) == array(start+pattval-1); % delete false ones from indices start(~locs) = []; end

得到结果和时间。

f = @findPattern2 t (1) = isequal (f (a, 9 [4]), 6 [3]);t (2) = isempty (f (a、4 [9]));t (3) = isequal (f (b,“2003”),13);t (4) = isequal (f (b, uint8 (“2003”13)));极好的=所有(t = = true)

f = @findPattern2极好的= 1

使用strfind

接下来,我测试使用相同的数据strfind。尽管它的名字,strfind可以愉快地处理非字符数据类型,特别是双打和整数。

f = @strfind t (1) = isequal (f (a, 9 [4]), 6 [3]);t (2) = isempty (f (a、4 [9]));t (3) = isequal (f (b,“2003”),13);t (4) = isequal (f (b, uint8 (“2003”13)));极好的=所有(t = = true)

f = @strfind极好的= 1

用例和性能

杰夫更详细地描述了他解决问题。他有一个文件有多个图像,与存储的数据uint8。图像由一个特定的模式。让我给你一个图像序列,在处理和提取帧。

负载forloren图像(X(:,:,: 17)),轴从谁X

类属性X 4 - d 26726400 uint8名字大小字节

现在让我展示和时间找到原始数据中的模式。数据包含29图像。

清晰的负载imrawdata谁模式= (254 255 0 224);f = @ () findpattern (rawdata、模式);tfind时间= (f);f = @ () findPattern2 (rawdata、模式);tfind时间(2)= (f);f = @ () strfind (rawdata、模式);tfind时间(3)= (f)

类属性名称大小字节rawdata 1 x1259716 1259716 uint8 tfind = 0.80941 0.011273 0.019194

拼图和后续步骤

在大数据集的情况下,strfind不是最快的算法,虽然我在小得多的数据发现,strfind的表现findPattern2。一些可能的原因findPattern2是速度最快的三种算法:

它不是通用和没有错误检查

只有写向量,

它无法处理情况|南|年代可能涉及。

如果我找到原因,我将让你知道。与此同时,如果你有任何想法添加,请发表评论在这里。

得到了MATLAB代码

使用MATLAB®7.6发表