5

更新：我用一个很棒的外部库解决了这个问题 - https://code.google.com/p/xdeltaencoder/。我这样做的方式在下面发布为接受的答案

想象一下，我有两台独立的电脑，它们都有相同的 byte[] A。

其中一台电脑创建了 byte[] B，它几乎与 byte[] A 相同，但它是一个“较新”的版本。

为了让第二台电脑将他的 byte[] A 副本更新为最新版本（byte[] B），我需要将整个 byte[] B 传输到第二台电脑。如果 byte[] B 的大小有很多 GB，这将花费太长时间。

是否可以创建一个 byte[] C 是 byte[] A 和 byte[] B 之间的“差异”？对 byte[] C 的要求是知道 byte[] A，就可以创建 byte[] B。

这样，我只需将 byte[] C 传输到第二台 PC，理论上它只是 byte[] B 大小的一小部分。

我正在寻找用 Java 解决这个问题的方法。

非常感谢您提供的任何帮助:)

编辑：在大多数情况下，数据更新的性质是额外的字节被插入到数组的一部分中。当然，可能会更改某些字节或删除某些字节。byte[] 本身代表目标 PC 上所有文件/文件夹名称的树。byte[] 最初是通过创建自定义对象树，使用 JSON 编组它们，然后使用 zip 算法压缩该数据来创建的。我正在努力创建一种可以智能地创建对象 c 的算法。

编辑2：非常感谢这里的每个人提供的所有帮助，我很抱歉这么长时间没有活跃。我很可能会尝试让一个外部库为我进行增量编码。关于这个线程的一个重要部分是我现在知道我想要实现的目标是什么！我相信，当我找到合适的解决方案时，我会发布并接受它，以便其他人可以看到我是如何解决我的问题的。再次，非常感谢您的帮助。

4

4 回答 4

3

使用“更改事件”的集合而不是发送整个数组

对此的解决方案是发送一个描述更改的序列化对象，而不是重新发送实际数组。

public class ChangePair implements Serializable{
    //glorified struct
    public final int index;
    public final  byte newValue;

    public ChangePair(int index, byte newValue) {
        this.index = index;
        this.newValue = newValue;
    }

    public static void main(String[] args){

        Collection<ChangePair> changes=new HashSet<ChangePair>();

        changes.add(new ChangePair(12,(byte)2));
        changes.add(new ChangePair(1206,(byte)3));

    }
}

生成“更改事件”

实现这一目标的最有效方法是随时跟踪更改，但假设这是不可能的，您可以强行通过，找出哪些值不同

public static Collection<ChangePair> generateChangeCollection(byte[] oldValues, byte[] newValues){
    //validation
    if (oldValues.length!=newValues.length){
        throw new RuntimeException("new and old arrays are differing lengths");
    }

    Collection<ChangePair> changes=new HashSet<ChangePair>();

    for(int i=0;i<oldValues.length;i++){
        if (oldValues[i]!=newValues[i]){
            //generate a change event
            changes.add(new ChangePair(i,newValues[i]));
        }
    }

    return changes;
}

发送和接收这些更改事件

根据这个关于通过互联网发送序列化对象的答案，您可以使用以下代码发送您的对象

Collection<ChangePair> changes=generateChangeCollection(oldValues,newValues);

Socket s = new Socket("yourhostname", 1234);
ObjectOutputStream out = new ObjectOutputStream(s.getOutputStream());
out.writeObject(objectToSend);
out.flush();

在另一端，您将收到该对象

ServerSocket server = new ServerSocket(1234);
Socket s = server.accept();
ObjectInputStream in = new ObjectInputStream(s.getInputStream());
Collection<ChangePair> objectReceived = (Collection<ChangePair>) in.readObject();
//use Collection<ChangePair> to apply changes

使用这些更改事件

然后可以简单地使用此集合来修改另一端的字节数组

public static void useChangeCollection(byte[] oldValues, Collection<ChangePair> changeEvents){
    for(ChangePair changePair:changeEvents){
        oldValues[changePair.index]=changePair.newValue;
    }
}
于 2014-01-24T11:26:37.743 回答
1

在本地记录对字节数组的更改，就像一个小的版本控制系统。事实上，您可以使用 VCS 创建补丁文件，将它们发送到另一端并应用它们以获取最新文件；

如果您无法记录更改，则需要在本地将数组加倍，或者（不是 100% 安全）在块上使用校验和数组。

于 2014-01-24T11:20:27.190 回答
1

所以，我最终做的是使用这个：

https://code.google.com/p/xdeltaencoder/

从我的测试来看，它真的很好用。但是，您需要确保校验源（在我的情况下为 fileAJson），因为它不会自动为您完成！

无论如何，下面的代码：

//Create delta
String[] deltaArgs = new String[]{fileAJson.getAbsolutePath(), fileBJson.getAbsolutePath(), fileDelta.getAbsolutePath()};
XDeltaEncoder.main(deltaArgs);

//Apply delta
deltaArgs = new String[]{"-d", fileAJson.getAbsolutePath(), fileDelta.getAbsolutePath(), fileBTarget.getAbsolutePath()};
XDeltaEncoder.main(deltaArgs);

//Trivia, Surpisingly this also works
deltaArgs = new String[]{"-d", fileBJson.getAbsolutePath(), fileDelta.getAbsolutePath(), fileBTarget.getAbsolutePath()};
XDeltaEncoder.main(deltaArgs);
于 2014-02-09T02:30:48.413 回答
1

这里的主要问题是数据压缩。

Kamikaze为您提供了很好的数据数组压缩算法。它使用Simple16 和 PForDelta 编码。Simple16 是一个很好的（正如其名称）简单的列表压缩选项。或者您可以使用运行 长度 编码。或者您可以尝试使用 Java 中可用的任何压缩算法...

无论如何，如果您首先预处理数据，您使用的任何方法都将得到优化。

您可以减少数据计算差异，或者正如@RichardTingle 指出的那样，创建不同数据位置对。

您可以计算C为B- A。A必须是一个int数组，因为两个值之间的差异byte可能高于255. 然后您可以恢复B为A+ C。

在这里结合至少两种方法的好处是可以获得更好的结果。

例如，如果您将差异方法与A = { 1, 2, 3, 4, 5, 6, 7 }and一起使用B = { 1, 2, 3, 5, 6, 7, 7 }。差异数组C将是{ 0, 0, 0, 1, 1, 1, 0 }。RLE 可以C以非常有效的方式进行压缩，因为当序列中有许多重复数字时，它有利于压缩数据。

如果您的数据几乎在每个位置都发生变化，那么使用 Simple16 的差异方法会很好，但值之间的差异很小。0它可以将 28 个单位值 (或1) 的数组或 14 个 2 位值的数组压缩为单个 32 字节整数。

进行实验，这一切都取决于您的数据的行为方式。并比较每个实验的数据压缩率。

编辑：您必须在JSON 和 zip 压缩之前预处理数据。

创建两组old和now。后者包含现在存在的所有文件。对于前者，旧文件，您至少有两个选择：

  • 应该包含在您将它们发送到另一台 PC 之前存在的所有文件。您需要保留一组其他 PC 知道的信息，以计算自上次同步以来发生的变化，并仅发送新数据。

  • 包含自您上次检查更改后的所有文件。您可以保留本地更改历史记录并为每个版本指定一个“id”。然后，当您同步时，您将“版本 ID”与更改的数据一起发送到另一台 PC。下一次，另一台 PC 首先发送它的“版本 id”（或者您在本地保留每台 PC 的“版本 id”），然后您可以向另一台 PC 发送所有新更改（该 PC 之后的所有版本）有）。

更改可以由另外两个集合表示：newFiles和deleted文件。（内容发生变化的文件呢？您不需要同步这些文件吗？）newFiles包含仅存在于 set 中的文件now（而不存在于 中old）。该deleted集合包含仅存在于集合中old（不存在于now）中的文件。

如果您将每个文件表示为String具有完整路径名的 ，那么您将安全地拥有每个文件的唯一表示。或者你可以使用java.io.File.

在减少对文件集的更改后newFiles，deleted您可以将它们转换为 JSON、zip 并执行其他任何操作来序列化和压缩数据。

于 2014-01-24T11:53:11.857 回答