{"action":"created","issue":{"url":"https://api.github.com/repos/google/brotli/issues/180","labels_url":"https://api.github.com/repos/google/brotli/issues/180/labels{/name}","comments_url":"https://api.github.com/repos/google/brotli/issues/180/comments","events_url":"https://api.github.com/repos/google/brotli/issues/180/events","html_url":"https://github.com/google/brotli/issues/180","id":108509960,"number":180,"title":"Improved matchfinder for high quality compression","user":{"login":"ebiggers","id":2373140,"avatar_url":"https://avatars.githubusercontent.com/u/2373140?v=3","gravatar_id":"","url":"https://api.github.com/users/ebiggers","html_url":"https://github.com/ebiggers","followers_url":"https://api.github.com/users/ebiggers/followers","following_url":"https://api.github.com/users/ebiggers/following{/other_user}","gists_url":"https://api.github.com/users/ebiggers/gists{/gist_id}","starred_url":"https://api.github.com/users/ebiggers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ebiggers/subscriptions","organizations_url":"https://api.github.com/users/ebiggers/orgs","repos_url":"https://api.github.com/users/ebiggers/repos","events_url":"https://api.github.com/users/ebiggers/events{/privacy}","received_events_url":"https://api.github.com/users/ebiggers/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-09-27T03:03:04Z","updated_at":"2016-01-27T09:24:46Z","closed_at":"2016-01-27T09:24:46Z","body":"Brotli currently always finds matches using \"cache tables\": each 4-byte (or 5-byte for lower quality compression) sequence is hashed and placed in a limited-size array of sequences which share the same hash code.  This works great in many cases but is not really well suited for large windows, especially in high compression modes.\r\n\r\nAn alternative which is used in LZMA and some other compressors is to have each hash bucket store a binary tree of sequences which share that hash code.  The tree is sorted in two ways: by sequences in lexicographic order, and as a minheap for distance (the shortest distances are at the top).  Matches can be found by searching for the current sequence in the tree, while re-rooting the tree.\r\n\r\nThere are normally two binary tree nodes allocated for each position in the sliding window, so this does require additional memory (8 times the sliding window size in bytes).\r\n\r\nI implemented this as a proof of concept to see what would happen.\r\n\r\nIt does indeed seem to be better; here are some example results with an uncompressed archive of the silesia corpus (211,941,764 bytes) at quality 11:\r\n\r\n\tCurrent version: compressed to 51,973,280 bytes in 10 mins 10 secs\r\n\tWith binary tree matchfinder: compressed to 51,609,618 bytes in 7 mins 34 secs\r\n\r\nThe code can be found at: repository https://github.com/ebiggers/brotli, branch \"bt_matchfinder\".  Please feel free to do whatever you want with the code.  I've left several TODOS in it.\r\n"},"comment":{"url":"https://api.github.com/repos/google/brotli/issues/comments/175506584","html_url":"https://github.com/google/brotli/issues/180#issuecomment-175506584","issue_url":"https://api.github.com/repos/google/brotli/issues/180","id":175506584,"user":{"login":"szabadka","id":9074039,"avatar_url":"https://avatars.githubusercontent.com/u/9074039?v=3","gravatar_id":"","url":"https://api.github.com/users/szabadka","html_url":"https://github.com/szabadka","followers_url":"https://api.github.com/users/szabadka/followers","following_url":"https://api.github.com/users/szabadka/following{/other_user}","gists_url":"https://api.github.com/users/szabadka/gists{/gist_id}","starred_url":"https://api.github.com/users/szabadka/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/szabadka/subscriptions","organizations_url":"https://api.github.com/users/szabadka/orgs","repos_url":"https://api.github.com/users/szabadka/repos","events_url":"https://api.github.com/users/szabadka/events{/privacy}","received_events_url":"https://api.github.com/users/szabadka/received_events","type":"User","site_admin":false},"created_at":"2016-01-27T09:24:46Z","updated_at":"2016-01-27T09:24:46Z","body":"Thanks for the suggestion, this was implemented in #306, mostly along the lines of your proof-of-concept."}}