java - 著名的压缩算法(LZ78)的实现缓慢

我写了一个方法，用LZ78算法来逼近一个字符串的Kolmogorov复杂度，除了增加一个表，我只保留一个计数器，我只对压缩的大小感兴趣。
问题是，对于大投入来说，这需要几个小时这是我实施的方式吗？

/**
 * Uses the LZ78 compression algorithm to approximate the Kolmogorov
 * complexity of a String
 *
 * @param s
 * @return the approximate Kolmogorov complexity
 */
public double kComplexity(String s) {

    ArrayList<String> dictionary = new ArrayList<String>();
    StringBuilder w = new StringBuilder();
    double comp = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (dictionary.contains(w.toString() + c)) {
            w.append(c);
        } else {
            comp++;
            dictionary.add(w.toString() + c);
            w = new StringBuilder();
        }
    }
    if (w.length() != 0) {
        comp++;
    }

    return comp;
}

更新：
使用

HashSet<String> dictionary = new HashSet<String>();

而不是

ArrayList<String> dictionary = new ArrayList<String>();

使它更快

最佳答案

我想我可以做得更好（抱歉有点长）：

import java.io.File;
import java.io.FileInputStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class LZ78 {
    /**
     * Uses the LZ78 compression algorithm to approximate the Kolmogorov
     * complexity of a String
     *
     * @param s
     * @return the approximate Kolmogorov complexity
     */
    public static double kComplexity(String s) {
        Set<String> dictionary = new HashSet<String>();
        StringBuilder w = new StringBuilder();
        double comp = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dictionary.contains(w.toString() + c)) {
                w.append(c);
            } else {
                comp++;
                dictionary.add(w.toString() + c);
                w = new StringBuilder();
            }
        }
        if (w.length() != 0) {
            comp++;
        }
        return comp;
    }

    private static boolean equal(Object o1, Object o2) {
        return o1 == o2 || (o1 != null && o1.equals(o2));
    }

    public static final class FList<T> {
        public final FList<T> head;
        public final T tail;
        private final int hashCodeValue;

        public FList(FList<T> head, T tail) {
            this.head = head;
            this.tail = tail;
            int v = head != null ? head.hashCodeValue : 0;
            hashCodeValue = v * 31 + (tail != null ? tail.hashCode() : 0);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof FList<?>) {
                FList<?> that = (FList<?>) obj;
                return equal(this.head, that.head)
                        && equal(this.tail, that.tail);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return hashCodeValue;
        }

        @Override
        public String toString() {
            return head + ", " + tail;
        }
    }

    public static final class FListChar {
        public final FListChar head;
        public final char tail;
        private final int hashCodeValue;

        public FListChar(FListChar head, char tail) {
            this.head = head;
            this.tail = tail;
            int v = head != null ? head.hashCodeValue : 0;
            hashCodeValue = v * 31 + tail;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof FListChar) {
                FListChar that = (FListChar) obj;
                return equal(this.head, that.head) && this.tail == that.tail;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return hashCodeValue;
        }

        @Override
        public String toString() {
            return head + ", " + tail;
        }
    }

    public static double kComplexity2(String s) {
        Map<FList<Character>, FList<Character>> dictionary =
            new HashMap<FList<Character>, FList<Character>>();
        FList<Character> w = null;
        double comp = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            FList<Character> w1 = new FList<Character>(w, c);
            FList<Character> ex = dictionary.get(w1);
            if (ex != null) {
                w = ex;
            } else {
                comp++;
                dictionary.put(w1, w1);
                w = null;
            }
        }
        if (w != null) {
            comp++;
        }
        return comp;
    }

    public static double kComplexity3(String s) {
        Map<FListChar, FListChar> dictionary =
            new HashMap<FListChar, FListChar>(1024);
        FListChar w = null;
        double comp = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            FListChar w1 = new FListChar(w, c);
            FListChar ex = dictionary.get(w1);
            if (ex != null) {
                w = ex;
            } else {
                comp++;
                dictionary.put(w1, w1);
                w = null;
            }
        }
        if (w != null) {
            comp++;
        }
        return comp;
    }

    public static void main(String[] args) throws Exception {
        File f = new File("methods.txt");
        byte[] data = new byte[(int) f.length()];
        FileInputStream fin = new FileInputStream(f);
        int len = fin.read(data);
        fin.close();
        final String test = new String(data, 0, len);

        final int n = 100;
        ExecutorService exec = Executors.newFixedThreadPool(1);
        exec.submit(new Runnable() {
            @Override
            public void run() {
                long t = System.nanoTime();
                double value = 0;
                for (int i = 0; i < n; i++) {
                    value += kComplexity(test);
                }
                System.out.printf("kComplexity: %.3f; Time: %d ms%n",
                        value / n, (System.nanoTime() - t) / 1000000);
            }
        });
        exec.submit(new Runnable() {
            @Override
            public void run() {
                long t = System.nanoTime();
                double value = 0;
                for (int i = 0; i < n; i++) {
                    value += kComplexity2(test);
                }
                System.out.printf("kComplexity2: %.3f; Time: %d ms%n", value
                        / n, (System.nanoTime() - t) / 1000000);
            }
        });
        exec.submit(new Runnable() {
            @Override
            public void run() {
                long t = System.nanoTime();
                double value = 0;
                for (int i = 0; i < n; i++) {
                    value += kComplexity3(test);
                }
                System.out.printf("kComplexity3: %.3f; Time: %d ms%n", value
                        / n, (System.nanoTime() - t) / 1000000);
            }
        });
        exec.shutdown();
    }
}

结果：
K复杂性：41546000；时间：17028毫秒
KFixyTy2：41546000；时间：6555毫秒
K络合物3：41546000；时间：5971毫秒
编辑同行压力：它是如何工作的？
弗兰基，不知道，这似乎是加快速度的好方法。我也得弄清楚，所以我们开始吧。
据观察，原始代码添加了大量字符串，但是，用LinkedList<String>替换它并没有帮助，因为在哈希表中查找集合的压力是恒定的-每次使用hash code（）和equals（）时，都需要遍历整个列表。
但我如何才能确保代码不执行这种不必要的操作呢？答案是：不变性-如果你的类是不变性的，那么至少hashcode是常量，因此，可以预先计算。等式检查也可以快捷方式执行，但在最坏的情况下，它仍将遍历整个集合。
这很好，但接下来如何“修改”一个不可变类。不，你不需要，每次需要不同的内容时都要创建一个新的。但是，当你仔细看字典的内容时，你会发现它包含了多余的信息：[]a，[abc]d，[abc]e，[abcd]f，char。所以为什么不将头部存储为指向先前看到的模式的指针，并为当前字符设置尾部呢？
确切地。使用不变性和反向引用可以节省空间和时间，甚至垃圾收集器也会喜欢你。我的解决方案的一个特点是，在f和haskell中，列表使用head:[tail]签名-head是元素类型，tail是指向下一个集合的指针。在这个问题中，当列表在尾部增长时，则需要相反的结果。
在这里，它只是一些进一步的优化——例如，使用一个具体的cc作为尾部类型，以避免泛型版本的常量字符重新编译。
我的解决方案的一个缺点是，它在计算列表的各个方面时使用递归。对于相对较小的列表，这很好，但较长的列表可能需要增加运行计算的线程堆栈大小。理论上，通过java 7的尾部调用优化，我的代码可以重写为允许jit执行优化的方式（或者已经这样了吗？很难说）。