Thread Subject: Matching Character Phrases...

Hi

Can anyone help me with figuring out what kind of loop would solve this
problem?

I have a variable 'text' that is a series of uppercase characters. It looks
something like this:

OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO...

The user enters a value, and based on this number, the program should look
for all matching phrases of that length. For example, if they choose '4' the
loop should look through 'text' for all phrases of this size that occur more
than once. It should also record the distance between the matching phrases
in another row of the array (or a seperate array if this is easier). The output
array for the above 'text' should end up looking something like this:

OPAS [14]
OPAS [20]
GLBO [15]
GLBO [23]
...etc...

Using strmatch doesnt seem to help me for this...

I have a loop that works, but it is very time consuming to run. I only really
need to use the first '30' results from the output array so it would be ideal if
the loop could break when the output array is of length 30 (if it gets up to 30,
sometimes there will be less), otherwise it should end when there are no
more matches found.

I recently learned a little about regexp, and you might try
something like the following. You could use the
outputs 'num_times' and 'distances' to format the output
exactly how you want it. No loop required.

J

A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
user_str = 'OPAS';
[s] = regexp(A,user_str,'start');
num_times = size(s,2);
distances = diff(s);

"Jack Branning" <jbr.nospam@nospam.com> wrote in message
<fpkn42$3cg$1@fred.mathworks.com>...
> Hi
>
> Can anyone help me with figuring out what kind of loop
would solve this
> problem?
>
> I have a variable 'text' that is a series of uppercase
characters. It looks
> something like this:
>
> OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO...
>
> The user enters a value, and based on this number, the
program should look
> for all matching phrases of that length. For example, if
they choose '4' the
> loop should look through 'text' for all phrases of this
size that occur more
> than once. It should also record the distance between
the matching phrases
> in another row of the array (or a seperate array if this
is easier). The output
> array for the above 'text' should end up looking
something like this:
>
> OPAS [14]
> OPAS [20]
> GLBO [15]
> GLBO [23]
> ...etc...
>
> Using strmatch doesnt seem to help me for this...
>
> I have a loop that works, but it is very time consuming
to run. I only really
> need to use the first '30' results from the output array
so it would be ideal if
> the loop could break when the output array is of length
30 (if it gets up to 30,
> sometimes there will be less), otherwise it should end
when there are no
> more matches found.

"jay vaughan" <jvaughan5.nospam@gmail.com> wrote in message
<fpkp21$rvm$1@fred.mathworks.com>...
> I recently learned a little about regexp, and you might try
> something like the following. You could use the
> outputs 'num_times' and 'distances' to format the output
> exactly how you want it. No loop required.
>
> J
>
> A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
> user_str = 'OPAS';
> [s] = regexp(A,user_str,'start');
> num_times = size(s,2);
> distances = diff(s);
>


Thanks for your help, that's definitely along the right lines, although I need
the program to be finding the phrases itself. So, for example, it firstly tries to
find all 'OPAS' matches in 'text' (A, in your example), then moves on to 'PASK'
matches, then 'ASKS' etc, until it has found 30 matches, or it reaches the end
of the 'text'.

Hmm, is the length of the repeated strings always known? In
your case it seemed to be 4.

J

"Jack Branning" <jbr.nospam@nospam.com> wrote in message
<fpktm4$501$1@fred.mathworks.com>...
> "jay vaughan" <jvaughan5.nospam@gmail.com> wrote in
message
> <fpkp21$rvm$1@fred.mathworks.com>...
> > I recently learned a little about regexp, and you might
try
> > something like the following. You could use the
> > outputs 'num_times' and 'distances' to format the
output
> > exactly how you want it. No loop required.
> >
> > J
> >
> > A
= 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
> > user_str = 'OPAS';
> > [s] = regexp(A,user_str,'start');
> > num_times = size(s,2);
> > distances = diff(s);
> >
>
>
> Thanks for your help, that's definitely along the right
lines, although I need
> the program to be finding the phrases itself. So, for
example, it firstly tries to
> find all 'OPAS' matches in 'text' (A, in your example),
then moves on to 'PASK'
> matches, then 'ASKS' etc, until it has found 30 matches,
or it reaches the end
> of the 'text'.
>
>
>

