将项目列表分解为可用于表示它的最少组数的算法

Question

很抱歉提出这个宽泛的问题，但我正在为如何从这个问题着手而苦苦思索。我有一个模糊的想法，我实际上想做的是压缩算法所做的事情，但实际上我正在寻找有人指出我可以用来作为基础的写作方向。

基本上我有文件。该文件由多行组成。每行都是逗号分隔的项目列表。我想生成一个新列表，其中包含可用于构建原始文件的这些列表的最小子集数。

一个示例可能会更好地说明这一点，如果我有一个输入文件

A,B,C,D
E,B,C,D
F,B,C,D
G,B,C,H
A,I,J,D
1,2,3,4,5,6,7,8
9,5,6,7,2,3,4,1

我的输出应该是这样的

A
B,C
D
E
F
G
I,J
1
2,3,4
5,6,7
8
9

因为这是我需要建立原始列表的唯一组的最小数量。

我很确定我在描述压缩算法的工作（虽然我这样做不是为了压缩）但我找不到任何文档来实现这样的事情我正在尝试使用 C# 中的字符串数组 - 我能找到的最好的是 compressing/decompressing 一个字节数组的预构建库，这不是我想要的。我感觉最接近的是谷歌搜索“霍夫曼编码”，这似乎是我正在尝试做的事情的正确轨道，但老实说，我正在努力理解如何根据我正在阅读的内容实施任何事情。

Answer 1

所以你要重塑 Lempel-Zip？

我们的想法是，通过列出从当前位置向后的距离和要复制到输出流的长度来制作字典（就像您已经以某种方式制作的一样）。

来自维基百科的 LZ77 伪代码。

while input is not empty do
    prefix := longest prefix of input that begins in window
    
    if prefix exists then
        d := distance to start of prefix
        l := length of prefix
        c := char following prefix in input
    else
        d := 0
        l := 0
        c := first char of input
    end if
    
    output (d, l, c)
    
    discard l + 1 chars from front of window
    s := pop l + 1 chars from front of input
    append s to back of window
repeat

根据您的输入我们注意到 'A' 是第一个字符并且没有前缀，所以 (0,0,'A') 被写入并且'A'被添加到前缀。

下一个 'B' 不在前缀中所以它被添加，(0,0,'B') 和 'B' 被添加到前缀中，依此类推直到 'E' 包括在内。

接下来是'B'，已经存在，前缀中的'B'位置是-4，后面的'C'和'D'也在输入中所以长度是 3，(-4,3,'F')，'F' 是输入中的下一个。这意味着有时流中会重复一个 char，如果不需要将 \0 表示为 char 并将其用作前缀中的 no，则可以避免这种情况。

Answer 2

看起来很直接：

首先尝试A，第一个看到的字符。看看它后面是否总是跟同一个字符。回答 AB 和 AI，所以只是 [A]。将 [A] 添加到列表中。从输入中删除所有 [A]。

尝试 B（找到下一个字符）。看看它后面是否总是跟同一个字符。总是回答 BC，所以是的，现在还要看看 C 是否出现在它前面没有 B 的地方，它没有，所以将 [BC] 添加到列表中。从输入中删除所有 [BC]。

以此类推

将项目列表分解为可用于表示它的最少组数的算法

Algorithm to break down a list of item into the minimum number of groups that can be used to represent it

c#

algorithm

lossless-compression