how to find percentage of similarity between two arrays.

Suppose x=[1 0 1 0],y=[1 1 1 0] here, if i compare individual elements of x with y, then the highest matching (i have to consider from the beginning of x)is at 3rd and 4th of 2nd array. so the percentage of matching is 50% . how to write matlab code for this.

Imp.:-The point is how much % of x starting from 1st element and serially is matching with y.

Answer 1

[Jan]

I want to share my guess also, perhaps it matchs your needs:

% Method 1:
x  = [1 1 0 0]; 
y  = [1 1 1 0 1 1 0 1];
nx = length(x);
ny = length(y);
yy = [y, nan(1, nx - 1)];  % Append nans to compare the last values
p  = ones(1, ny);          % Pre-allocation [EDITED, was: zeros()]
for iy = 1:ny              % Loop over substrings of y
  match = find(yy(iy:iy + nx - 1) ~= x, 1);
  if ~isempty(match)       % Any match is found
    p(iy) = 100 * (match - 1) / nx;
  end
end
[maxP, maxPos] = max(p)    % Highest in % value and index

If this solves your problem, it is time to search for optimizations.

[EDITED2] Simplified:

% Method 2:
nx = length(x);
ny = length(y);
yy = [y, nan(1, nx - 1)];  % Append nans to compare the last values
p  = zeros(1, ny);         % Pre-allocation (here zeros() is fine)
for iy = 1:ny              % Loop over substrings of y
  p(iy) = find([(yy(iy:iy + nx - 1) ~= x), true], 1) - 1;
end
[maxP, maxPos] = max(100 * p / nx)  % Highest value in % and index

If y is long, it might be cheaper to iterate over the substrings of x:

Note: strfind operates on double vectors directly, as long as they have a row shape. Then:

% Method 3:
p  = zeros(size(y));
nx = length(x);
for ix = 1:nx                       % Loop over substrings of x
  p(strfind(y, x(1:ix))) = ix;      % STRFIND accepts double vectors
end
[maxP, maxPos] = max(100 * p / nx);

Because only the longest match is wanted, it is cheaper to start with the complete x and stop the loop when the first match is found:

% Method 4:
maxP = 0;
for ix = length(x):-1:1           % Start with complete x
  maxPos = strfind(y, x(1:ix));   % Search in y
  if any(maxPos)                  % Success 
    maxP = 100 * ix / length(x);
    break;
  end
end

Now maxPos contains all indices of the occurrences of the longest substring.

Sorry for posting multiple versions. I thought seeing the steps of development might be interesting.

[John BG]

Jan good effort but when you run your code with

x=[1 1 0]

it should give 100% match but it gives 66.6%

regards

John BG

<mailto:[e-mail] [e-mail]>

[Jan]

@John BG: Thanks for finding the bug in the first method. p must be pre-allocated with ones() instead of zeros(). See [EDITED].

@aditya sahu: See [EDITED2] for some simplifications. Unfortunately I'm still not sure, if this does what you are asking for, but it does it efficiently. :-)

Some timings:

x = randi([0,1], 1, 10);
y = randi([0,1], 1, 1e7);
Method 1: 3.63 sec
Method 2: 4.27 sec (!!! Simpler, but slower !!!)
Method 3: 0.20 sec
Method 4: 0.02 sec

[aditya sahu]

Dear @jan simon, your solution is 100% perfect. i am more than happy for your effort and suggestions given, and it is working for me. you are amazing. i accept it. Also thank you vary much to @john,@kssv,@ Stephen Cobeldick. you all are really wonderful guys.god bless you all. Thank you once again.

[aditya sahu]

Dear @jan simon, Thank you once agian. i am having a small doubt , plz see my question below. suppose x=[1 0 1 0 1 1 1] y=[1 1 0 0 0 0 0 0 0 ]; here,percentage match=28.5 and positions starts from 2nd. Now my requirement is the remaining unmatched bit of 1st vector i.e 1 0 1 1 1 , i want to search for the matching with 'y' vector once agin in the next step and its position where it is matched. so once again only [1 0] is matched at index 2. In this way i want to match all remaining elements of x with why with their indexes untill i get 100% match. Thank you.

[Jan]

@aditya sahu: What should happen if the match is found mutliple times?

Let's start with a modified Method 4 packed into a function:

function [maxP, maxPos, maxLen] = FindSubMatch(x, y)
maxLen = 0;
for ix = length(x):-1:1           % Start with complete x
  maxPos = strfind(y, x(1:ix));   % Search in y
  if any(maxPos)                  % Success 
    maxLen = ix;
    break;
  end
