fix for quadratic time caused by substring() in LZW compression
Author: inflatonCreated Feb 6, 2022Updated Feb 6, 2022
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:
LempelZivWelch.java: improved LZW.java
TernarySearchTrie: improved TST.java
lzw.sh: shell script proves the correctness and performance improvement. NOTE: existing LZW seems to take forever to compress dickens.txt (~29MB)
Regards, Donghao
Source: kevin-wayne/algs4