3

我有很多网址要处理。我将其中大约 20'000'000 个存储在哈希集中。这会造成一些记忆问题。

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

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);

“压缩”的网址更大......

有人知道如何成功压缩网址吗？

4

9 回答 9

5

好吧，如果它们在一个集合中，那么您所能做的就是添加/删除/查找。您也可以在“字符森林”上执行这些操作，它可能是更紧凑的表示。我在想一棵节点树，每个节点都有一个角色，彼此链接。森林的根将包含“h”、“f”等。在“h”节点下将是一个“t”节点，在该节点下是另一个“t”，在该节点下是一个“p”，等等。“f”节点将有“t”和“i”子节点。最终树会分叉，但在根部附近可能会有很多共享。然后，您只需在森林中走一走，看看那里是否有 URL。

我想一个节点需要一个布尔成员来指示集合中的一个 URL 在那里终止，一个保存字符的成员，以及指向其他节点的链接数组。

于 2012-04-13T13:16:50.250 回答
1

您是否考虑过不同的方法？哈希集中的 2000 万个字符串非常多。您可以将它们存储在数据库中并从那里进行处理吗？

于 2012-04-13T14:12:24.723 回答
0

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

另请参阅此维基百科页面

于 2012-04-13T13:38:55.353 回答
0

短字符串可能不会压缩到小于未压缩的字符串。您是否尝试过-XX:+UseCompressedString某些 Java 6 版本默认打开的选项。

于 2012-04-13T13:28:01.343 回答
0

只是，一般来说，为了使压缩工作良好，字符串必须更长，因为它基于所述字符串中的模式工作。

于 2012-04-13T13:20:09.577 回答
0

您可以使用 tinyurl 减少长度然后存储它。您可以在此处
找到指向小 URL 的 java 实用程序类

于 2012-04-13T13:52:29.890 回答
0

您可以一次压缩 n 个 URL，其中 n 可能是 10 到 100。这将使压缩器以重复字符串和倾斜字符概率分布的方式工作。缺点是每次访问都必须解压缩 10 到 100 个 URL。因此，实现这一点后，改变 n 以在内存使用和速度之间进行交易，并选择你喜欢的折衷方案。

于 2012-04-13T13:37:06.770 回答
0

例如，将 100 个链接连接在一起（由特殊字符分隔）并尝试将它们压缩成一个 CompressedString 怎么样？压缩可能需要最小长度才能有效。CompressedString 类可以恢复集合中的 100 个字符串。

于 2012-04-13T14:19:43.973 回答
0

由于包装类的额外开销，压缩 URL 不一定会为您节省任何内存。另一种方法是使用前缀映射来缩短 URL。但是，如果使用包装类，则必须实现hashCodeandequals方法。没有它们，哈希集将无法按预期工作（允许重复）。对于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 的大致数量，您还可以增加负载因子并设置散列集的初始大小，这将为您节省大量重新散列并让您更有效地使用分配的空间。

于 2018-07-17T19:10:35.937 回答