Here is a brute force solution. It runs in 10 seconds or so
on my computer witn num = 4, but it will scale badly for
larger numbers.

A = 'OPASKSBBBBGLBOJASLOPASNKMGLBOSDLBBBBAS...
JSFLOPASHHASKSMLGLBOAAABFDFAAAB';

v = ['ABCDEFGHIJKLMNOPQRSTUVWXYZ'];
num = 4; % user specifies this
SS = PermsRep(v,num); % generates all permutations

% download subroutine PermsRep from URL below
% http://www.mathworks.com/support/solutions...
% /files/s36265/PermsRep.m

O = struct([]);
ctr = 1;
for k = 1:size(SS,1)
    [s]=regexp(A,SS(k,:),'start');
    if max(size(s))>1
        O(ctr).string = SS(k,:);
        O(ctr).positions = s;
        O(ctr).distances = diff(s);
        ctr = ctr + 1;
    end
end

Hope it helps.

J

"Jack Branning" <jbr.nospam@nospam.com> wrote in message
<fpkn42$3cg$1@fred.mathworks.com>...
> Hi
>
> Can anyone help me with figuring out what kind of loop
would solve this
> problem?
>
> I have a variable 'text' that is a series of uppercase
characters. It looks
> something like this:
>
> OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO...
>
> The user enters a value, and based on this number, the
program should look
> for all matching phrases of that length. For example, if
they choose '4' the
> loop should look through 'text' for all phrases of this
size that occur more
> than once. It should also record the distance between
the matching phrases
> in another row of the array (or a seperate array if this
is easier). The output
> array for the above 'text' should end up looking
something like this:
>
> OPAS [14]
> OPAS [20]
> GLBO [15]
> GLBO [23]
> ...etc...
>
> Using strmatch doesnt seem to help me for this...
>
> I have a loop that works, but it is very time consuming
to run. I only really
> need to use the first '30' results from the output array
so it would be ideal if
> the loop could break when the output array is of length
30 (if it gets up to 30,
> sometimes there will be less), otherwise it should end
when there are no
> more matches found.

Driving home, I thought about it again and realized that my
brute force suggestion only wins when length(A)>(26^num),
which is probably not usually true!! Then you could try the
following instead.

-J


A = 'XXXXDEFGHXXXXIJKLYYYYMNOPQXXXXRSTUVWXYXXXXZYYYY';
num = 4;

O = struct([]);
ctr = 1;
for k = 1:(length(A)-num)
   [m s]=regexp(A(k:end),A(k:(k+num-1)),'match','start');
   occurs_again = length(s)>1;
   occurred_already =...
      ~isempty(regexp(A(1:(k+num-2)),A(k:(k+num-1))));
   if and(occurs_again,~occurred_already)
      O(ctr).string = m{1};
      O(ctr).positions = s;
      O(ctr).distance = diff(s);
      ctr = ctr+1;
   end
end

On 2008-02-21 15:32:02 -0500, "Jack Branning" <jbr.nospam@nospam.com> said:

> Hi
>
> Can anyone help me with figuring out what kind of loop would solve this
> problem?
>
> I have a variable 'text' that is a series of uppercase characters. It looks
> something like this:
>
> OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO...
>
> The user enters a value, and based on this number, the program should look
> for all matching phrases of that length. For example, if they choose '4' the
> loop should look through 'text' for all phrases of this size that occur more
> than once. It should also record the distance between the matching phrases
> in another row of the array (or a seperate array if this is easier). The output
> array for the above 'text' should end up looking something like this:
>
> OPAS [14]
> OPAS [20]
> GLBO [15]
> GLBO [23]
> ...etc...
>
> Using strmatch doesnt seem to help me for this...
>
> I have a loop that works, but it is very time consuming to run. I only really
> need to use the first '30' results from the output array so it would be
> ideal if
> the loop could break when the output array is of length 30 (if it gets
> up to 30,
> sometimes there will be less), otherwise it should end when there are no
> more matches found.

