search

kevin-wayne / algs4

Algorithms, 4th edition textbook code and libraries
http://algs4.cs.princeton.edu/code/
GNU General Public License v3.0
7.41k stars 2.68k forks source link

fix for quadratic time caused by substring() in LZW compression #114

Open inflaton opened 2 years ago

inflaton commented 2 years ago

Hi Kevin,

I've made a fix for quadratic time caused by substring() in LZW compression. The key to the fix is to use a new overloaded method TST.longestPrefixOf(String query, int startIndex) in LZW.compress() method. Attached please find 3 reference files:

1) LempelZivWelch.java: improved LZW.java

2) TernarySearchTrie: improved TST.java

3) lzw.sh: shell script proves the correctness and performance improvement. NOTE: existing LZW seems to take forever to compress dickens.txt (~29MB)

Regards, Donghao

LZW_fix.zip