end
maxP = 100 * maxLen / length(x);
end

Now this can be called from another function:

function [maxP, maxPos] = FindSubMatchRecursive(x, y)
nx     = length(x);
maxP   = zeros(1, nx);
maxPos = zeros(1, nx);
index  = 0;
while nx > 0
  [maxPi, maxPosi, maxLen] = FindSubMatch(x, y);

    % Store results:
    index         = index + 1;
    maxP(index)   = maxPi;
    maxPos(index) = maxPosi(1);  % The first match only?

    % Prepare data for next iteration:
    x  = x(maxLen + 1:nx);       % Crop the found part
    nx = length(x);
    y(1:maxPosi(1) - 1) = NaN;   % Mask leading values
  end
  maxP   = maxP(1:index);        % Crop unused elements [EDITED]
  maxPos = maxPos(1:index);
  end

I've overwritten the initial part of y in each iteration to consider the "its position where it is matched". But I'm not sure, if this is exactly the wanted procedure. Just try it and modify this to satisfy your needs.

[aditya sahu]

@Jan Simon, thank you very much.it is working exactly as per the requirement,but the index positions are showing for first time where it is matching and in the next subsequent matching the index positions are not found.

[Jan]

Please post an example for the input and the wanted output.

I've added a cropping of the unused elements (see [EDITED]). Then for the input x=[1 0 1 0 1 1 1], y=[1 1 0 0 0 0 0 0 0 ] I get the result:

maxP   = [28 40 33 50 100]
maxPos = [2 2 2 2 2]

This means, that the "10" part is found two times at position 2, then the remaining "1"a are found there also. Is this what you need?

[aditya sahu]

Suppose i take, x=[1 0 1 0 1 1 1], y=[1 1 0 0 0 0 0 0 0 ] then [1 0] (first 2 elements) of x are matching started at position 2, of y and % matching is 28.5. again for x next largest bit/bits matching is [1 0] (3rd ,4th bit of x)and matching is 57.1%(total 4 values of x matched till now out of 7) and position is 2. similarily the next match is 5th,6th of x i.e [1 1] with 1st,2nd bit of y,so % match will be now 85%(untill now 6 bits of has matched) and position is 1.and the remaining element of x i.e the last 1, is matched with position 1 of y, so percentage matching now is 100%.so i should get it like this. maxP = [28 57 85 100] maxPos = [2 2 1 1] By executing your edited code,i got the maxP(%) but not the positions.

[Jan]

And the next version:

function [P, Pos] = FindSubMatchRecursive(x, y)
nx    = length(x);
nx0   = nx;
P     = zeros(1, nx);
Pos   = zeros(1, nx);
index = 0;
found = 0;
while nx > 0
   [Leni, Posi] = FindSubMatch(x, y);

     % Store results:
     index      = index + 1;
     found      = found + Leni;  % Number of found elements
     P(index)   = 100 * found / nx0;
     Pos(index) = Posi(1);       % The first match only?

     % Prepare data for next iteration:
     x  = x(Leni + 1:nx);        % Crop the found part
     nx = length(x);
  end
  P   = P(1:index);              % Crop unused elements
  Pos = Pos(1:index);
  end

function [Len, Pos] = FindSubMatch(x, y)
Len = 0;
for ix = length(x):-1:1         % Start with complete x
   Pos = strfind(y, x(1:ix));   % Search in y
   if any(Pos)                  % Success
      Len = ix;
      break;
   end
end
end

I've cleaned it up a bit, e.g. removed the many "max" before the names. Now:

x = [1 0 1 0 1 1 1];
y = [1 1 0 0 0 0 0 0 0 ];
[P, Pos] = FindSubMatchRecursive(x, y)
>> P = 28.571       57.143       85.714          100
>> Pos =  2     2     1     1

Kind regards, Jan

[John BG]

the match locations are right

aber

the 3/4 percentages are wrong

have a look to my updated answer just below these lines.

John BG

<mailto:[e-mail] [e-mail]>

[Jan]

@John BG: Why do you think that the percentages are wrong? Compare them with aditya's comment:

 so i should get it like this. maxP = [28 57 85 100] 
 maxPos = [2 2 1 1]

Looks fine.

[aditya sahu]

@jan simon, Thank you once again .it is working correctly. can i ask you one more change in the same question,(i know i am making it longer,so extremely regret). For example,