All of the current suggestions search through the string multiple
times. I think you should run through it once and collect information
along the way. If your text is always letters (no spaces or numbers),
you can use the words as dynamic field names to quickly "hash" the
various words. For example, the following code will create (1) a
structure of locations of each "word" and (2) a structure of distances
between multiple occurences of the words. However, this code could
become slow if you have *lots* of occurences of a particular word,
because it keeps "growing" arrays [in the line that uses (end+1)].
Really, this problem would be much easier in a language that had more
flexible hashes/dictionaries and supported linked lists.

A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
num = 4;
locationStruct = struct;
for k=1:(numel(A)-num)
    word = A(k:(k+num-1));
    if isfield(locationStruct, word)
        locationStruct.(word)(end+1) = k;
    else
        locationStruct.(word) = k;
    end
end
distanceStruct = structfun(@diff, locationStruct, 'UniformOutput', 0);

On 2008-02-22 09:52:44 -0500, Arthur G <gorramfreak+news@gmail.com> said:
>
> All of the current suggestions search through the string multiple
> times. I think you should run through it once and collect information
> along the way. If your text is always letters (no spaces or numbers),
> you can use the words as dynamic field names to quickly "hash" the
> various words. For example, the following code will create (1) a
> structure of locations of each "word" and (2) a structure of distances
> between multiple occurences of the words. However, this code could
> become slow if you have *lots* of occurences of a particular word,
> because it keeps "growing" arrays [in the line that uses (end+1)].
> Really, this problem would be much easier in a language that had more
> flexible hashes/dictionaries and supported linked lists.
>
> A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
> num = 4;
> locationStruct = struct;
> for k=1:(numel(A)-num)
> word = A(k:(k+num-1));
> if isfield(locationStruct, word)
> locationStruct.(word)(end+1) = k;
> else
> locationStruct.(word) = k;
> end
> end
> distanceStruct = structfun(@diff, locationStruct, 'UniformOutput', 0);

I just wanted to point out a few more limitations to this approach:
(1) It's limited to 63-character word length, because that's
namelengthmax in MATLAB
(2) It could also become memory intensive if the text is very long with
very few word repeats, due to lots of fields in the structure. I don't
know if there's a limit to the number of fields in a MATLAB structure.

But in the examples you've provided, this certainly isn't a problem...

Hi, thank you so much for your help, I think this solution is very close to what
I need.

However, I do have a couple of questions:
How can I build an array of just the 'words' that are repeated in A?
and how can I build another array that shows the distances between
matching pairs?

This solution is 1000% quicker than my solution, so I am very interested in
hearing how I can put it into practise!

Thanks again!
>
> All of the current suggestions search through the string multiple
> times. I think you should run through it once and collect information
> along the way. If your text is always letters (no spaces or numbers),
> you can use the words as dynamic field names to quickly "hash" the
> various words. For example, the following code will create (1) a
> structure of locations of each "word" and (2) a structure of distances
> between multiple occurences of the words. However, this code could
> become slow if you have *lots* of occurences of a particular word,
> because it keeps "growing" arrays [in the line that uses (end+1)].
> Really, this problem would be much easier in a language that had more
> flexible hashes/dictionaries and supported linked lists.
>
> A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
> num = 4;
> locationStruct = struct;
> for k=1:(numel(A)-num)
> word = A(k:(k+num-1));
> if isfield(locationStruct, word)
> locationStruct.(word)(end+1) = k;
> else
> locationStruct.(word) = k;
> end
> end
> distanceStruct = structfun(@diff, locationStruct, 'UniformOutput', 0);
>
>

On 2008-02-22 10:16:34 -0500, "Jack Branning" <jbr.nospam@nospam.com> said:
>
>>
>> All of the current suggestions search through the string multiple
>> times. I think you should run through it once and collect information
>> along the way. If your text is always letters (no spaces or numbers),
>> you can use the words as dynamic field names to quickly "hash" the
>> various words. For example, the following code will create (1) a
>> structure of locations of each "word" and (2) a structure of distances
>> between multiple occurences of the words. However, this code could
>> become slow if you have *lots* of occurences of a particular word,
>> because it keeps "growing" arrays [in the line that uses (end+1)].
>> Really, this problem would be much easier in a language that had more
>> flexible hashes/dictionaries and supported linked lists.
>>
>> A = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
>> num = 4;
>> locationStruct = struct;
>> for k=1:(numel(A)-num)
>> word = A(k:(k+num-1));
>> if isfield(locationStruct, word)
>> locationStruct.(word)(end+1) = k;
>> else
>> locationStruct.(word) = k;
>> end
>> end
>> distanceStruct = structfun(@diff, locationStruct, 'UniformOutput', 0);

