压缩Java字符串（URL）

Question

我有很多URL要处理。我将大约20'000'000个URL存储在一个哈希集合中，这会导致一些内存问题。

我尝试创建了一个压缩字符串类：

import java.io.*;//file writer
import java.util.*;
import java.util.zip.*;

class CompressedString2 implements Serializable{
    private int originalSize;
    private byte[] cstring;



    public CompressedString2 (){
        compress("");
    }


    public CompressedString2 (String string){
        compress(string);
    }


    public void compress(String str){
        try {
            byte[] bytes = str.getBytes("UTF-8");
            originalSize = bytes.length;

            ByteArrayOutputStream deflatedBytes = new ByteArrayOutputStream();
            DeflaterOutputStream dos = new DeflaterOutputStream(deflatedBytes,new Deflater(Deflater.DEFAULT_COMPRESSION));
            dos.write(bytes);
            dos.finish();
            cstring=deflatedBytes.toByteArray();
        }catch(Exception e){e.printStackTrace();}

    }


    public String decompress() throws Exception{
        String result="";
        try{
            ByteArrayOutputStream deflatedBytes=new ByteArrayOutputStream();
            deflatedBytes.write(cstring);
            deflatedBytes.close();


            InflaterInputStream iis = new InflaterInputStream(new ByteArrayInputStream(deflatedBytes.toByteArray()));
            byte[] inflatedBytes = new byte[originalSize];
            iis.read(inflatedBytes);
            result= new String(inflatedBytes, "UTF-8");
        }catch(Exception e){e.printStackTrace();}
        return result;
    }
}

但事实上，当我像这样存储它们时：

HashSet<String> urlStr=new HashSet<String>();
HashSet<CompressedString> urlComp=new HashSet<CompressedString>();


        String filePath=new String();

            filePath=args[0];

        int num=0;

        try{
            BufferedReader br = new BufferedReader(new FileReader(filePath));

            String line = br.readLine();
            while (line != null) {

                num++;
                urlStr.add(line);
                urlComp.add(new CompressedString(line));

            line = br.readLine();
            }
        } catch(Exception e){
        System.out.println("fehler..:");
            e.printStackTrace();
        }

ObjectOutputStream oos1 = new ObjectOutputStream(new FileOutputStream("testDeflator_rawurls.obj"));
oos1.writeObject(urlStr);
ObjectOutputStream oos4 = new ObjectOutputStream(new FileOutputStream("testDeflator_compressed2.obj"));
oos4.writeObject(urlComp);

“压缩”后的URL甚至更大...

有人有成功压缩URL的想法吗？

- Moritz B.

---

之前你只是将URL存储为字符串，现在你将会把它们存储为“CompressedString”对象。当然，虽然URL本身被压缩了，但你的对象将占用比字符串更多的内存空间。 - jzworkman

@jzworkman -- 我不同意；CompressedString 包含一个数组和一个 int，实际上比 String 的成员更少。 - Ernest Friedman-Hill

Answer 1

如果它们在一个集合中，那么你只能进行添加/删除/查找操作。你也可以在“字符森林”上执行这些操作，它可能是一种更紧凑的表示方式。我考虑使用节点树，每个节点都包含一个字符，并彼此链接。森林的根包含“h”，“f”和其他一些节点。在“h”节点下面会有一个“t”节点，然后再下面是另一个“t”节点，最后是一个“p”节点等等。"f"节点将有"t"和"i"子节点。最终树会分支，但在根附近可能会有很多共享。然后你只需要遍历整个森林，就可以确定URL是否在其中。

我认为每个节点需要一个布尔成员来指示集合中是否有一个URL在此处终止，一个成员来保存字符，并且一个链接数组用于连接其他节点。

- Ernest Friedman-Hill

---

这取决于实现方式，可能会很快（期望的时间复杂度为O(n)，其中n是URL的长度）。 - Adrian

我可能会尝试实现类似这样的东西，只是为了好玩！ - Spencer Kormos

根据URL，"字符串森林"可能会更好地工作（就查找时间和存储开销而言）。以"http://"和"ftp://"等根节点为起点，每个"/"都会分裂出子节点。 - ArjunShankar

Answer 2

你有没有考虑过另一种方法？在哈希集中存储2000万个字符串是很多的。你能否将它们存储在数据库中并从那里进行处理？

- user1316820

Answer 3

一般而言，为了使压缩效果更好，字符串的长度应该越长越好，因为压缩是基于字符串中的模式进行的。

- Adrian

Answer 4

短字符串可能无法压缩到比未压缩的字符串更小。您尝试过-XX:+UseCompressedString吗？对于某些Java 6版本，默认情况下已启用该选项。

- Peter Lawrey

Answer 5

您可以一次压缩n个URL，其中n可能是10到100个。这将为压缩器提供重复字符串和偏斜字符概率分布的工作内容。缺点是每次访问都需要解压10到100个URL。因此，在实现后，可以变化n以在内存使用和速度之间进行权衡，并选择您喜欢的折衷方案。

- Mark Adler

Answer 6

如果您的许多URL具有共同的基础，例如http://www.mysite.com/，那么您应该考虑使用Ropes（项目页面），以便每个字符串的第一部分只表示一次。

另请参见此维基百科页面。

- daveb

Answer 7

您可以使用TinyURL来缩短链接并进行存储。
您可以在这里找到Java实用程序类来生成Tiny URL。

- rot

Answer 8

关于将100个链接连接在一起（用特殊字符分隔）并尝试将它们压缩成一个CompressedString，您怎么看？ 压缩可能需要最小长度以提高效率。 CompressedString类可以将100个字符串还原为一个集合。

- Houcem Berrayana

Answer 9

压缩 URL 并不一定会节省内存，因为包装类的额外开销。另一种方法是使用前缀映射来缩短 URL。但是，如果使用包装类，则必须实现 hashCode 和 equals 方法。如果没有它们，则哈希集将无法按预期工作（允许重复项）。对于 CompressedString2，可以这样实现：

@Override
public int hashCode() {
    return Arrays.hashCode(cstring);
}

public boolean equals(Object other){
    if(other instanceof CompressedString){
        return Arrays.equals(cstring, ((CompressedString) other).cstring);
    }
    return false;
}

另一个大幅减少内存占用的方法是使用类似于Trove的THashSet。既然您知道URL的数量，还可以增加负载系数并设置哈希集的初始大小，这将节省大量重新哈希的时间，并允许您更有效地使用分配的空间。

- Robin Keskisarkka