Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize the compaction algorithm for speed #4

Closed
bzaar opened this issue Sep 14, 2015 · 1 comment
Closed

Optimize the compaction algorithm for speed #4

bzaar opened this issue Sep 14, 2015 · 1 comment

Comments

@bzaar
Copy link
Owner

bzaar commented Sep 14, 2015

This will involve two passes. In pass 1, it computes the hashes for all nodes. A hash for a node cosists of the payload has plus the hashes of all children's chars plus the hashes of all child nodes, i.e. it is recursive.
In pass two it uses the hashes to compare and merge the nodes effectively.
Both oasses are bottom up, so each node is visited only twice.

@bzaar
Copy link
Owner Author

bzaar commented Oct 8, 2015

This is done now in version 1.2. Building a 2.5-million word Dawg now takes 5 seconds!

@bzaar bzaar closed this as completed Oct 8, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant