15

目标

如何对描述如何使用尽可能少的数据量将静态列表从一个订单重新排序到另一个订单的数据进行编码？

我觉得有一个算法或计算机科学术语可以帮助我，但现在我太困在这个问题上，无法找出其他看待它的方法。

背景动机

我有一个程序部署到一个远程位置，所有通信都是通过间歇性的极其昂贵的卫星连接进行的。这有点夸张，但数据成本接近每千字节一美元，而且每天只能发生几次。

在一天开始时，用户会得到一个项目列表，他们会去现场做一些事情，但最终结果或多或少是按不同顺序排序的相同项目列表。还有其他数据，但这对这个问题并不重要。

现在我正在发回所有发生的动作的记录并按顺序播放它们。随着用户对系统感到满意，移动记录列表开始接近仅将所有项目本身发回的大小，并且通常某些移动组合会导致撤消以前的移动记录。

假设

  • 起始列表和结束列表由完全相同的一组项目组成
  • 每个项目都有一个唯一的 id（32 位整数）
  • 每个项目都有一个唯一的排序顺序（32 位整数）
  • 用户将拥有数百到一千或更多项目的列表
  • 用户通常会在一天内重新订购大约 100 件此类商品
  • 可以检测到订单的更改将项目移动到列表中的新位置
  • 一些“动作”可能会撤销之前的动作
  • 用于计算最佳解决方案的计算资源便宜/无限
  • 传输时间昂贵
  • 发回更改数据比发回整个列表便宜

最简单的数据结构

为了解决这个问题，假设以下数据结构可用。

  • 项目清单
    • item_id
    • 排序
  • 移动记录
    • item_a_id
    • 新位置

这是一个示例列表。每个列表中的项目都是相同的。请注意，即使只有少数项目发生了变化，但每个项目 id 都有一个新的排序顺序，因此您不能只发回新的 item_id/sort_order_id 对。

**List 1: Original List**    **List 2: Re-ordered List**    
order - id                    order - id
     1. 10                         1. 90
     2. 20                         2. 30
     3. 30                         3. 40
     4. 40                         4. 50
     5. 50                         5. 60
     6. 60                         6. 10
     7. 70                         7. 80
     8. 80                         8. 70
     9. 90                         9. 20

如何使用尽可能少的数据量对将 List 1 的顺序转换为 List 2 的顺序所需的更改进行编码？

出于好奇，是否有可能证明存在最优解？

更新

一位同事指出，“交换”可能不是正确的思考方式。您还可以将项目发送到列表的顶部或底部，这更像是移动而不是交换。交换然后变成两个动作的组合。

感谢您的指点。到目前为止，我还没有看到有保证的最佳解决方案。加上问题只是改变了一点。

如果我不能证明任何一种方法都能产生最佳结果，那么我将使用每种方法找出一个解决方案，并用一个小标题发回该解决方案，指示所使用的方法。不过，请继续提出解决方案，我将通过我的研究更新这个问题。

感谢大家！

4

8 回答 8

2

算法部分：

列表的重新排序称为置换。每个排列可以分成一组循环，每个循环的 N 个元素都需要 (N - 1) 次交换。例如

1, 2, 3, 4, 5, 6 --> 3, 2, 4, 1, 6, 5

这可以分为 1 - 4 - 3（需要 2 次交换） 2 - 2（0 次交换） 5 - 6（1 次交换）

要找到解决方案，您只需选择错误位置的任何元素并将其放在原位即可。

细节部分：

当然，您可以使用更小的数据类型、RLE 或其他一些编码算法等等。

非常理论但不实用的部分。

N 个数字序列的所有排列都可以按字典顺序排列，从 0 到 (N! - 1) 的一个数字足以表示该序列。因此，理论上最好的答案是：计算排列的索引，传输它，通过该索引重新创建排列。

于 2009-10-14T23:10:28.653 回答
1

我不确定分析掉期能给你带来什么。正如您所说，它们可以相互撤消，并导致令人困惑的结果。

我相信您最好的选择是在重新排序的列表中识别该列表中相对于原始列表未重新排序的部分，即使它们从新位置开始。在您的示例中，这是从 30 到 60 的段。因此，在一种运行长度编码中，我将发回描述位置和长度的段图。

同样，使用您的示例数据：有序起始索引列表，长度：

{ (9, 1) , (3, 4) , (1, 1) , (8, 1) , (7, 1) , (2, 1) }

似乎是您可以发回的最少信息量。数据的可压缩性取决于公共段的数量和大小。

（编辑）实际上，在我看来，如果交换的数量很少，将会有一些数据集的交换列表会更短。但是可能会有一些转折点，其中游程编码做得更好；在这种情况下，我会说计算两者并选择较小的一个。

于 2009-10-14T18:09:26.037 回答
1

您想要的是对列表进行排序所需的排列。您可以通过构建一个从 0 到 n 的索引列表，然后使用自定义比较函数对该列表进行排序，该函数比较相应索引处的项目。例如，在 Python 中：

perm = sorted(range(len(l)), key=lambda x:l[x])

