Bug fix for ACISM

Several people have used the Aho-Corasick interleaved state-transition matrix code, only to find it didn’t match all strings (!)
The bug was in the machine construction: the “prune backlinks” step in acism_create is (as-is) broken. I commented it out, and voilà it works.
I will update github once I’ve sorted out an SSL cert issue 😛
Thanks for the patience of those who took that code and stumbled on that bug; and special thanks to perfgao@gmail.com, who came up with the tiny example that identified the problem.

FWIW the prune-backlinks code will return; but it will check that the subtrees of targets of backlinks, not just the immediate children, must be a subset of the subtree of the source, in order to prune the link.

Advertisements

About mischasan

I've had the privilege to work in a field where abstract thinking has concrete value. That applies at the macro level --- optimizing actions on terabyte database --- or the micro level --- fast parallel string searches in memory. You can find my documents on production-system radix sort (NOT just for academics!) and some neat little tricks for developers, on my blog https://mischasan.wordpress.com My e-mail sig (since 1976): Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection.
This entry was posted in aho-corasick, algorithm, string search. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s