# Finding patterns in vectors
**URL:** https://discourse.julialang.org/t/finding-patterns-in-vectors/82833
**Category:** General Usage
**Tags:** array, pattern-matching, vector
**Created:** [June 15, 2022, 7:41pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833 "2022-06-15T19:41:09Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@duodenum](https://discourse.julialang.org/u/duodenum)
#### Post date: [June 15, 2022, 7:41pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/1 "2022-06-15T19:41:09Z")
Hello,
I’m trying to write a Julia implementation of Lempel-Ziv Complexity. Specifically I’m stuck at the pattern-finding part of the algorithm. Let’s say I have a vector: [1, 0, 0, 1]. It contains the pattern [1, 0] but doesn’t contain the pattern [1,1] [0,1,1]; so it should start reading from the left and go to the right. I need an operation that gives a logical true when I give the [1, 0] and the aforementioned vector and false when I give it [1,1]. The “issubset” function still gives a true when I type issubset([1, 0, 0, 1], [0, 1, 1]).
Any help is greatly appreciated,
Yasir
---
### Author:  [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)
#### Post date: [June 15, 2022, 8:10pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/2 "2022-06-15T20:10:37Z")
What `issubset(a, b)` tests is “whether every element of a is also in b”, because this is the definition of subset, it disregards the order the elements are stored in the `Vector` because “order” does not exist in sets.
You are not entirely clear on what you want. Do you want to check if `b` is a prefix of `a`? In this case use: `is_prefix(a, b) = @view(a[keys(b)]) == b`; if you want to check if there is a sub-sequence inside `a` that matches `b` then you can use `any((x -> is_prefix(x, b)), (a[i:(i+length(b)-1)] for i in firstindex(a):(lastindex(a) - length(b) + 1)))`
---
### Author:  [@duodenum](https://discourse.julialang.org/u/duodenum)
#### Post date: [June 16, 2022, 5:56am UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/3 "2022-06-16T05:56:37Z")
I was actually looking for the second one. Works like a charm, thanks so much! It seems should delve more into higher order functions.
---
### Author:  [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)
#### Post date: [June 16, 2022, 12:28pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/4 "2022-06-16T12:28:57Z")
Could we do this with a simpler for loop?
```julia
# is y subarray of x?
function issubarray(y,x)
ny = length(y)
for i in eachindex(x)[begin:end-ny+1]
y == view(x,i:i+ny-1) && (return true)
end
return false
end
```
Thanks.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 16, 2022, 5:06pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/5 "2022-06-16T17:06:48Z")
```julia
using IterTools
binc(b,c)=Tuple(b) ∈ IterTools.partition(c,length(b),1)
```
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 16, 2022, 5:23pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/6 "2022-06-16T17:23:04Z")
Also consider using the findfirst function if this is right for you
```julia
findfirst(pattern::AbstractVector{<:Union{Int8,UInt8}}, A::AbstractVector{<:Union{Int8,UInt8}})
```
---
### Author:  [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)
#### Post date: [June 16, 2022, 7:48pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/7 "2022-06-16T19:48:30Z")
@rocco_sprmnt21 is right. I did use an old version of Julia so I did not see this:
```julia
help?> findfirst([0x0, 0x01, 0x0], [0x0, 0x1])
findfirst(pattern::AbstractVector{<:Union{Int8,UInt8}},
A::AbstractVector{<:Union{Int8,UInt8}})
Find the first occurrence of sequence pattern in vector A.
│ Julia 1.6
│
│ This method requires at least Julia 1.6.
Examples
≡≡≡≡≡≡≡≡≡≡
julia> findfirst([0x52, 0x62], [0x40, 0x52, 0x62, 0x63])
2:3
```
You can just call `findfirst(b, a) !== nothing` then.
---
### Author:  [@duodenum](https://discourse.julialang.org/u/duodenum)
#### Post date: [June 18, 2022, 10:35am UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/8 "2022-06-18T10:35:10Z")
Thanks so much for your very helpful comments!!!
---
### Author:  [@pitsianis](https://discourse.julialang.org/u/pitsianis)
#### Post date: [June 20, 2022, 5:04pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/9 "2022-06-20T17:04:29Z")
The approaches proposed so far have complexity O(m n) when you are searching for a pattern of length m in a vector of length n. When m is large, you may want to consider correlation in the Fourier domain that would result to O((m+n) \log(m+n)).
Here is a shameless plug to our work to compute the Pearson correlation coefficient in the Fourier domain and accurately locate patterns even when they have been scaled and translated: the registered package [FastLocalCorrelationCoefficients.jl](https://github.com/pitsianis/FastLocalCorrelationCoefficients.jl)
---
### Author:  [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)
#### Post date: [June 20, 2022, 8:06pm UTC](https://discourse.julialang.org/t/finding-patterns-in-vectors/82833/10 "2022-06-20T20:06:39Z")
A very similar problem is finding _similar_ subsequences in a vector, or finding _approximate_ matches of a pattern in a vector.
The package
> **[GitHub - baggepinnen/MatrixProfile.jl: Time-series analysis using the Matrix...](https://github.com/baggepinnen/MatrixProfile.jl)**
>
> Time-series analysis using the Matrix profile in Julia - GitHub - baggepinnen/MatrixProfile.jl: Time-series analysis using the Matrix profile in Julia
contains several methods to look for such matches.