array inside a array!?

[sathya]

I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;

The array is decleared as

int skip[UCHAR_MAX+1];

unsigned char *pat;


I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time to
explain the above.
BTW, if this a FAQ please refer the question number.

--
"Combinatio n is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan AT gmail DOT com
(AT = @ and DOT = .)

[sathya]

Re: array inside a array!?



sathya wrote:
[color=blue]
> I was going through an Boyer-Moore-Horspool pattern match, I saw a
> array inside a array, like the below,
>
> skip[pat[i] ] = patlen - i - 1;
>
> The array is decleared as
>
> int skip[UCHAR_MAX+1];
>
> unsigned char *pat;
>
> I have seen function call inside the array such as calling strlen()
> inside a array, but the above one is
> strange and new to me as a beginner. Can anybody spend a little time to
> explain the above.
> BTW, if this a FAQ please refer the question number.
>[/color]

Sorry I must be more precise in my question. The bellow properties is
well known with the array:

"In an array, LOGICAL ADJACENCY (B follows A) is modeled by
PHYSICAL ADJACENCY (B occurs just after A in memory.)"

As in the case of the above "array inside a array" I cannot figure out
the possibility of logical and
physical adjacency. And is the above kind of "array inside a array" is
UD in std?


--
"Combinatio n is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan AT gmail DOT com
(AT = @ and DOT = .)

[Chris Dollin]

Re: array inside a array!?

sathya wrote:
[color=blue]
> I was going through an Boyer-Moore-Horspool pattern match, I saw a
> array inside a array, like the below,
>
> skip[pat[i] ] = patlen - i - 1;[/color]

This is NOT "an array inside an array". This is array indexing where
the index expression is itself an array indexing expression.
[color=blue]
> I have seen function call inside the array such as calling strlen()
> inside a array, but the above one is
> strange and new to me as a beginner.[/color]

Why? pat[i] is just as much an expression as f(j) or k+1.

--
Chris "electric hedgehog" Dollin

[Taran]

Re: array inside a array!?

sathya wrote:[color=blue]
> I was going through an Boyer-Moore-Horspool pattern match, I saw a
> array inside a array, like the below,
>
> skip[pat[i] ] = patlen - i - 1;[/color]

I'm not sure about the Boyer-Moore-Horspool pattern match algorithm.

But what the code seems to do is this:

skip[pat[i] ] = patlen - i - 1;

pat[i] gets the ASCII value of the char pointed to by ptr 'pat'.
Index in the array 'skip' to the element (pat[i]), which in this case
is for that particular character, and store whatever 'patlen-i-1' is.
So the ASCII value of that char is actually an index for the skip
array, just like skip[65], 65 ASCII for 'A', would be for char 'A'

pat[i] is actually a number/value which is used as index. The notation
looks like array in array but there's nothing like array in array in C.
Hope that Helps.

Regards,
Taran Tripathi

[Jens.Toerring@physik.fu-berlin.de]

Re: array inside a array!?

sathya <sathya@nomail. com> wrote:[color=blue]
> I was going through an Boyer-Moore-Horspool pattern match, I saw a
> array inside a array, like the below,[/color]
[color=blue]
> skip[pat[i] ] = patlen - i - 1;[/color]
[color=blue]
> The array is decleared as[/color]
[color=blue]
> int skip[UCHAR_MAX+1];[/color]
[color=blue]
> unsigned char *pat;[/color]

[color=blue]
> I have seen function call inside the array such as calling strlen()
> inside a array, but the above one is
> strange and new to me as a beginner. Can anybody spend a little time to
> explain the above.
> BTW, if this a FAQ please refer the question number.[/color]

I don't think that this requires a FAQ entry. In the above line
"pat[i]" simply evaluates to a number that is used as the index
in the 'skip' array. That's not different from using the result
of a function call or computation as the index. It's basically
the same as writing e.g.

idx = pat[ i ];
skip[ idx ] = patlen - i - 1;

just shorter and does not require an extra variable.

Regards, Jens
--
\ Jens Thoms Toerring ___ Jens.Toerring@p hysik.fu-berlin.de
\______________ ____________ http://www.toerring.de

[Flash Gordon]

Re: array inside a array!?

On Tue, 14 Dec 2004 17:25:56 +0530
sathya <sathya@nomail. com> wrote:
[color=blue]
> sathya wrote:
>[color=green]
> > I was going through an Boyer-Moore-Horspool pattern match, I saw
> > a
> > array inside a array, like the below,
> >
> > skip[pat[i] ] = patlen - i - 1;
> >
> > The array is decleared as
> >
> > int skip[UCHAR_MAX+1];
> >
> > unsigned char *pat;
> >
> > I have seen function call inside the array such as calling strlen()
> > inside a array, but the above one is
> > strange and new to me as a beginner. Can anybody spend a little time
> > to explain the above.
> > BTW, if this a FAQ please refer the question number.
> >[/color]
>
> Sorry I must be more precise in my question. The bellow properties
> is well known with the array:
>
> "In an array, LOGICAL ADJACENCY (B follows A) is modeled by
> PHYSICAL ADJACENCY (B occurs just after A in memory.)"
>
> As in the case of the above "array inside a array" I cannot figure
> out the possibility of logical and
> physical adjacency. And is the above kind of "array inside a array"
> is UD in std?[/color]

It's simple. You do *not* have an array inside an array, you are just
looking in one array to find an index in to the other. It is basically
equivalent to:

int skip[UCHAR_MAX+1];
unsigned char *pat;
unsigned char tmp;

tmp = pat[i];
skip[ tmp ] = patlen - i - 1;