然后，您可以通过连接发送“perm”，并使用它来获取排序列表：

for x in perm:
  print perm[x]

作为进一步的优化，如果大多数元素保持不变，则排列将是高度可压缩的——通过使用常规压缩或使用差异之类的变换（例如，将每个元素存储为与前一个元素的差异，而不是其绝对值），移动到前面和运行长度编码。

于 2009-10-14T18:11:45.923 回答
0

如果您真的想尽量减少通过网络传输的每一位数据，您将如何传输数据？例如，您是否以某种方式压缩它？如果您只有几千个项目，则使用 32 位数字进行排序可能有点过分了。16 位以 $$$ 的一半为您提供 65000 件物品。唯一 ID 也是如此。

于 2009-10-14T18:23:10.870 回答
0

假如说：

  • 您可以在现场设备和基本系统上保留原始数据和最终数据的副本
  • 当您谈论交换时，您的意思是列表中的两个项目相互交换

您最好的解决方案可能是：

与其在执行时保留您所做的所有交换的列表，不如在一天结束时比较您的开始和结束数据，然后生成进行更改所需的交换。这将忽略列表中保持不变的任何位置，即使它们只是因为一系列交换“取消”了一些变化而没有改变。如果你的数据采用a,b,a,b,...where的形式a告诉你下一个元素的索引以它们所在的顺序离开，并b告诉你要交换它的项目的索引。

因为您只进行交换而不是轮班，所以您很少会得到像样本数据这样的数据，其中 30、40 和 50 的顺序相同，但位置略有不同。由于交换的数量将在列表中原始项目数量的 1/4 到 1/10 之间，因此您通常会以相同的顺序和最初所在的位置拥有大量数据。假设进行了以下交换：

1 <-> 9
4 <-> 2
5 <-> 2

结果列表将是：

 1. 90                   
 2. 50                  
 3. 30                      
 4. 20                       
 5. 40                      
 6. 60                       
 7. 70                       
 8. 80                       
 9. 10

所以变化数据可以表示为：

 1,9,2,4,4,5

这只有六个值，可以表示为 16 位数字（假设您的初始列表中不会有超过 16,000 个项目）。因此，每个“有效”交换都可以用一个 32 位数字表示。由于实际交换的数量通常是原始列表大小的 1/5 到 1/2，因此您最终将通过网络发送原始列表中 10% 到 20% 的数据（或者更少，因为如果其中一些交换相互撤销，“有效”交换的数量可能会更少）。

于 2009-10-14T20:06:44.873 回答
0

一个快速的解决方法可能是使用Zobrist 哈希来发现您返回到先前订单的情况。也就是说，在每次交换之后，根据您达到的排列计算一个哈希值。每个哈希映射到迄今为止针对该特定排列找到的最短交换序列。

这可以通过一些探索性搜索轻松扩展 - Zobrist 哈希是作为优化游戏树搜索的一种方式而发明的。

当然，很容易为交换数量提供严格的下限 - 不在其所需位置的项目数量。然而，这个下限是否真的可以实现是一个更困难的问题。

于 2009-10-14T18:08:50.633 回答
0

另一种可能的解决方案，忽略您的数据结构......

为已更改的项目发送一组 ID/索引（如果它是完全随机的稀疏子集，只需列出它们）和描述该子集重新排序的排列数。排列数将需要一个大整数表示 - 大小应与 log(n!) 成比例，其中 n 是更改的项目数。

当然，排列数是从排列数组中定义的，但是在解码时可以避免这个细节。诀窍是对排列数进行编码，这样，一旦将正确的第一项交换到第一个槽中，您还可以导出一个新的排列数，该排列数对于数组的尾部是正确的。

那是...

while not empty(indexes)
  item-to-swap := permutation-no remainder len(indexes)
  permutation-no := permutation-no div len(indexes)
  if item-to-swap != 0 : swap slot[indexes[0]], slot[indexes[item-to-swap]]
  indexes := tail(indexes)

即使在开始时需要更改所有项目，也需要进行 != 0 检查 - 项目可能已在循环的早期向上交换到它的正确位置。

这并不试图优化交换次数——一个项目可能会向上交换几次，然后再向下交换到正确的位置。也就是说，排列数可能是数组随机排列的最佳空间表示。鉴于您的排列只影响整个数组的一小部分，为该子集使用较小的排列数很有意义。

于 2009-10-14T18:37:05.753 回答
0

正如彼得所说，最小化每个整数的大小是理想的——但事实上，你可以在不限制项目数量的情况下做到这一点。可变字节编码是一种仅使用必要的字节数来压缩整数序列的方法。最常用的方法是在每个字节中保留一个位，以指示该字节是否是当前列表项中的最后一个。

首先使用增量编码可能很有用。那是你存储整数之间的差异的地方，而不是整数本身——这意味着它们最终使用可变字节压缩得更好。当然，必须首先对存储的整数（在您的情况下可能是正在更改的项目的 ID）进行排序，但这对您来说似乎不是问题。

于 2009-10-17T11:41:37.897 回答