if x = [1 0 1 0 1 1 1]; y = [1 1 0 0 0 0 0 0 0 ]; the result coming is

P = 28.57          57.14            85.71          100

Pos =  2             2                1             1

Here the percentage p, i.e at first match 28% i.e 2 bits are matching and in the subsequent matchings, the % is increasing cumulatively.Instead of cumulative percentage can we find the individual bit/bits matching percentage up to 100%. i.e i should gets the results as below. if x = [1 0 1 0 1 1 1]; y = [1 1 0 0 0 0 0 0 0 ]; the result should be

P = 28.57      28.57     28.57     14.28   and their positions 

Pos = 2         2         1          1

I am very thankful to you for your kind help.

[Jan]

@aditya: This is a tiny change only:

function [P, Pos] = FindSubMatchRecursive(x, y)
nx    = length(x);
nx0   = nx;
P     = zeros(1, nx);
Pos   = zeros(1, nx);
index = 0;
while nx > 0
   [Leni, Posi] = FindSubMatch(x, y);

     % Store results:
     index      = index + 1;
     P(index)   = 100 * Leni / nx0;  % <-- Leni instead of cummulation
     Pos(index) = Posi(1);       % The first match only?

     % Prepare data for next iteration:
     x  = x(Leni + 1:nx);        % Crop the found part
     nx = length(x);
  end
  P   = P(1:index);              % Crop unused elements
  Pos = Pos(1:index);
  end

And the same FindSubMatch() from above.

[aditya sahu]

Thank you @Jan Simon..it is working

[John BG]

Aditya

x = [1 0 1 0 1 1 1]; y = [1 1 0 0 0 0 0 0 0 ] there is no 14%, there is only one percentage match, the 28%

Jan Simon's answer is still not supplying correct percentages. 28% is correct but 14%? there is no such match because 14% is the percentage of a single bit, for this example.

Regards

John BG

<mailto:[e-mail] [e-mail]>

[Jan]

@John BG: After the explained procedure was subject to changes during the discussion, Aditya, the author of this question, finally asked explicitely for a version, which replies 14% and described the wanted algorithm accordingly. Together with the statement "it is working", we can assume, that the code replies the wanted result.

The found sub-vectors are: [1 0], [1 0], [1 1] and [1]. The last sub-vector is 1/7th of the full vector. Your code replies something else, but this does not mean, that the need of the OP and the corresponding solution is wrong.

[John BG]

detection of [1] or [0] in this context is trivial, is not what Aditya asked for.

I have exchanged emails with Aditya and it was confirmed that the smallest vectors to seek have length 2, not 1.

What is the point any way to write so much code to end up detecting 1s and 0s?

I know my answer works, Aditya knows my answer works. Your answer works catching vectors and percentages but you also produce results that are not needed, like detecting [1] and [0] in a sequence of zeros and ones. Don't worry, it's ok.

Regards

John BG

<mailto:[e-mail] [e-mail]>

[Jan]

@John BG: You wrote

 detection of [1] or [0] in this context is trivial, is not what
 Aditya asked for.

This is wrong. See Aditya's comment above:

 and the remaining element of x i.e the last 1, is matched with
 position 1 of y, [...]

It does not matter what you exchange by email. Here only the contents of this thread matters. According to Aditya's comment, my code works as wanted. Therefore your repeated claims, that my code is wrong, are annyoing. Stop this clutter.

[Emu]

Hello - I treid method #1 but got this error:

Error using horzcat

Dimensions of arrays being concatenated are not consistent.

Error in VocalCodingIRR (line 21)

yy = [whoSpeakCoder, nan(1, nx - 1)]; % Append nans to compare the last values

Is it because there are NaNs in my data? I have attached sample data (withour NaNs)

[Emu]

Ohhhhhh becasue my data is vertical?

[Image Analyst]

@Emu, I don't have your data but if it's a column vector (vertical), try

yy = [whoSpeakCoder; nan(nx - 1, 1)];  % Append nans to compare the last values
% or else you could make yy a row vector instead if you want:
yy = [reshape(whoSpeakCoder, 1, []), nan(1, nx - 1)];  % Append nans to compare the last values

[Emu]

thank you! yes worked :)

Answer 2

[John BG]

Hi Adithya

This is John BG ( <mailto:[e-mail] [e-mail]> )

ok, got it

1.

The percentages are implicit in the mask applied to x.

let be

x2=[1 1 0 0];             % pattern to find
y2=[1 1 1 0 1 1 0 1]      % signal

then