> Hi, thank you so much for your help, I think this solution is very
> close to what
> I need.
>
> However, I do have a couple of questions:
> How can I build an array of just the 'words' that are repeated in A?
> and how can I build another array that shows the distances between
> matching pairs?
>
> This solution is 1000% quicker than my solution, so I am very interested in
> hearing how I can put it into practise!
>
> Thanks again!

Once you have locationStruct and distanceStruct, there are lots of ways to
create the arrays. What's most efficient depends on the number of "single"
words, but here's what I think is a relatively robust solution:

numWords = sum( ~structfun(@numel, locationStruct) );
wordList = cell(numWords, 1);
distanceList = zeros(numWords, 1);
count = 0;
fn = fieldnames(distanceStruct);
for i=1:numel(fn)
    word = fn{i};
    for distance=distanceStruct.(word)
        count = count + 1;
        wordList{count} = word;
        distanceList(count) = distance;
    end
end

> Once you have locationStruct and distanceStruct, there are lots of ways to
> create the arrays. What's most efficient depends on the number of "single"
> words, but here's what I think is a relatively robust solution:
>
> numWords = sum( ~structfun(@numel, locationStruct) );
> wordList = cell(numWords, 1);
> distanceList = zeros(numWords, 1);
> count = 0;
> fn = fieldnames(distanceStruct);
> for i=1:numel(fn)
> word = fn{i};
> for distance=distanceStruct.(word)
> count = count + 1;
> wordList{count} = word;
> distanceList(count) = distance;
> end
> end
>

Thanks again!!

I have tested this code, and it seems 'wordlist' contains every possible word.
Is there a way to just show the words that match in an array?

Also, distanceList seems to be full of the mostly same number... For the
ciphertext I tested it on, it shows as mostly '480'. Is there a way of this array
showing the distances between matches? (i.e. 45, 95, 105, 25 etc... (or
whatever the values may be)).

We are so nearly there though, thanks so much for all the effort!!

"Jack Branning":
<SNIP looking for n-char patterns in a boring string

one of the many solutions