<pedantic>
C does not guarantee physical adjacency, only logical adjacency. For
example, on a system with paged memory one location in the array might
be in physical memory whilst the next location, on the other side of a
page boundary, might have been swapped out to disk and not exist in
physical memory at all.
</pedantic>

If you want to look at formal definitions with respect to C you really
need to look at the C standard in my opinion. Google for N869 to find
the publicly available last draft of the C99 standard.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Lawrence Kirby]

Re: array inside a array!?

On Tue, 14 Dec 2004 17:25:56 +0530, sathya wrote:
[color=blue]
>
>
> sathya wrote:
>[color=green]
>> I was going through an Boyer-Moore-Horspool pattern match, I saw a
>> array inside a array, like the below,
>>
>> skip[pat[i] ] = patlen - i - 1;[/color][/color]

This is equivalent to

char tmp;

tmp = pat[i];
skip[tmp] = patlen - i - 1;
[color=blue][color=green]
>> The array is decleared as
>>
>> int skip[UCHAR_MAX+1];
>>
>> unsigned char *pat;
>>
>> I have seen function call inside the array such as calling strlen()
>> inside a array, but the above one is
>> strange and new to me as a beginner. Can anybody spend a little time to
>> explain the above.[/color][/color]

The expression between the [] is just a number used to index the array.
There is no real sense that it is "inside" the array, this idea seems to
be more confusing than helpful. See the equivalent code where pat[i]
isn't "inside" anything.
[color=blue][color=green]
>> BTW, if this a FAQ please refer the question number.[/color][/color]

I doubt it, this is simple expression evaluation.
[color=blue]
> Sorry I must be more precise in my question. The bellow properties is
> well known with the array:
>
> "In an array, LOGICAL ADJACENCY (B follows A) is modeled by
> PHYSICAL ADJACENCY (B occurs just after A in memory.)"[/color]

If you want a discussion of how the algorithm works a newsgroup like
comp.programmin g would be appropriate.
[color=blue]
> As in the case of the above "array inside a array" I cannot figure out
> the possibility of logical and
> physical adjacency. And is the above kind of "array inside a array" is
> UD in std?[/color]

The code is perfectly well defined, assuming the variables involved have
sensible values and it is in a sensible context in the rest of the program.
Again, look at the equivalent code, there's nothing unusual happening here.

Lawrence

[Flash Gordon]

Re: array inside a array!?

On 14 Dec 2004 04:07:40 -0800
"Taran" <taran.tripathi @honeywell.com> wrote:
[color=blue]
> sathya wrote:[color=green]
> > I was going through an Boyer-Moore-Horspool pattern match, I saw a
> > array inside a array, like the below,
> >
> > skip[pat[i] ] = patlen - i - 1;[/color]
>
> I'm not sure about the Boyer-Moore-Horspool pattern match algorithm.
>
> But what the code seems to do is this:
>
> skip[pat[i] ] = patlen - i - 1;
>
> pat[i] gets the ASCII value of the char pointed to by ptr 'pat'.[/color]

Stop right there. The C standard does NOT mandate ASCII, and C has been
implemented on a number of systems that are not ASCII. All pat[1] does
is get the number stored in pat[i] which may have been generated as
something to do with the execution character set, but it might also
just be being used as a byte array.
[color=blue]
> Index in the array 'skip' to the element (pat[i]), which in this case
> is for that particular character,[/color]

What makes you think pat contains character rather than, for example,
bytes of a bitmap graphic?
[color=blue]
> and store whatever 'patlen-i-1' is.
> So the ASCII value of that char is actually an index for the skip
> array, just like skip[65], 65 ASCII for 'A', would be for char 'A'[/color]

Definitely not as mentioned above. Don't assume that all the world is a
PC not that text is the only thing stored in char arrays.
[color=blue]
> pat[i] is actually a number/value which is used as index. The notation
> looks like array in array but there's nothing like array in array in
> C. Hope that Helps.[/color]

That is correct.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Richard Tobin]

Re: array inside a array!?

In article <277392xbur.ln2 @brenda.flash-gordon.me.uk>,
Flash Gordon <spam@flash-gordon.me.uk> wrote:[color=blue]
>What makes you think pat contains character rather than, for example,
>bytes of a bitmap graphic?[/color]

The fact that he's applying the Boyer-Moore algorithm to it?

Of course, you can apply it to any sequence, but it's common to think
of characters in this context.

-- Richard

[Flash Gordon]

Re: array inside a array!?

On 14 Dec 2004 14:27:19 GMT
richard@cogsci. ed.ac.uk (Richard Tobin) wrote:
[color=blue]
> In article <277392xbur.ln2 @brenda.flash-gordon.me.uk>,
> Flash Gordon <spam@flash-gordon.me.uk> wrote:[color=green]
> >What makes you think pat contains character rather than, for example,
> >bytes of a bitmap graphic?[/color]
>
> The fact that he's applying the Boyer-Moore algorithm to it?
>
> Of course, you can apply it to any sequence, but it's common to think
> of characters in this context.[/color]

Well, this is comp.lang.c not an algorithms group and I happen not to
have needed to do pattern matching on text and I know that text
processing is not the only place one does pattern matching. Taran stated
that he did not know the Boyer-Moore-Horspool algorithm, therefor s/he
obviously had no way of knowing that it was likely to be a character,
and all the references to ASCII showed a lack of understanding of what a
char is in C.

So I stand by my question, how did Taran (not you or the OP) know that
pat contained characters?

I add the further question, how does anyone other than the OP know that
the execution character set is ASCII?
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.