if sought string is [1 1 0 0] then percentage=100%

if sought string is [1 1 0] then percentage=75%

if sought string is [1 0 0] then percentage=75%

if sought string is [1 1] then percentage=50%

if sought string is [1 0] then percentage=50%

if sought string is [0 0] then percentage=50%

it's agreed that no single bits are sought, right?

so, my suggestion is to address the percentage 1st.

the basic processing is:

clear all

x2=[1 1 0 0];             % pattern
y2=[1 1 1 0 1 1 0 1]      % signal     

maskx=[1:3]                % assign percentage here
                           % but only continuous bits, ok?
x=num2str(x2(maskx));
y=num2str(y2);
x(x==' ')=[];y(y==' ')=[];
n=strfind(y,x)

2.

sweeping all percentages

x=[1 1 0 0]
y=randi([0 1],1,20)
N=numel(x)

N=4;

maskx=[1:N]

v={}

for q=1:1:N-1
     for s=1:q
            v=[v maskx([1+s-1:N-q+1+s-1])]
     end
end 

stry

for k=1:1:numel(v)

    Lx=v{k};
    pc=numel(Lx)/numel(x)*100;
    strx=num2str(x(Lx));
    stry=num2str(y);
    strx(strx==' ')=[];stry(stry==' ')=[];
    n=strfind(stry,strx);

    strdisp=['sample ' strx ' with percentage ' num2str(pc)  '%%has '  num2str(numel(nonzeros(n)))  ' match(es). location in y: ' num2str(n) ];
    sprintf([strdisp '\n'])

end

3.

example

stry =
01000101100010101001

   =
  sample 1100 with percentage 100% has 1 match(es). location in y: 3

   =
  sample 110 with percentage 75% has 1 match(es). location in y: 3

   =
  sample 100 with percentage 75% has 2 match(es). location in y: 4  14

   =
  sample 11 with percentage 50% has 2 match(es). location in y: 3  19

   =
  sample 10 with percentage 50% has 6 match(es). location in y: 4   8  10  12  14  17

=
sample 00 with percentage 50% has 4 match(es). location in y: 1   5   6  15

if you find this answer useful would you please be so kind to mark my answer as Accepted Answer?

To any other reader, please if you find this answer

please click on the thumbs-up vote link

thanks in advance

John BG

<mailto:[e-mail] [e-mail]>

regards

John BG

<mailto:[e-mail] [e-mail]>

[aditya sahu]

yes john,but it is not working

[John BG]

it works, check your email.

I wrote the sample ahead of the main string, strfind works the other way around: long string first, sample 2nd.

:)

John BG <mailto:[e-mail] [e-mail]>

[Jan]

The conversion to a string can be omitted:

x2 = [1 1 0 0];
y2 = [1 1 1 0 1 1 0 1];
strfind(y, x(1:3))

[John BG]

Hi again this is John BG ( <mailto:[e-mail] [e-mail]> )

my script applied to

x = [1 0 1 0 1 1 1];
y = [1 1 0 0 0 0 0 0 0 ];

apply my updated script

1  1  0  0  0  0  0  0  0
ans =
sample 1010111 with percentage 100% has 0 match(es). location in y: 

ans =
sample 101011 with percentage 85.7143% has 0 match(es). location in y: 

ans =
sample 010111 with percentage 85.7143% has 0 match(es). location in y: 

ans =
sample 10101 with percentage 71.4286% has 0 match(es). location in y: 

ans =
sample 01011 with percentage 71.4286% has 0 match(es). location in y: 

ans =
sample 10111 with percentage 71.4286% has 0 match(es). location in y: 

ans =
sample 1010 with percentage 57.1429% has 0 match(es). location in y: 

ans =
sample 0101 with percentage 57.1429% has 0 match(es). location in y: 

ans =
sample 1011 with percentage 57.1429% has 0 match(es). location in y: 

ans =
sample 0111 with percentage 57.1429% has 0 match(es). location in y: 

ans =
sample 101 with percentage 42.8571% has 0 match(es). location in y: 

ans =
sample 010 with percentage 42.8571% has 0 match(es). location in y: 

ans =
sample 101 with percentage 42.8571% has 0 match(es). location in y: 

ans =
sample 011 with percentage 42.8571% has 0 match(es). location in y: 

ans =
sample 111 with percentage 42.8571% has 0 match(es). location in y: 

ans =
sample 10 with percentage 28.5714% has 1 match(es). location in y: 2

ans =
sample 01 with percentage 28.5714% has 0 match(es). location in y: 

