Rather than clog the forum with files, I have posted a later version of the BM algo with 2 variants at the following URL.
http://www.pbq.com.au/home/hutch/bm.htm
I have slightly modified the verson that have posted before to remove one jump from it, the two variants are based on using only one of the shift types, one uses the GOOD SUFFIX shift, the other uses the BAD CHARACTER shift.
One works well on the AMD I have to test on, shorter pipeline and lower penalty for a stall, the other is faster on the Intel, longer pipeline but better branch prediction. The basic BM algo is more flexible across different processors.
Regards,
hutch@pbq.com.au
http://www.pbq.com.au/home/hutch/bm.htm
I have slightly modified the verson that have posted before to remove one jump from it, the two variants are based on using only one of the shift types, one uses the GOOD SUFFIX shift, the other uses the BAD CHARACTER shift.
One works well on the AMD I have to test on, shorter pipeline and lower penalty for a stall, the other is faster on the Intel, longer pipeline but better branch prediction. The basic BM algo is more flexible across different processors.
Regards,
hutch@pbq.com.au
I have just modified the html page for the BM algorithms so that it includes a tutorial on the basic design of Boyer Moore algorithms.
When I was developing the original version, I found very little useful information posted on the net that explained the basic workings of this design so I hope that this tute will help to fill that gap.
Regards,
hutch@pbq.com.au :alright:
When I was developing the original version, I found very little useful information posted on the net that explained the basic workings of this design so I hope that this tute will help to fill that gap.
Regards,
hutch@pbq.com.au :alright:
Very nice Hutch
i like those simple HTML tutorials with ASM source code ;),
esp where the algorithm is explained in detailed plain english
i wish i will start to write some...one of those days ...
Thx a lot man
i like those simple HTML tutorials with ASM source code ;),
esp where the algorithm is explained in detailed plain english
i wish i will start to write some...one of those days ...
Thx a lot man
Bogdan,
Your welcome, when you get enough time, some of your graphics and animation knowhow would be most appreciated.
Regards,
hutch@pbq.com.au
Your welcome, when you get enough time, some of your graphics and animation knowhow would be most appreciated.
Regards,
hutch@pbq.com.au
Hutch,
I had some time to look these over & read-up on the theory. Nice & clean implementation :alright:
A question: Just curious... Did you look into the "extended bad character shift?"
Quick explanation: That is, where you shift upon finding a bad char by moving the pattern so that next occurance of the bad char to the left of the current pattern position will be aligned? Some of the lit I read claims that it works better for small char sets (like ACGT for DNA etc.).
Just curious as to how you'd have tried to do it that's all.
rafe
I had some time to look these over & read-up on the theory. Nice & clean implementation :alright:
A question: Just curious... Did you look into the "extended bad character shift?"
Quick explanation: That is, where you shift upon finding a bad char by moving the pattern so that next occurance of the bad char to the left of the current pattern position will be aligned? Some of the lit I read claims that it works better for small char sets (like ACGT for DNA etc.).
Just curious as to how you'd have tried to do it that's all.
rafe
rafe,
I am not sure how that works, the standard bad character shift just moves the whole pattern past the last bad character and starts reverse comparing again.
There is a variation where the bad character shift is compared to the good character shift in the table for the compared character and the larger of the two is taken but I found in practice that it was slower code in every case so i did not use it.
Regards,
hutch@movsd.com
I am not sure how that works, the standard bad character shift just moves the whole pattern past the last bad character and starts reverse comparing again.
There is a variation where the bad character shift is compared to the good character shift in the table for the compared character and the larger of the two is taken but I found in practice that it was slower code in every case so i did not use it.
Regards,
hutch@movsd.com