% the data
% ...assuming char range ]A-z[
% ...otherwise: adjust appropriately
     z='OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
     n=4;
% the engine
     s=[];
     zz=z;
while ~isempty(zz) && length(zz) >= n
     p=zz(1:n);
if ~isfield(s,p) % this makes it very(!) fast
     ix=strfind(zz,p);
     s.(p)=numel(ix);
end
     zz=zz(2:end);
end
% the result
     c=struct2cell(s);
     [fn,fx]=sort(fieldnames(s));
     s
     r=[fn c(fx)]

us

On 2008-02-22 11:16:36 -0500, "Jack Branning" <jbr.nospam@nospam.com> said:

>> Once you have locationStruct and distanceStruct, there are lots of ways to
>> create the arrays. What's most efficient depends on the number of "single"
>> words, but here's what I think is a relatively robust solution:
>>
>> numWords = sum( ~structfun(@numel, locationStruct) );
>> wordList = cell(numWords, 1);
>> distanceList = zeros(numWords, 1);
>> count = 0;
>> fn = fieldnames(distanceStruct);
>> for i=1:numel(fn)
>> word = fn{i};
>> for distance=distanceStruct.(word)
>> count = count + 1;
>> wordList{count} = word;
>> distanceList(count) = distance;
>> end
>> end
>>
>
> Thanks again!!
>
> I have tested this code, and it seems 'wordlist' contains every possible word.
> Is there a way to just show the words that match in an array?
>
> Also, distanceList seems to be full of the mostly same number... For the
> ciphertext I tested it on, it shows as mostly '480'. Is there a way of
> this array
> showing the distances between matches? (i.e. 45, 95, 105, 25 etc... (or
> whatever the values may be)).
>
> We are so nearly there though, thanks so much for all the effort!!

The code works as expected on all text I've tested...

Here's what it does: step through every field in distanceStruct and
record every nonzero distance and the associated word. For efficiency,
I first count the number of items and "pre-allocate" the cell and array.

You could also check locationStruct and see if the same words really
are occurring 480 characters apart...

This seems like a good time to use dynamic regular expressions.

Try this:

>> text = 'OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO';
>> len = num2str(4);
>> s = '';
>> regexp(text,
['(.{',len,'})((?>.*?\1))(?@s=sprintf(''%s%s[%d]\\n'',s,$1,length($2));)(?!)']);
>> s
s =
OPAS[14]
ASKS[38]
GLBO[15]
LOPA[20]
OPAS[20]
GLBO[25]

What did that do?

 (.{',len,'}) - match exactly len characters, and capture it
in token #1

 ((?>.*?\1)) - match as few characters as possible, followed
by an exact match of token #1. Make this group atomic (so
it won't continue to look for another match of token #1),
and capture this second portion in token #2

 (?@s=sprintf(''%s%s[%d]\\n'',s,$1,length($2));) - evaluate
this code in the MATLAB workspace. This will append the
token #1 followed by the length of token #2 to the workspace
variable s, which was initialized to ''

 (?!) - force the regular expression to fail. The purpose
of the expression is to do the evaluation, and then to keep
looking for more matches, so regexp will not actually return
any matches.

Alternately, you can collect the matches in a cell array in
the workspace, which may be easier to work with:

>> c={};
>> regexp(text,
['(.{',len,'})((?>.*?\1))(?@c{end+1}=sprintf(''%s[%d]\\n'',$1,length($2));)(?!)']);
>> c{:}
ans =
OPAS[14]

ans =
ASKS[38]

ans =
GLBO[15]

ans =
LOPA[20]

ans =
OPAS[20]

ans =
GLBO[25]

Or:

>> c={};
>> regexp(text, ['(.{',len,'})((?>.*?\1))(?@c{end+1}={$1,
length($2)};)(?!)']);
>> c{:}
ans =
    'OPAS' [14]
ans =
    'ASKS' [38]
ans =
    'GLBO' [15]
ans =
    'LOPA' [20]
ans =
    'OPAS' [20]
ans =
    'GLBO' [25]

Hope that helps,

-=>J


"Jack Branning" <jbr.nospam@nospam.com> wrote in message
<fpkn42$3cg$1@fred.mathworks.com>...
> Hi
>
> Can anyone help me with figuring out what kind of loop
would solve this
> problem?
>
> I have a variable 'text' that is a series of uppercase
characters. It looks
> something like this:
>
> OPASKSGLBOJASLOPASNKMGLBOSDLASJSFLOPASHHASKSMLGLBO...
>
> The user enters a value, and based on this number, the
program should look
> for all matching phrases of that length. For example, if
they choose '4' the
> loop should look through 'text' for all phrases of this
size that occur more
> than once. It should also record the distance between the
matching phrases
> in another row of the array (or a seperate array if this
is easier). The output
> array for the above 'text' should end up looking something
like this:
>
> OPAS [14]
> OPAS [20]
> GLBO [15]
> GLBO [23]
> ...etc...
>
> Using strmatch doesnt seem to help me for this...
>
> I have a loop that works, but it is very time consuming to
run. I only really
> need to use the first '30' results from the output array
so it would be ideal if
> the loop could break when the output array is of length 30
(if it gets up to 30,
> sometimes there will be less), otherwise it should end
when there are no
> more matches found.

On Feb 22, 8:46=A0pm, "Jason Breslau" <tendiamo...@mathworks.com> wrote:
> This seems like a good time to use dynamic regular expressions.
<snip>

Interesting... But the regexp engine will still end up scanning
(albeit smaller and smaller portions of) the string repeatedly. As
long as you have the ability to hash (at most) numel(text) "words",
then you only have to scan the string once...

True. Subsequently, your solution is significantly more
efficient than mine.

Thank you both your your responses to this problem!

Both solutions are much MUCH quicker than my brute force solution, so I will
definitely work with what you have given!

Thanks again!!