ans =
sample 10 with percentage 28.5714% has 1 match(es). location in y: 2

ans =
sample 01 with percentage 28.5714% has 0 match(es). location in y: 

ans =
sample 11 with percentage 28.5714% has 1 match(es). location in y: 1

ans =
sample 11 with percentage 28.5714% has 1 match(es). location in y: 1

result:

there are only 2 sub sequences 10 and 11, each with only 1 match, 10 in location 2 and 11 in location 1, and only one match percentage

28.57%

John BG

<mailto:[e-mail] [e-mail]>

Answer 3

[KSSV]

   x=[1 0 1 0] ;
   y=[1 1 1 0]  ;

   idx = x==y ;
   % percentage 
   p = nnz(idx)/numel(x)*100

[aditya sahu]

Thank u dear friend..but as i need, upto which elements only it is matching from first element onwards.. If i take your answer it gives me 75% but the answer should be 25%.

[KSSV]

   x=[1 0 1 0] ; y=[0 1 1 0]  ;

In this case what you want answer?

[aditya sahu]

this should be 50% but another set of answer i want plz check below for my question,suppose x=[1 0 1 1] and y= [0 1 1 0 1 1] ,here the result should be 100% as all the first 4 elements of x are matching serially with y starting from 3rd element..

[aditya sahu]

fin this i got by doing

c=0;
>> for i=1:1:xx
if (x(i)==y(i))
c=c+1;
else
break;
end
end
>> per=(c/n)*100;

[aditya sahu]

but suppose x=[1 0 1 1] and y= [0 1 1 0 1 1] ,here the result should be 100% as all the first 4 elements of x are matching serially with y starting from 3rd element..

[KSSV]

Try that with your code....your code gives 25 as answer if first element matches or exits the loop.

Answer 4

[John BG]

Hi Aditya

This is John BG ( [e-mail] )

the following solves this question, and your other question

https://uk.mathworks.com/matlabcentral/answers/329142-how-to-find-longest-common-substring-in-case-of-binary-arrays

that has been closed, not by me, considered duplicate

clear all;clc;close all;

x=[1 1 1];
y=randi([0 1],1,20)
% y= [ 1 1 1 0 1 1 0 1]

maskx=[1:3]

r=conv(x(maskx),y)
n=find(r==max(r))
if max(r)==sum(x(maskx))                    % only sync if peak
     for k=1:1:numel(n)                                            
          sync_position(k)=n(k)                 % sync_position in correlation
          sync_start(k)=sync_position(k)-numel(maskx)+1;     % sync_start in y
          percentage_match(k)=numel(x(maskx))/numel(x)*100
          sync_start=nonzeros(sort(sync_start))
     end
     else
          disp('no match')
end
y

Please let me know if this answer satisfies your question, script_10.m sent by email

regards

John BG

<mailto:[e-mail] [e-mail]>

[aditya sahu]

Thank you very much, Dear JOHN.

It is a very nice experience to talk with you. and even better feelings sharings things about MatLab with you.

I really appreciate the time and effort you have given to solve my problem. I feel lucky enough myself.

i have tried the attached code(test_10.m) ..It is an improved code compared to previous one. but i feel sorry to inform you that it is also working for some set of values of x array and y array.

For example if i take. the value of, x=[1 1 0 0]; y= [ 1 1 1 0 1 1 0 1]; and maskx=[1:4]; here the code gives, percentage_match = 100%, where as it should be 75% only.bcz the longest substring for x matching with y array is 1 1 0 . i.e 3 digits are matching out of total 4 digits.

Once again from the bottom of my heart i felt really wonderful for your help.

[John BG]

Aditya

you are right, with a for loop some chains go missing.

It's even easier than using a for loop:

clear all
x2=[1 1 0 0];             % pattern
y2=[1 1 1 0 1 1 0 1]      % signal     

% y=randi([0 1],1,20)

maskx=[1:3]                % assign percentage here
                           % but only continuous bits, ok?

x=num2str(x2(maskx));
y=num2str(y2);
x(x==' ')=[];y(y==' ')=[];
n=strfind(x,y)

Please confirm

Regards

John BG

<mailto:[e-mail] [e-mail]>

Answer 5

[Image Analyst]

I'm not sure what the question is because, after reading most of the replies, it seems that aditya's been changing it (specifically the sample data and size of the sample data), but one measure of similarity is the Sørensen–Dice coefficient.

https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient

When it's applied to binary images, I believe it requires the images to be of the same size.