我需要能够在压缩的大量文件(.txt)中搜索文本.压缩可以改为其他东西,甚至可以变成专有的.我想避免解压缩所有文件并压缩(编码)搜索字符串并在压缩文件中搜索.这应该可以使用霍夫曼压缩与所有文件的相同码本.我不想重新发明轮子,所以..任何人都知道,做这样的事情或霍夫曼算法实现和测试,或者一个更好的主意库？
提前致谢
在什么条件下,霍夫曼编码使字符串不可压缩？当所有角色以相同的频率/概率出现时？如果是这样,那怎么能证明这是真的呢？
我正在考虑使用霍夫曼代码来压缩文本，但使用可变长度的符号（字符串）。例如（使用下划线作为空格）：
huffman-code | symbol
------------------------------------
00 | _
01 | E
100 | THE
101 | A
1100 | UP
1101 | DOWN
11100 | .
11101 |
1111...
(etc...)
如何构建频率表？显然存在一些重叠问题，序列_TH出现的频率几乎与 一样THE，但在表中毫无用处（_和THE都有短霍夫曼代码）。
这样的算法存在吗？它有一个特殊的名字吗？生成频率表有哪些技巧？我需要对输入进行标记吗？我在文献/网络中没有找到任何内容。（所有这些让我也想到了基数树）。
我正在考虑使用迭代过程：
但我不知道如何防止重叠（_THvs THE）的问题。
我刚刚完成了霍夫曼压缩算法的创建。我使用 bytearray() 将压缩文本从字符串转换为字节数组。我正在尝试解压缩我的霍夫曼算法。但我唯一担心的是我无法将字节数组转换回字符串。是否有任何内置函数可以用来将我的字节数组（带有变量）转换回字符串？如果没有，是否有更好的方法将我的压缩字符串转换为其他内容？我尝试使用 byte_array.decode() 并得到以下结果：
print("Index: ", Index) # The Index
# Subsituting text to our compressed index
for x in range(len(TextTest)):
TextTest[x]=Index[TextTest[x]]
NewText=''.join(TextTest)
# print(NewText)
# NewText=int(NewText)
byte_array = bytearray() # Converts the compressed string text to bytes
for i in range(0, len(NewText), 8):
byte_array.append(int(NewText[i:i + 8], 2))
NewSize = ("Compressed file Size:",sys.getsizeof(byte_array),'bytes')
print(byte_array)
print(byte_array)
print(NewSize)
x=bytes(byte_array)
x.decode()
UnicodeDecodeError：“utf-8”编解码器无法解码位置 0 中的字节 0x88：起始字节无效
假设我有一个只有一个字符的大字符串 say x。我需要使用霍夫曼编码。霍夫曼编码是一棵完全二叉树。那么当我们根本不需要两片叶子时，如何为单个字符创建霍夫曼代码？
https://www.ietf.org/rfc/rfc1951.txt的 "3.2.7.动态霍夫曼码的压缩(BTYPE = 10)"部分描述了压缩期间使用的动态霍夫曼树的编码.在DEFLATE比特流中可能出现的这种编码霍夫曼树表示的最大大小(以位为单位)是多少？使用外部参考支持特定数字的额外点;-).
这是理解DEFLATE属性的理论问题.但当然它有实际应用,例如,"应该使用多大的缓冲区来保证解码霍夫曼树？"
我正在编写霍夫曼压缩/解压缩程序。我已经开始编写我的压缩方法，但我陷入困境。我试图读取文件中的所有字节，然后将所有字节放入字节数组中。将所有字节放入字节数组后，我创建一个int[]数组，用于存储每个字节的所有频率（索引为 ASCII 代码）。
它确实包含扩展 ASCII 表，因为int数组的大小为 256。但是，当我在文件中读取特殊字符（又名 ASCII 值高于 127 的字符）时，我就会遇到问题。我知道一个字节是有符号的，一旦超过 127 个数字限制（并且数组索引显然不能为负数），它就会环绕为负值，因此我尝试通过在指定时将其转换为有符号值来解决此问题我的数组索引 ( array[myByte&0xFF])。
这种方法有效，但它给了我错误的 ASCII 值（例如，如果字符的正确 ASCII 值是 134，我反而得到 191 或其他值）。更烦人的是，我注意到特殊字符被分成 2 个单独的字节，我觉得这会在以后引起问题（例如当我尝试解压缩时）。
如何使我的程序与每种类型的字符兼容（该程序应该能够压缩/解压缩图片、mp3 等）。
也许我对此采取了错误的方法，但我不知道正确的方法是什么。请给我一些构建这个的提示。
树：
package CompPck;
import java.util.TreeMap;
abstract class Tree implements Comparable<Tree> {
public final int frequency; // the frequency of this tree
public Tree(int freq) { frequency = freq; }
// compares on the frequency
public int compareTo(Tree tree) {
return frequency - tree.frequency;
}
}
class Leaf …我注意到C中的单个位没有内置结构.有(无符号)char和int,它们是8位(一个字节),long是64+位,依此类推(uint64_t) ,布尔...)
我在编写一个霍夫曼树时遇到了这个问题,并且某些字符的编码不一定是8位长(如00101),因此没有有效的方法来存储编码.我必须找到临时解决方案,如字符串或布尔数组,但这需要更多的内存.
但不管怎么说,我的问题是更普遍:有存储的一个很好的方式阵位,或某种用户定义的结构吗？我在网上搜索了一个,但最小的结构似乎是8位(一个字节).我试过这样的东西,int a : 1但它没有用.我读到了有关字段的内容,但它们并不能简单地实现我想做的事情.我知道在C++中已经有人问过这个问题,如果有一个单位的结构,但大多数情况下我想知道什么是在C中存储编码如00101的最有效内存的方法.
这个问题是关于RFC-1951的第 3.2.7 节，重建动态霍夫曼树。
每个代码由代码长度序列定义，使得给定位长度的所有代码都具有字典顺序连续的值。
例如，这里是一个 rgb(255,0,0) 50x50 png，其中 IDAT 是来自 DEFLATE 的动态哈夫曼树。
0000024: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx CIDATx
000002a: xxxxxxxx 11101101 11001111 00110001 00010001 00000000 ...1..
0000030: 00000000 00001000 00000000 10100001 11101111 01011111 ....._
0000036: 01011010 00110011 10111000 01111010 00001100 00000100 Z3.z..
000003c: 10100000 10101001 11111001 00100000 00010001 00010001 ... ..
0000042: 00010001 00010001 00010001 00010001 00010001 00010001 ......
0000048: 00010001 00010001 00010001 00010001 00010001 00010001 ......
000004e: 00010001 00010001 00010001 00010001 00010001 00010001 ......
0000054: …给定 15 个随机十六进制数（60 位），其中每 20 位运行（5 个十六进制）中总是至少有 1 个重复。
压缩字节的最佳方法是什么？
这里有些例子：
01230 45647 789AA
D8D9F 8AAAF 21052
20D22 8CC56 AA53A
AECAB 3BB95 E1E6D
9993F C9F29 B3130
最初，我一直尝试仅在 20 位上使用霍夫曼编码，因为霍夫曼编码可以从 20 位降低到约 10 位，但存储表需要超过 9 位。
这是显示 20 位 -> 10 位的细分 01230
Character Frequency Assignment Space Savings
0 2 0 2×4 - 2×1 = 6 bits
2 1 10 1×4 - 1×2 = 2 bits
1 1 110 1×4 - 1×3 = 1 bits
3 1 111 1×4 - 1×3 …