Mailing List Archive: Why the function ac_maketrans defined size of array is 256?

Why the function ac_maketrans defined size of array is 256?

Feb 1, 2012, 7:53 PM

Post #1 of 4 (1835 views)

Hello All,

I debug code of clamav. Aho-Corasick( AC) Algorithms concepts for
matching between virus and signature files. Step for AC is build trie (
keyword tree) for inserting signature from virus database files. I
have question in step build tire before matching with input information.
Why source code in "static int ac_maketrans(struct cli_matcher *root)"
[1] define size of array is 256?.
In addition, Do you using the Depth First Search Algorithm( DFS)
for building trie?

Thanks you,
Chatsiri Rattana

1) http://goo.gl/bIqdx
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net

Re: Why the function ac_maketrans defined size of array is 256? [ In reply to ]

edwin at clamav

Feb 2, 2012, 1:02 AM

Post #2 of 4 (1783 views)

Permalink

On 02/02/2012 05:53 AM, chatsiri wrote:
> Hello All,
>
> I debug code of clamav. Aho-Corasick( AC) Algorithms concepts for matching between virus and signature files. Step for AC is build trie ( keyword tree) for inserting signature from virus
> database files. I have question in step build tire before matching with input information. Why source code in "static int ac_maketrans(struct cli_matcher *root)" [1] define size of array is 256?.

Because the trie matches byte-by-byte, so each node has 256 children, and that includes the root.

> In addition, Do you using the Depth First Search Algorithm( DFS) for building trie?

ac_maketrans uses BFS.

Best regards,
--Edwin
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net

Re: Why the function ac_maketrans defined size of array is 256? [ In reply to ]

chatsiri at chatsiri

Feb 2, 2012, 5:18 PM

Post #3 of 4 (1776 views)

Permalink

----- Original message -----
> On 02/02/2012 05:53 AM, chatsiri wrote:
> > Hello All,
> >
> > IÂ debug code of clamav.Â Aho-Corasick( AC) Algorithms concepts for
> > matching between virus and signature files. Step for AC is build trie
> > ( keyword tree)Â for inserting signature from virus database files. I
> > have question in step build tire before matching with input
> > information. Why source code in "static int ac_maketrans(struct
> > cli_matcher *root)" [1]Â define size of array is 256?.
>
> Because the trie matches byte-by-byte, so each node has 256 children,
> and that includes the root.
What's contain in node? My view, Node contains a signature files for matching with virus in files.right? My plan for optimized algorithm code of string matching with GPU.
>
> > In addition, Do you using the Depth First Search Algorithm( DFS) for
> > building trie?
>
> ac_maketrans uses BFS.
>
> Best regards,
> --Edwin
> _______________________________________________
> http://lurker.clamav.net/list/clamav-devel.html
> Please submit your patches to our Bugzilla: http://bugs.clamav.net

_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net

Re: Why the function ac_maketrans defined size of array is 256? [ In reply to ]

tkojm at clamav

Feb 3, 2012, 7:59 AM

Post #4 of 4 (1780 views)

Permalink

On Fri, 03 Feb 2012 08:18:24 +0700 Chatsiri Ratana
<chatsiri@chatsiri.com> wrote:
> ----- Original message -----
>> On 02/02/2012 05:53 AM, chatsiri wrote:
>>> Hello All,
>>>
>>> I debug code of clamav. Aho-Corasick( AC) Algorithms concepts for
>>> matching between virus and signature files. Step for AC is build trie
>>> ( keyword tree) for inserting signature from virus database files. I
>>> have question in step build tire before matching with input
>>> information. Why source code in "static int ac_maketrans(struct
>>> cli_matcher *root)" [1] define size of array is 256?.
>>
>> Because the trie matches byte-by-byte, so each node has 256 children,
>> and that includes the root.
> What's contain in node? My view, Node contains a signature files for matching with virus in files.right? My plan for optimized algorithm code of string matching with GPU.

I'd suggest you have a look at the source code - all the information is
there.

--
oo ..... Tomasz Kojm <tkojm@clamav.net>
(\/)\......... http://www.ClamAV.net/gpg/tkojm.gpg
\..........._ 0DCA5A08407D5288279DB43454822DC8985A444B
//\ /\ Fri Feb 3 16:57:08 CET 2012
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net